Advent of Code 2020: Day 16

aoc_2020_day_16.exs

defmodule Advent2020.Day16 do

  def input, do: File.read!(Path.expand("day16.txt", :code.priv_dir(:advent_2020)))

  defp split_lines(str), do: String.split(str, "\n", trim: true)
  defp to_int(str), do: String.to_integer(str)

  defp parse_fields(fields) do
    Map.new(split_lines(fields), fn field ->
      [_, name, a1, a2, b1, b2] = Regex.run(~r/([a-z ]+): (\d+)-(\d+) or (\d+)-(\d+)/, field)
      {name, {{to_int(a1), to_int(a2)}, {to_int(b1), to_int(b2)}}}
    end)
  end

  defp parse_ticket(ticket), do: String.split(ticket, ",") |> Enum.map(&to_int/1)

  defp parse_my_ticket(ticket) do
    ["your ticket:", ticket] = split_lines(ticket)
    parse_ticket(ticket)
  end

  defp parse_nearby_tickets(tickets) do
    ["nearby tickets:" | tickets] = split_lines(tickets)
    Enum.map(tickets, &parse_ticket/1)
  end

  def parse(input) do
    [fields, ticket, nearby] = String.split(input, "\n\n", trim: true)

    %{
      fields: parse_fields(fields),
      ticket: parse_my_ticket(ticket),
      nearby: parse_nearby_tickets(nearby)
    }
  end

  defp match_field?({_name, {{a1, a2}, {b1, b2}}}, value) do
    (value >= a1 && value <= a2) || (value >= b1 && value <= b2)
  end

  defp valid_ticket_value?(fields, value) do
    Enum.any?(fields, &match_field?(&1, value))
  end

  defp valid_ticket?(fields, ticket) do
    Enum.all?(ticket, &valid_ticket_value?(fields, &1))
  end

  def part_one(%{nearby: nearby, fields: fields}) do
    nearby
    |> Enum.flat_map(&Enum.reject(&1, fn ticket -> valid_ticket_value?(fields, ticket) end))
    |> Enum.sum()
  end

  # we assigned all fields to a position successfully
  defp assign_fields_to_position([], assigned), do: Enum.reverse(assigned)

  # we dont have any fields for current position, backtrack
  defp assign_fields_to_position([[] | _rest_positions], _assigned), do: :invalid

  defp assign_fields_to_position([[field | remaining_possible_fields] | rest_positions], assigned) do
    with false <- Enum.member?(assigned, field),
         ordered_fields when is_list(ordered_fields) <-
           assign_fields_to_position(rest_positions, [field | assigned]) do
      ordered_fields
    else
      _ ->
        assign_fields_to_position([remaining_possible_fields | rest_positions], assigned)
    end
  end

  def part_two(%{nearby: nearby, ticket: my_ticket, fields: fields}) do
    Enum.filter(nearby, &valid_ticket?(fields, &1))
    |> Enum.zip()
    |> Enum.map(fn nearby_col ->
      nearby_col = Tuple.to_list(nearby_col)

      # find all fields possible for current column/position
      Enum.filter(fields, fn field -> Enum.all?(nearby_col, &match_field?(field, &1)) end)
      |> Enum.map(fn {name, _} -> name end)
    end)
    |> assign_fields_to_position([])
    |> Enum.zip(my_ticket)
    |> Enum.reduce(1, fn
      {"departure " <> _, value}, result -> value * result
      _, result -> result
    end)
  end
end