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
