My 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.
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.