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.

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")

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

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.

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

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