I ended up using the same technique. My plan A was to sleep on it and hope to wake up with a general solution - that didn't work. :). Thanks for this video!
Thank you so much for these videos. After solving each problem I watch these to see a much more efficient way of doing it. Looks like cycle lengths are always prime so could we just take the product? [again another wild assumption…]
The generalised problem has no solution guaranteed to run in short time. This is a theorem in computation theory: Halting Problem, etc etc. Basically the input defines a general computational circuit, and there's no general algorithm T(X) to tell how long a circuit (X) will run for (if there were, you could write a modified algorithm T' which is guaranteed to run for longer, turn T' into a circuit C', apply it to itself, reductio ad absurdum, see your computational theory lecture notes for details). You can assert that this particular problem decomposes in a regular way, and that the decomposed parts behave in particular ways (in particular, that each sub-circuit c generates a rising edge after N_c button pushes and then thereafter on every N_c button pushes, and that each time it generates a rising edge, it does so on the same number of clock ticks after the button push), and then just LCM the N_c values. It's a lot like the ghosts problem in several ways. For instance, it disdains to rely on the Chinese Remainder Theorem.
For part 2, one possibility that your approach does not cover is that sometimes when the button is pushed, the feed module might not receive any pulses from one or more of its input modules, so the memory of feed might stay "hi" for several rounds. Rather than looking at when a high pulse was sent to feed, I checked when the memory of feed changed for each input. This showed that on the same button push that an input sent a high pulse, it also sent a low pulse afterwards, thus proving that all the high pulses must arrive on the same button push.
Only 'sort of' generalization for part 2 is to start from the *rx* node and look back for increasing depth as long as all nodes you find on that depth are type '&'. The list you end up with then is your 'magic' node list to check the cycle length for. That's what I did visually first by drawing out the nodes, starting from *rx* . For me, the *%* nodes started after depth 3, giving me 4 usable magic nodes
It looks like the input is structured the same for everyone - rx is the output, one “combinator” node that feeds rx and four nodes that feed combinator (with % inputs)
Thanks for all the cool explanation videos btw.
I ended up using the same technique. My plan A was to sleep on it and hope to wake up with a general solution - that didn't work. :). Thanks for this video!
Thank you so much for these videos. After solving each problem I watch these to see a much more efficient way of doing it.
Looks like cycle lengths are always prime so could we just take the product? [again another wild assumption…]
That seems to be true, but that's a bit risky of an assumption to make, and doing LCM isn't that much more inconvenient.
A minor note on math.lcm: it takes *ints, so math.lcm(*cycle_lengths.values()) would work, no need for the loop.
The generalised problem has no solution guaranteed to run in short time. This is a theorem in computation theory: Halting Problem, etc etc. Basically the input defines a general computational circuit, and there's no general algorithm T(X) to tell how long a circuit (X) will run for (if there were, you could write a modified algorithm T' which is guaranteed to run for longer, turn T' into a circuit C', apply it to itself, reductio ad absurdum, see your computational theory lecture notes for details).
You can assert that this particular problem decomposes in a regular way, and that the decomposed parts behave in particular ways (in particular, that each sub-circuit c generates a rising edge after N_c button pushes and then thereafter on every N_c button pushes, and that each time it generates a rising edge, it does so on the same number of clock ticks after the button push), and then just LCM the N_c values. It's a lot like the ghosts problem in several ways. For instance, it disdains to rely on the Chinese Remainder Theorem.
For this problem (unlike the ghosts problem), it wasn't even necessary to LCM.
For part 2, one possibility that your approach does not cover is that sometimes when the button is pushed, the feed module might not receive any pulses from one or more of its input modules, so the memory of feed might stay "hi" for several rounds. Rather than looking at when a high pulse was sent to feed, I checked when the memory of feed changed for each input. This showed that on the same button push that an input sent a high pulse, it also sent a low pulse afterwards, thus proving that all the high pulses must arrive on the same button push.
Only 'sort of' generalization for part 2 is to start from the *rx* node and look back for increasing depth as long as all nodes you find on that depth are type '&'. The list you end up with then is your 'magic' node list to check the cycle length for. That's what I did visually first by drawing out the nodes, starting from *rx* . For me, the *%* nodes started after depth 3, giving me 4 usable magic nodes
It looks like the input is structured the same for everyone - rx is the output, one “combinator” node that feeds rx and four nodes that feed combinator (with % inputs)
But yeah, I guess you’ve described a general solution.
@@Gusto20000 a general approach at least. Whether it leads to a solution depends on how many magic nodes you find.
Also analyzed the input data and solved it this way 😂. Would be interested if there is a general algorithmic solution for the problem.
crazy
Why does my code have more comments than code T_T