Part 1, no problem. Part 2… Ended up being a complete rewrite. Once again, recursion is giving me a headache.
I’m impressed that you found a recursive solution. I started down a similar path initially but viewing it more like an automata problem where the simulation might eventually add a patterned number of stones every step. I couldn’t find any obvious patterns though so I looked at other properties of the input and fell into the (probably) more common solution of compressing the state and simulating large numbers of stones simultaneously instead. I think we’ve had nearly identical optimization problems in past years.
Nice to see I’m not the only one who lost time trying to recurse. It turns out there are some very nice recursive solutions (the Reddit solutions use a cached DFS; one solution I examined caches the stone number and the depth at whcih it was found).
If I understand what @jcmoyer means by “compressing the state and simulating large numbers of stones” then I think he and I did the same thing. I’d phrase it as, I tracked the numbers on the stones with the numbers of those stones; so that the list 4 0 4 8 2 0 2 4 is instead the mapping 0 ↦ 2, 2 ↦ 2, 4 ↦ 3, 8 ↦ 1.
1 Like