A modern programming language that makes developers happier.

kotlinlang

Are there any good general solutions for day 8 part 2?

I saw that the LCM approach seems to be very popular, but to me it seems to rely on each ghost only visiting the same destination over and over (which possibly other destinations before entering a loop), which may be how the puzzle is generated, but not required by the description.

Am I seeing this incorrectly? If not: Are there good solutions that would allow ghosts to cycle multiple destinations?

the ghost always visits the same positions - there are only a finite number of states possible, so eventually they cycle

we also have exactly 6 starting A's and exactly 6 ending Z's, so we're fairly limited in how many times Z will come up during the cycle

and since it's limited, to handle multiple Z's coming up during a cycle at different offsets, we could just compute the solution for every combination of Z's and take the minimum

You are right. That could easily be done. Thank you!

Assuming that the different cycles were shifted against each other, you would not only determine the joint period (the LCM mentioned above), but also the smallest solution of the Chinese remainder theorem (the point, when all 6 cycles are simultaneously at Z).  The good news is (and I did check that), that the first time every cycle individually reaches Z and their respective period length coincide, meaning that the full solution is just the LCM.

I think there is no inherent proof in the question itself that the LCM would works, you just have to observe the sequence of data for each path starting A and ending Z to notice that the cycles have the properties to make make the solution LCM. 

IMG_3406.png

&gt;  we also have exactly 6 starting A's and exactly 6 ending Z's, so we're fairly limited in how many times Z will come up during the cycle
In principle the same Z can occur multiple/many times before the cycle repeats. Of course it's still limited by the total state space, but I suppose at some point it would be more efficient to manually iterate through the Z-Z intervals, rather than calculate the chinese remainder theorem for all combinations, because that grows very quickly (roughly O(n^6)?).