Advent of Code 2023 Day 4 Highlights

Day 4 introduces one of the core algorithmic techniques: dynamic programming aka memoization in the functional programming world. I really liked the design of the puzzle: the first part contains a very nice hint on how to approach part 2.

This day was yet again an Elixir day for me. I love this language a bit too much, it seems :) Here’s the livebook.

Parsing

As usual, some String.splits, Enum.maps, and pattern matching:

def parse_input(input) do
  cards = String.split(input, "\n", trim: true)

  Enum.map(cards, fn card ->
    [id, numbers] = String.split(card, ": ")
    id = String.replace_prefix(id, "Card ", "") |> String.trim() |> String.to_integer()

    numbers = numbers |> String.split(" | ")

    [winning_numbers, numbers_you_have] =
      Enum.map(numbers, fn numbers ->
        String.split(numbers)
        |> Enum.map(&String.trim/1)
        |> Enum.map(&String.to_integer/1)
      end)

    %{id: id, winning_numbers: winning_numbers, numbers_you_have: numbers_you_have}
  end)
end

I didn’t bother with structs today, and went for a plain list of maps to represent the task’s input.

Part 1

Originally, I wrote part 1 as a simple cell, but ofc. for the final solution and for using it in the part 2, I ended up extracting it into 2 functions:

def count_wins(input) do
  Enum.map(input, fn card ->
    MapSet.new(card.numbers_you_have)
    |> MapSet.intersection(MapSet.new(card.winning_numbers))
    |> MapSet.size()
  end)
end

def p1(input) do
  count_wins(input)
  |> Enum.map(fn wins ->
    if wins == 0, do: 0, else: 2 ** (wins - 1)
  end)
  |> Enum.sum()
end

The key here is recognizing that we are doing powers of two here, which makes the task trivial. And the efficient way to count a number of common unique elements in 2 lists is a set intersection.

Note the output we get from the count_wins function, since it’ll be useful to understand the solution for part 2:

[4, 2, 2, 1, 0, 0]

Part 2

The key to solving part 2 is recognizing that the last card will never produce any copies. If we walk the list of the count_wins from the back, we can calculate precisely how many total copies of all cards below it each card will produce (accounting for the copies produced by the copies, etc.)

To simplify this computation we use an old functional programming technique - memoization. Since we walk the list from the back, we can use Enum.reduce and maintain a map from the card id to its total count of produced card copies. Let’s look at the whole thing and then take it step by step.

def card_id_to_produced_copies(input) do
  count_wins(input)
  |> Enum.with_index(fn el, idx -> {idx + 1, el} end)
  |> Enum.map(fn {id, copies} ->
    if copies > 0 do
      {id, Enum.map(1..copies, fn x -> x + id end)}
    else
      {id, []}
    end
  end)
  |> Enum.reverse()
  |> Enum.reduce(
    %{},
    fn
      {card_id, []}, memo -> Map.put(memo, card_id, 0)
      {card_id, wins_card_ids}, memo ->
        copies_to_win = Enum.map(wins_card_ids, &Map.get(memo, &1)) |> Enum.sum()
        Map.put(memo, card_id, copies_to_win + length(wins_card_ids))
    end
  )
end

We start by reusing the output of the count_wins function we used in the part 1. This will just show us the number of copies each card will make in the part 2. For test input it’ll look like this:

[4, 2, 2, 1, 0, 0]

Next, we associate each of those copy numbers with the card id:

[{1, 4}, {2, 2}, {3, 2}, {4, 1}, {5, 0}, {6, 0}]

And now we can replace the number of copies with the card ids that will be copied:

[
  {1, [2, 3, 4, 5]},
  {2, [3, 4]},
  {3, [4, 5]},
  {4, [5]},
  {5, []},
  {6, []}
]

As you can see, the last (and, in this case, the one before the last) card won’t produce any copies. Let’s reverse this list:

[
  {6, []},
  {5, []},
  {4, [5]},
  {3, [4, 5]},
  {2, [3, 4]},
  {1, [2, 3, 4, 5]}
]

And now we call Enum.reduce and maintain a memo accumulator while walking through the list. This memo map will contain the total number of copies each card will produce, accounting for transitive copies produced by the copied cards.

For the cards #6 and #5 no copies will be produced, so memo becomes %{5 => 0, 6 => 0} by the time we process card #4.

Card #4 will only copy card #5, and we can get the total number of produced copies for card #5 from the memo - it’s 0, we add it to the 1 copy produced directly by card #4, and we save this value 1 in the memo.

For card #3, we produce copies of cards #4 and #5. We take the total produced copies for them from the memo - 1 and 0, sum them and add the 2 copies produced directly by card #3 - the result is 3, and we save that in the memo.

Repeating this for the remaining cards, we arrive at the following state in the memo:

%{
  1 => 14,
  2 => 6,
  3 => 3,
  4 => 1,
  5 => 0,
  6 => 0
}

We can use this to arrive at the answer for the part2:

def p2(input) do
  total_copies_produced = card_id_to_produced_copies(input) |> Map.values() |> Enum.sum()
  total_copies_produced + length(input)
end

We just sum all the values in the memo aka result of the card_id_to_produced_copies(input) call and add the number of cards we start with.