Advent of Code 2020 - Day 16

This topic is about Day 16 of the Advent of Code 2020 .

Thanks to @egze, we have a private leaderboard:
https://adventofcode.com/2020/leaderboard/private/view/39276

The join code is:
39276-eeb74f9a

Just solved part 1. I find the code not elegant but it did give me a star.

Takes ~9s for part two, can be optimized further I guess.
EDIT: fixed, now it takes 0.4s

I’m kind of surprised that I can just ‘chain’ my valid tickets eventually into a nice map of keys to column indices (e.g. "row" => 1)…

Explanation:

  1. Get valid tickets
  2. Pivot them so that you get a map of column indices to all the values of that column
  3. Map that to a tuple {col, matches} where matches is a list of possible keys
  4. Sort by the count of matches (almost there)
  5. Reduce to another map, this time keyed by the key with the column index as the value
  6. Filter for map entries where the key starts with "departure"
  7. Perform the final reduction by multiplication
    # snippet only
    {rules, own, nearby} = process(input)
    Enum.filter(nearby, &(elem(&1, 1) == []))
    |> Enum.map(fn {ticket, _} -> Map.new(Enum.with_index(ticket), fn {n, index} -> {index, [n]} end) end)
    |> Enum.reduce(&(Map.merge(&1, &2, fn _, v1, v2 -> v1 ++ v2 end)))
    |> Enum.map(
         fn {col, values} ->
           {col, Enum.map(Enum.filter(rules, fn {_, valid?} -> Enum.all?(values, valid?) end), &(elem(&1, 0)))}
         end
       )
    |> Enum.sort_by(&(length(elem(&1, 1))))
    |> Enum.reduce(Map.new(), fn {col, matches}, acc -> Map.put(acc, hd(matches -- Map.keys(acc)), col) end)
    |> Enum.filter(fn {key, _} -> String.starts_with?(key, "departure") end)
    |> Enum.reduce(1, fn {_, col}, acc -> Enum.at(own, col) * acc end)
1 Like

Here is my solution.

My solution.

Used a comprehension to generate a list of all valid fields for each index and then reducing that. Will try to revisit this part later though and see how it can be improved.

Me too ! :sweat_smile: we arrive pretty much at the same conclusion

My strategy is to find all possible field names for each column. If a column has only 1 candidate field, then that field name of that column is taken and set to that column. Then I look at the columns that have 2 candidate fields. Subtract the candidate fields by the already taken fields, and I get more fields set. Then I look at the columns with 3 candidate fields, and then those with 4 candidate fields, so on and so forth.

#!/usr/bin/env elixir

to_range = fn str ->
  str
  |> String.split("-")
  |> Enum.map(&String.to_integer/1)
  |> (fn[a, b]-> a..b end).()
end

parse_rule = fn line ->
  [field_name | ranges] = Regex.scan(~r/^([^:]+): (\d+-\d+) or (\d+-\d+)$/, line, capture: :all_but_first)
                          |> List.flatten()
  {field_name, Enum.map(ranges, to_range)}
end

rules = "day16-rules.txt"
        |> File.stream!()
        |> Enum.map(parse_rule)
        |> Map.new()

rule_values = Map.values(rules)

invalid? = &Enum.all?(rule_values, fn [rule1, rule2] -> &1 not in rule1 and &1 not in rule2 end)

transpose = fn matrix -> 
  matrix
  |> Enum.zip()
  |> Enum.map(&Tuple.to_list/1)
end

valid_tickets = "day16-nearby-tickets.txt"
                |> File.stream!()
                |> Stream.map(&String.trim/1)
                |> Stream.map(&String.split(&1, ","))
                |> Stream.map(&Enum.map(&1, fn s -> String.to_integer(s) end))
                |> Enum.reject(&Enum.any?(&1, invalid?))
                |> transpose.()

in_any_range? = fn value, ranges ->
  Enum.any?(ranges, & value in &1)
end

find_all_candidate_fields = fn values ->
  rules
  |> Enum.filter(fn{_field_name, ranges}-> 
    Enum.all?(values, fn v -> in_any_range?.(v, ranges) end)
  end)
  |> Enum.map(&elem(&1, 0))
  |> MapSet.new()
end

fields = valid_tickets
         |> Enum.map(find_all_candidate_fields)
         |> Enum.with_index()
         |> Enum.sort_by(&MapSet.size(elem(&1, 0)))
         |> (fn ls -> [{MapSet.new(), -1} | ls] end).()
         |> Enum.chunk_every(2, 1, :discard)
         |> Enum.reduce({[], MapSet.new()}, fn [{fs1, _i1}, {fs2, i2}], {acc, seen} ->
           seen = MapSet.union(seen, fs1)
           [f] = fs2 |> MapSet.difference(seen) |> MapSet.to_list()
           {[{f, i2} | acc], seen}
         end)
         |> elem(0)
         |> Enum.sort_by(&elem(&1, 1))
         |> Enum.map(&elem(&1, 0))

