:date: 2023-12-08 12:00
Ok, Part One was easy enough to brute force with simple Python.
And Part Two seemed ok - I got the test data working pretty quickly. But once it ran on the real data, it didn't end quickly. It got up to huge numbers and submitting them confirmed I was still too low. I believe this is a correct algorithm, but not sufficiently efficient for the actual data. Clicking on the Reddit link in the puzzle, I saw a meme that mentioned LCM and I realized the effective solution was looking for cycles of the rules and then trying to find where those cycles intersect using least common multiple. I was not feeling like generating a LCM algorithm so I asked ChatGPT for one and it delivered just fine. I'm kind of astonished that I got the right answer (around 10.6 trillion) immediately the first time I tried this strategy. Not only that but I was able to get the answer in 37ms.
What bothered me is the reason it wasn't obvious to use LCM based on a system of cycles. The instructions (part A) say, "If you run out of left/right instructions, repeat the whole sequence of instructions as necessary..." Ok, that's fine. On the sample input for part A, the ZZZ end condition has targets of "ZZZ/ZZZ" meaning it doesn't matter what the left/right instruction repeats as - you're conspicuously stuck there. So right away I'm tipped off to the fact that there is no special help for cycling through the items. They can in fact be unhelpfully intransigent.
The part B instructions say, "If only some of the nodes you're on end with Z, they act like any other node and you continue as normal." Ok, that's fine. But why would we suppose that "continuing as normal" - where "normal" is quite a messy path - would mean the same thing as "neatly returning to the first step ensuring a repeating cycle"?
So let's consider an example. If I arrive at "ZZZ" but the other threads are not done, the left/right targets are "MTL/KJN". But searching for where "MTL" shows up, we find it in "AAA" - the left/right targets for "AAA" are "KNJ/MTL", the reverse of the "ZZZ". This makes me think that the beginning and end of the left/right string must be different. This is true in all the examples, but seems like a bad thing to assume.
Let me put it this way: my brute force algorithm is too slow to ever finish, but if it could, it would at least produce the correct answer for any input structured as described. The algorithm I actually used to get the accepted answer seems to have failure modes and depends on the data being neatly structured for success. Assuming helpful data is bad, but so is checking for helpful data by hand if you need a scalable and robust solution.