it is "hard" to do math in roc without autoscasting the number types :thinking:
it might be a matter of getting used to it, but doing this AoC Day 8 part 2, I have spent most of the time trying to do basic aritmetics in roc and fighting the type system...

What I don't like for today is, that lcm seems to be the only viable solution, but in theory there can be inputs, that are not solvable this way. Looks like all are, but there is nothing in the text gving you a hint that all routes are circles with only one target.

I did not like day8. The input had some characteristics, that where not in the description of the day.

Each start has it's own end and the end comes always at the same ratio. So if XXA leads to XXZafter 5 steps, then it will never go to YYZ and the next XXZ-nodes will be after 10, 15, 20 steps. This is how it is solved, but I could not read this contain in the description. For example, here is an input, that does not hold the constrain:

LR

11A = (11D, XXX)
11B = (XXX, 11C)
11C = (11D, XXX)
11D = (XXX, 11Z)
11Z = (11B, XXX)

I was thinking all day about the problem until I analyzed the actual input and found the constrains.

But maybe day8 was not for humans to solve, but for ghosts :wink:

I figured the dictionary lookup was the slowest part so I played around with different types for the key. I found U16 was pretty quick so I converted each of the 3 characters into a unique ID and used that as the key.

I believe my solution works for all possible inputs as described in the puzzle. It takes about 6 seconds on my input.

After my naïve solution for part 2 was taking forever, I assumed there were hundreds of start nodes in the input and started optimizing the traversal. I came up with an algorithm to compute the destiny of every node in the input (including non-start nodes) in O(nodes * directions) time. Then once I viewed the output so far and saw that there were only six start nodes and they each only encountered one end node in their cycles, I was pretty disappointed. I still didn't realize that the cycle length was equal to the exit distance, so I implemented a general solution for satisfying the congruence restrictions mod the cycle length using an implementation of division mod the cycle length. This is actually the most explosive part of the algorithm because it would take exponential time in the number of start nodes if each start node actually hit an end node more than once per cycle.