File.read!("day16-my-ticket.txt")
|> String.trim()
|> String.split(",")
|> Enum.map(&String.to_integer/1)
|> Enum.zip(possible_fields)
|> Enum.filter(fn {_value, field_name} -> String.starts_with?(field_name, "departure") end)
|> Enum.map(&elem(&1, 0))
|> Enum.reduce(&*/2)
|> IO.inspect()

Was a bit worried that my answer was quite complex, with multiple maps, transposing, tracking seen values, and nlogn filtering, but it seems that’s what everyone else did too. :relieved:

I need to focus on work for the next couple of weeks, so I’ll only be looking at the remaining problems on days off from now on.

3 Likes

Enum.zip to transpose. Wish I’d thought of that.

3 Likes

My code for today :grinning:

Part1 / Part2

I really struggled with Part2 :exploding_head:

I first tried a brute force recursion approach which timed-out, then I trashed all my code and went for another approach which returns the proper result in 20ms.

I only made this code longer because I had not the leisure to make it shorter. cough

defmodule Day16 do
  def readinput() do
    [labelranges, myticket, nearbytickets] =
      File.read!("16.input.txt")
      |> String.split("\n\n")
      |> Enum.map(&String.split(&1, "\n", trim: true))

    # my ticket and nearby ticket sections starts with a header string
    # use tl() to skip that
    [
      ranges(labelranges),
      ticketsplit(List.last(myticket)),
      Enum.map(tl(nearbytickets), &ticketsplit/1)
    ]
  end

  @doc """
  Takes a list of strings like

  ["class: 1-3 or 5-7", "row: 6-11 or 33-44", "seat: 13-40 or 45-50"]

  and returns a dictionary of string keys, list of ranges values

    %{
        "class" => [1..3, 5..7],
        "row" => [6..11, 33..44],
        "seat" => [13..40, 45..50]
      },
  """
  def ranges(labels) do
    labels
    |> Enum.map(fn rule ->
      [label, r1start, r1end, r2start, r2end] =
        Regex.run(~r/(.*): (\d+)-(\d+) or (\d+)-(\d+)/, rule, capture: :all_but_first)

      {label,
       [
         String.to_integer(r1start)..String.to_integer(r1end),
         String.to_integer(r2start)..String.to_integer(r2end)
       ]}
    end)
    |> Map.new()
  end

  @doc """
  Splits a comma-separated list of numbers as a string and
  returns a list of numbers.
  """
  def ticketsplit(ticket) do
    String.split(ticket, ",")
    |> Enum.map(&String.to_integer/1)
  end

  def part1([rangemap, _, nearbytickets] \\ readinput()) do
    allranges = Map.values(rangemap) |> List.flatten()

    Enum.flat_map(nearbytickets, fn ticket ->
      Enum.reject(ticket, fn field ->
        Enum.any?(allranges, fn range ->
          field in range
        end)
      end)
    end)
    |> Enum.sum()
  end

  ################ part 2 ################

  def part2([rangemap, myticket, nearbytickets] \\ readinput()) do
    allranges = Map.values(rangemap) |> List.flatten()

    validtickets =
      Enum.filter(nearbytickets, fn ticket ->
        length(ticket) ==
          Enum.filter(ticket, fn field ->
            Enum.any?(allranges, fn range ->
              field in range
            end)
          end)
          |> Enum.count()
      end)
      |> Enum.map(&fieldtolabel(&1, rangemap))

    numtickets = length(validtickets)

    # labels starting with "departure"
    departuresidx =
      process(validtickets, numtickets)
      |> Enum.reduce([], fn {idx, label}, acc ->
        if String.starts_with?(label, "departure"), do: [idx | acc], else: acc
      end)

    # finally, calculate the product of the departure fields in my ticket
    myticket
    |> Enum.with_index()
    |> Enum.reduce(1, fn {val, idx}, acc ->
      if idx in departuresidx, do: acc * val, else: acc
    end)
  end

  @doc """

  Take a list of tickets and return a list of matching labels against
  each ticket item.  Find the matching labels by checking every item in
  each ticket with the label ranges.
  """
  def fieldtolabel(ticket, rangemap, result \\ [])

  def fieldtolabel([], _, result), do: Enum.reverse(result)

  def fieldtolabel([t | ticket], rangemap, result) do
    labels =
      Enum.filter(rangemap, fn {_label, [r1, r2]} ->
        t in r1 or t in r2
      end)
      |> Enum.map(fn {k, _v} -> k end)

    fieldtolabel(ticket, rangemap, [labels | result])
  end

  @doc """
  Take something like

    [
      [["row", "seat"], ["class", "row", "seat"], ["class", "row", "seat"]],
      [["class", "row"], ["class", "row", "seat"], ["class", "row", "seat"]],
      [["class", "row", "seat"], ["class", "row"], ["class", "row", "seat"]]
    ]

  and rotate it so the first column becomes the first row, etc.  Then, flatten the
  list:

    [["row", "seat"], ["class", "row"], ["class", "row", "seat"]]
    [["class", "row", "seat"], ["class", "row", "seat"], ["class", "row"]]
    [["class", "row", "seat"], ["class", "row", "seat"], ["class", "row", "seat"]]

    =>

    ["row", "seat", "class", "row", "class", "row", "seat"]
    ["class", "row", "seat", "class", "row", "seat", "class", "row"]
    ["class", "row", "seat", "class", "row", "seat", "class", "row", "seat"]

  Calculate the frequency of each item in each row, and filter out all
  items that do not show up in all of the original table's columns.
  We are left with the common fields.

  [["row"], ["class", "row"], ["class", "row", "seat"]]
  """
  def process(validtickets, numtickets) do
    bycolumn =
      for c <- 0..(length(List.first(validtickets)) - 1) do
        for r <- 0..(numtickets - 1) do
          Enum.at(validtickets, r) |> Enum.at(c)
        end
        |> List.flatten()
        |> Enum.frequencies()
        |> Enum.filter(fn {_k, v} -> v == numtickets end)
        |> Enum.map(fn {k, _v} -> k end)
      end
      |> Enum.with_index()

    # take something like [{["seat"], 0}]
    # and convert it to %{0 => "seat"}

    # "seat" is the common field in the first item of each row of validtickets

    colmap =
      bycolumn
      |> Enum.filter(fn {ks, _c} -> length(ks) == 1 end)
      |> Enum.reduce(%{}, fn {k, c}, acc -> Map.put(acc, c, List.first(k)) end)

    loop(colmap, bycolumn)
  end

  @doc """
  Loop until each column in bycolumn has one label
  """
  def loop(colmap, bycolumn) do
    if Enum.all?(bycolumn, fn {ks, _c} -> length(ks) == 1 end) do
      colmap
    else
      bycolumn =
        Enum.map(bycolumn, fn {ks, c} ->
          if length(ks) == 1 do
            {ks, c}
          else
            {MapSet.new(ks)
             |> MapSet.difference(MapSet.new(Map.values(colmap)))
             |> MapSet.to_list(), c}
          end
        end)

      colmap =
        bycolumn
        |> Enum.filter(fn {ks, _c} -> length(ks) == 1 end)
        |> Enum.reduce(%{}, fn {k, c}, acc -> Map.put(acc, c, List.first(k)) end)

      loop(colmap, bycolumn)
    end
  end
