Advent of Code 2024 - Day 19

I started with a straightforward solution I coded up in a few minutes, but it was taking too long on the real input, so I spent a while to rewrite it with a prefix tree (trie) instead. It ended up being too slow too, at which point I realized that, of course, I just needed to use memoization. So then I added it and was able to get the final answer. Ironically, it turned out that my original solution just lacked memoization as well so after adding it it ended up being even faster. Though both are slow compared to your runtime—definitely takes a few seconds for me. I didn’t parallelize, though.

With prefix tree and custom memoization: advent-of-code-2024/lib/advent_of_code2024/day19_trie.ex at main · ibarakaiev/advent-of-code-2024 · GitHub

Straightforward, using a nice memoization library: advent-of-code-2024/lib/advent_of_code2024/day19.ex at main · ibarakaiev/advent-of-code-2024 · GitHub

I do not use memoization. I was tempted to but the puzzles links to 2023 day 12 which is a huge hint on the solution.

For the first part, I just brute force but not with all towels, I start by removing all towels that can be created with other towels until there are only primitive towels left. This slows down patterns that are possible a little bit, but they are fast. It make the time to find impossible patterns very short.

For part two, for each target I start by removing towels that are not found in the pattern, to reduce the search scope. Then for each towel I check if the pattern starts with the towel, and when it does, I keep the rest of the pattern and I count 1, then I repeat with that list of “remainders” until the remainder is "" (keep the count), or unfinished (discard the count).

EDIT
yeah by adding a little bookkeeping I can compute a suffix only once

  defp count_combinations(target, towels) do
    possible_towels = Enum.filter(towels, fn {text, _} -> String.contains?(target, text) end)
    do_count([{target, 1}], possible_towels)
  end

  defp do_count([{"", count}], _) do
    count
  end

  defp do_count([longest | target_suffixes], towels) do
    {target_suffix, suffix_score} = longest

    new_suffixes =
      Enum.flat_map(towels, fn {h, b} ->
        case target_suffix do
          <<^h::binary-size(b), rest::binary>> -> [{rest, suffix_score}]
          _ -> []
        end
      end)

    target_suffixes = insert_all(target_suffixes, new_suffixes)

    do_count(target_suffixes, towels)
  end

  defp insert_all(target_suffixes, [h | t]), do: insert_all(insert(target_suffixes, h), t)
  defp insert_all(target_suffixes, []), do: target_suffixes

  defp insert([{longest, _} = top | t], {text, _} = new) when byte_size(text) < byte_size(longest) do
    [top | insert(t, new)]
  end

  defp insert([{same, count} | t], {same, add}) do
    [{same, count + add} | t]
  end

  defp insert(t, new) do
    [new | t]
  end

Part 2 is around 80ms when my computer is not busy doing its own life as usual.

Part 1 was nice and easy and I was amazed that the DFS I coded worked on literally the first try. That never ever happens.

Part 2 was a spanner in the works though - I have (what I think is) a nice solution, I’m not sure the name of the technique/algorithm I used though. Maybe memoization that everyone keeps mentioning.

https://github.com/sevenseacat/advent_of_code/blob/main/lib/y2024/day19.ex

I use a priority queue to keep track of the leftover strings to process for each requested towel, and a cache to track how many times I’ve seen each string.

If a string comes up in the queue and I’ve seen it before, then I can discard it and increment the number of different ways we’ve gotten to this point in the cache (by the number of ways we got to the previous point). Then, when the empty string comes up in the queue, I’ve seen all the ways to get here and can pluck it out of my cache. Works pretty well!

Name                     ips        average  deviation         median         99th %
day 19, part 1         29.38       34.03 ms     ±0.86%       34.01 ms       35.47 ms
day 19, part 2         29.36       34.06 ms     ±1.18%       34.03 ms       36.73 ms

Nice, I guess my last optimization could be refined again and I would end up with that you did directly haha

Surprisingly short code for today’s solution. I guess part 2 is not the fastest, but I don’t think it’s too bad for something I just made up on the spot.

