[rst]

It's easy to construct inputs for which the correct solution would not be the LCM of the cycle lengths. (Just take the input you got, and insert a few extra steps between the "start" point for one of the "ghosts" and the point where it enters its otherwise unaltered cycle.)

A more general solution is possible -- but it does require a trick that people may not be aware of unless they've studied a little number theory.

[penteract]

It gets even more interesting if you start worrying about ghosts that could finish at multiple points within each cycle. There are potentially too many combinations to try out each one individually.

[noxvilleza]

Would you use Chinese remainder theory on all possible configurations of the cycles, or something else completely?

[qsort]

I actually wrote the code to solve it in full generality (https://github.com/edoannunziata/jardin/blob/master/misc/Aoc...) -- CRT is the idea but it's actually the "generalized" case of CRT, because you could have moduli that are not coprime. So you have to use the CRT "in reverse" to break each linear congruence into its components (using the fact that \mathbb{Z}_m \times \mathbb{Z}_n \cong \mathbb{Z}_{mn} \iff \gcd(m, n) = 1) and then use the CRT again to find the answer.

Annoying to code, but I've done it a thousand times by hand for math competitions, so it's kind of carved into my skull.

There might be multiple cases, but I don't think there's anything better (please let me know if there is, I'm very interested) -- as a matter of fact, an instance of the original problem can be used to encode an instance of a system of linear congruences, so finding a better algorithm for the latter would imply a better algorithm for the former.

[penteract]

It's possible to answer "find the minimum n such that n%a is in s1 and n%b is in s2, assuming a and b are coprime" in runtime around O(n1+log(n1)*n2) where n1 is the size of s1 and n2 is the size of s2.

n1*n2 can get at least as big as a*b/8 without a naive linear search being guaranteed to be fast, so this roughly square roots the runtime of 'CRT on all pairs' if n1 is close to n2.

Here's the code, sorry it's not as well commented as yours, and I haven't integrated it into a solution to day 8.

https://github.com/penteract/adventofcode/blob/master/utils/... .

For more than 2 moduli, the best I can think of is to separate them into 2 roughly equal parts, generate the full lists of allowed remainders for each part, then use this algorithm to combine the parts. There may be better things you can do here (and perhaps you can show that for large sets of allowed remainders across enough different moduli, the solutions are spread out evenly enough there's one you can find by naive linear search).

Dealing with non-coprime moduli is left as an exercise to the reader :).

[qsort]

Wow, thanks! I'll check it out.

[noxvilleza]

Great, thanks!