end

I did something different today by using nimble_parsec to parse the input data. But otherwise especially part 2 feels like awkwardly procedural. I could make it work, but it’s just an unnerving amount of nested iterations over lists.

1 Like

Didn’t take the time to clean this up since I wanted breakfast, but it came out okay.

Day16

So much iteration…

Today I didn’t have much time to work on this so my solution isn’t very refined (please nobody look at my parsing function); however it gets the job done reasonably fast.

defmodule AdventOfCode.Day16 do
  def part1(input) do
    {fields, _my_ticket, tickets} = parse_input(input)

    Enum.reduce(tickets, 0, fn ticket, total ->
      ticket
      |> Enum.map(fn ticket_field ->
        case Enum.find(fields, fn {_, r1, r2} -> ticket_field in r1 or ticket_field in r2 end) do
          nil -> ticket_field
          _range -> 0
        end
      end)
      |> Enum.sum()
      |> Kernel.+(total)
    end)
  end

  def part2(input) do
    {fields, my_ticket, tickets} = parse_input(input)

    # this mega-pipe should be split in different functions for better testability...
    # find the valid tickets
    Enum.reduce([my_ticket | tickets], [], fn ticket, valid_tickets ->
      ticket
      |> Enum.map(fn ticket_field ->
        case Enum.find(fields, fn {_, r1, r2} -> ticket_field in r1 or ticket_field in r2 end) do
          nil -> false
          _range -> true
        end
      end)
      |> Enum.all?(& &1)
      |> if(do: [ticket | valid_tickets], else: valid_tickets)
    end)
    # zip all the valid tickets into columns
    |> Enum.zip()
    |> Enum.map(&Tuple.to_list/1)
    |> Enum.with_index()
    |> Enum.map(fn {col, col_i} ->
      plaus =
        Enum.reduce(fields, [], fn {label, r1, r2}, plausible ->
          if Enum.all?(col, fn f -> f in r1 or f in r2 end),
            do: [label | plausible],
            else: plausible
        end)

      {plaus, col_i}
    end)
    # find the correct field for each column
    |> Enum.sort(fn {p1, _}, {p2, _} -> length(p1) < length(p2) end)
    |> Enum.reduce(%{}, fn {plaus, i}, assigned ->
      Enum.reduce_while(plaus, assigned, fn p, ass ->
        if Map.has_key?(ass, p), do: {:cont, ass}, else: {:halt, Map.put(ass, p, i)}
      end)
    end)
    |> Enum.filter(fn {k, _v} -> String.starts_with?(k, "departure") end)
    |> Enum.map(fn {_k, v} -> Enum.at(my_ticket, v) end)
    |> Enum.reduce(&Kernel.*/2)
  end

  def parse_input(input) do
    # this parser function is disgusting, maybe refactor with nimbleparsec
    [fields, my_ticket, tickets] = String.split(input, "\n\n", trim: true)

    fields =
      fields
      |> String.split("\n", trim: true)
      |> Enum.map(fn line ->
        [label, ranges] = String.split(line, ": ")
        [r1, r2] = String.split(ranges, " or ")
        [r1a, r1b] = String.split(r1, "-")
        [r2a, r2b] = String.split(r2, "-")

        {label, String.to_integer(r1a)..String.to_integer(r1b),
         String.to_integer(r2a)..String.to_integer(r2b)}
      end)

    [_, my_ticket] = String.split(my_ticket, "\n", trim: true)
    my_ticket = my_ticket |> String.split(",") |> Enum.map(&String.to_integer/1)

    [_ | tickets] = String.split(tickets, "\n", trim: true)

    tickets =
      tickets |> Enum.map(fn t -> t |> String.split(",") |> Enum.map(&String.to_integer/1) end)

    {fields, my_ticket, tickets}
  end