defmodule Day19 do
  def parse(input) do
    [towels, patterns] = String.split(input, "\n\n")
    towels = String.split(towels, ", ")
    patterns = String.split(patterns, "\n", trim: true)

    {towels, patterns}
  end

  def possible?("", _towels), do: true

  def possible?(pattern, towels) do
    towels
    |> Enum.any?(fn towel ->
      case pattern do
        ^towel <> remaining -> possible?(remaining, towels)
        _ -> false
      end
    end)
  end

  def arrangements(pattern, towels) when is_binary(pattern) do
    arrangements(%{pattern => 1}, towels)
  end

  def arrangements(patterns, _towels) when map_size(patterns) == 0, do: 0

  def arrangements(%{"" => result} = patterns, _towels) when map_size(patterns) == 1, do: result

  def arrangements(patterns, towels) do    
    {longest, count} = Enum.max_by(patterns, fn {pattern, _count} -> String.length(pattern) end)
    patterns = Map.delete(patterns, longest)

    patterns =
      towels
      |> Enum.map(fn towel ->
        case longest do
          ^towel <> remaining -> {remaining, count}
          _ -> nil
        end
      end)
      |> Enum.reject(&is_nil/1)
      |> Map.new()
      |> Map.merge(patterns, fn _key, count1, count2 -> count1 + count2 end)
    
    arrangements(patterns, towels)
  end
end

# Parse
{towels, patterns} = Day19.parse(puzzle_input)

# Part 1
Enum.count(patterns, &Day19.possible?(&1, towels))

# Part 2
patterns
|> Enum.map(&Day19.arrangements(&1, towels))
|> Enum.sum()

My straightforward solution for part 1 didn’t terminate for my real input.

I then implemented a trie (prefix tree). That took me a while, but it still didn’t terminate.

I then added memoization using the process dictionary. That worked.

After solving part 2, I cleaned up my code. I tried to use Memoize for memoization but the time increased to 31 seconds. I did some attempts to make Memoize use only the first argument of my count function, but I couldn’t make it work. In the end, I rewrote my count function to take an explicit memo argument.

The combined runtime for both parts and the examples is 0.4 seconds.

https://github.com/bjorng/advent-of-code/blob/main/2024/day19/lib/day19.ex

Mine takes about 50ms per part, using in-process memoization since mixing designs does not seem to bring much.

defmodule AdventOfCode.Solution.Year2024.Day19 do
  use AdventOfCode.Solution.SharedParse

  @impl true
  def parse(input),
    do: String.split(input, "\n", trim: true) |> then(&{String.split(hd(&1), ", "), tl(&1)})

  def part1({patterns, designs}), do: run(patterns, designs) |> Enum.count(&(&1 > 0))

  def part2({patterns, designs}), do: run(patterns, designs) |> Enum.sum()

  defp run(patterns, designs) do
    Task.async_stream(designs, &ways(&1, patterns), ordered: false)
    |> Stream.map(fn {:ok, n} -> n end)
  end

  defp ways("", _), do: 1

  defp ways(design, patterns) do
    with nil <- Process.get(design) do
      Enum.reduce(patterns, 0, fn pattern, total ->
        case design do
          <<^pattern::binary, rest::binary>> -> ways(rest, patterns) + total
          _ -> total
        end
      end)
      |> tap(&Process.put(design, &1))
    end
  end
end

I compiled a big regex for part 1. It is slow and does not work for part 2 but it was trivial to implement. Now I have to find another kind of solution to be able to do part 2 and probably part 1 faster.

{towels, designs} = puzzle_input
|> String.split("\n")
|> then(fn [towels, _ | designs] -> {String.split(towels, ", "), designs} end)

{:ok, regex} = towels |> Enum.join("|") |> then(fn x -> "^(#{x})+$" end) |> Regex.compile()

designs
|> Enum.reduce(0, fn design, n -> if String.match?(design, regex), do: n+1, else: n end)
|> IO.inspect(label: "Part 1")

hah, that’s a clever idea!

Part 1 was pretty straight forward. Part 2 I figured may take memoization, but I tried brute force anyway, and it did not terminate. So then I tried adding a “already solved” map and carry it along during the recursion, but I got all twisted in my thinking on this. So I converted it to a global variable, and that was easier to reason about.

https://github.com/rvnash/aoc2024/blob/main/lib/d19.ex

I really should figure out how to do this in a recursive functional way, rather than relying on global state.