[noxvilleza]

The same is true with part 2 of problem 8 and problem 21 which both are generally much harder problems which are made easier by carefully constructed test cases. I also find it somewhat annoying, but par for the course with advent given the same test data for part 1 & 2; and the fact that you actually see the only test case -- it's not hidden test cases like in other programming competitions.

[flurie]

I'm behind this year, so I haven't looked at any postmortems, but I found an interesting solution to problem 8 part 2[1] after watching the brute force methods stall out. Could you explain what you mean by carefully constructed test cases?

[1] https://github.com/flurie/aoc-rust/blob/main/src/bin/08.rs#L...

[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!

[noxvilleza]

So in Question 8 part 2 you had multiple cycles through a graph. You started on all "A" nodes and you had to find the first time at which you were entirely on "Z" nodes.

The intended solution was seemingly to calculate the length of the cycle (as in, until you were on a "Z" node) for each starting node separately. Once you'd done this, you could find the LCM of these cycle lengths to find the overall period of the cycle (~10^13).

This solution might not work if your cycles weren't constant length -- for example imagine when walking your graph you found your i_th Z-node after {6, 7, 6, 7, 6, 7, 6, 7 ...} steps; or perhaps {6, 7, 7, 7, ...}. In the test data, this didn't occur - it was always {n, n, n, n, ...}.

I can give another example perhaps - consider you're asked to find the last 3 digits of 2^n for n >= 1. You start off calculating: 002, 004, 008, ... eventually you get to 2^103 which ends in 008. This means that the cycle length would be {103, 101, 101, 101, 101, ...} since it'll never get back to 002 or 004. Solving this is a bit more difficult than the constant cycle lengths, since it's not a simple LCM.

[harshreality]

Is there any theorem that puts limits on how irregular the cycles can be in a general case of tape length L with N options corresponding to N outputs from each graph node?

What has to be constant is the cycle length for (node, tape instruction #) pairs, because all the state to determine every future step is based on the current node and tape position; if both are the same, the path will be the same as before. I think, at least without advanced math, the only thing to rely on for "true" loops is identical pairs of (instr #, node), not just instr # or tape steps or node individually.

[noxvilleza]

I haven't spent that much time thinking about it, but my guess is that there may or may not be:

* a "tail" -- some initial part of the path before you get into a true cycle (like the 002, 004 in the example above)

* an inner repeating cycle before you reach a node you've seen before.

In the case given |t| = 0 and |c| = 1, but it's easy to construct a more complex example with nodes (A, B, C, D), edges (A->B, B->C, C->D, D->B), and 'ending nodes' being B and D. In this case left and right paths go to the same node. This case would have a tail of length 1, and then the inner cycles would be of length {2, 1, 2, 1 ...}.

As a result, valid 'ending states' (Z-nodes) for this graph would be after {1, 3, 4, 6, 7, 9, 10, ...} steps.

[harshreality]

You can have an inner seemingly-repeating cycle by node, but not by (node, tape instr #) pair.

Initial tails are something they should've done, which would've foiled the naive "find the cycle lengths and use lcm" approach.

[flurie]

I can see the case of an aperiodic first cycle length, but given that each vertex in the graph created by the input -> output nodes of the traversal path has only one outgoing edge, is it possible for the cyclic graph from a1 to some z1 to have an inconsistent length? And is there ever going to be some z2 for which the aperiodic cycle length from a1 to either z1 or z2 results in a better answer to the problem given that the periodic cycle length of a1 to z1 is shorter than the cycle length of a1 to z2? Please forgive me if I am not using the correct graph theory terms.