end

My solution uses MapSets of all possible values for each field, and MapSet.member? to test validity. Maybe not the most efficient way, but it still runs very fast. With ticket indexes 0 to 19, I used a Reduce to check each index and save the results, then another Reduce on my ticket to get the product of the appropriate indexes.

Day 16

Refactored my answer to remove almost all usages of Map and MapSet in favour of lists. I also stole @Aetherus’ Enum.zip idea for transpose. Much happier with it now. Here it is without the input parsing:

def run do
  {rules, my_ticket, tickets} = File.read!("input") |> parse_input()

  tickets
  |> Enum.filter(&valid?(&1, rules))
  |> transpose_tickets()
  |> valid_fields_for_columns(rules)
  |> reduce_to_column_by_field_name()
  |> Stream.filter(&match?({"departure" <> _, _idx}, &1))
  |> Stream.map(fn {_name, idx} -> my_ticket[idx] end)
  |> Enum.reduce(&Kernel.*/2)
  |> IO.puts()
end

def valid?(ticket, rules) do
  Enum.all?(ticket, fn field ->
    Enum.any?(rules, fn {_name, {range1, range2}} -> field in range1 || field in range2 end)
  end)
end

def transpose_tickets(tickets) do
  tickets |> Enum.zip() |> Enum.map(&Tuple.to_list/1) |> Enum.with_index()
end

# Compare each column against the rules to determine the list of fields each column satisfies
def valid_fields_for_columns(transposed_tickets, rules) do
  for {column, idx} <- transposed_tickets, do: {idx, valid_fields_for(column, rules)}
end

# Reduce the list of valid fields by elimination.
# The number of valid fields for each column is unique, which doesn't seem like a coincidence.
# Start with the column that only has one possible valid field, mark the field as seen.
# Continue to the column with two valid fields, subtract the seen field, mark remaining field as seen.
# Repeat for all columns.
def reduce_to_column_by_field_name(valid_fields_by_column) do
  valid_fields_by_column
  |> Enum.sort_by(fn {_k, v} -> length(v) end)
  |> Enum.map_reduce([], fn {col, fields}, seen ->
    [field] = fields -- seen
    {{field, col}, [field | seen]}
  end)
  |> elem(0)
end

def valid_fields_for(column, rules) do
  Enum.filter(rules, fn {_field, {range1, range2}} ->
    Enum.all?(column, fn val -> val in range1 || val in range2 end)
  end)
  |> Enum.map(&elem(&1, 0))
end

Happy to be stolen from :grin:

I’m not very happy with my solution either. I found that Enum.chunk_every(2, 1, :discard) is useless in my solution.

What is the benefit of using Lists over Map/Set? Is “in” faster than “member?” ?