3 ms·
What was the thought process that led to this solution? Did day 24 remind you of some other problem you'd seen before?
by atroche 5y ago
What was the thought process that led to this solution? Did day 24 remind you of some other problem you'd seen before?
- reitzensteinm 5y agoMy first instinct was to vectorize the interpreter, amortizing the cost across searching many possibilities in parallel. But 9^14 is still a huge search space even when efficiently implemented on a CPU, and indeed the compile to Rust brute force version I built later isn't faster than this one at finding the lowest/highest answers. Then I started to think about pruning the search space with early out. If you squint, there's a similarity here to bloom filters. It gives you two possible answers: definitely no, or possibly yes. I was expecting to run in to issues where the state grew too large, but that turned out never to be the case. An alternate way to approach it would have been with dynamic programming, but I didn't feel like that would be as much fun.