Yes it can. In the example for part1, ZZZ points to itself in both direction, which would cancel out the cycle once it's reached. But the input was made so that the offset was always the same length as the cycle.
math.lcm actually does exist but only since Python 3.9. And (as I annoyingly found out today) it only takes integers as separate arguments so you need to splat them. Can you even solve this problem in general with the CRT though? In theory, you can cycle through multiple Z states from a start, with different lengths between them. I guess it wouldn't change the cycle length but you'd have to compute it by checking when you've seen the same node again, not any node with Z. Or I guess really, the same node at the same instruction step. And then you could check all possible offsets that lead to a Z node in the cycle (for every different instruction step you see them at). So I guess still solvable using the CRT but definitely would be more complicated. Kinda annoying, so far, I always expected part two to actually require something harder than brute-force and the first time it actually happens, I was sure it couldn't possibly already be CRT and didn't check it for a while.
Yeah, we always have a cycle for each xxA node, as the number of states (defined by (node, i) where i is position in the dir instructions) is finite, so eventually we'll reach the same state, but such cycle can contain multiple exists (or the same exit multiple times). So in general for xxA entry we have the same cycle length but multiple offsets. So we could do a cartesian of all offsets and then calculate CRT for all combinations - and finally get the lowest one. But complexity of this general solution depends of the number of exit nodes on each cycle. In the data we all got it was just single exit in the whole cycle, and even better all offsets were 0 (it's not like @Jonathan said that from Z we go to A - as then the offset would be -1 - so the starting node is not at in the cycle) - so we got CRT in trivial form, reduced to LCM. And yes - same here, two days ago I was sure brute force won't work and didn't even try it - while today I was pretty sure CRT won't work and also didn't try it ;-)
In a fully generic input I don't even think directly applying the Chinese remainder theorem can give you the optimal answer... like suppose if the cycle went like 100 11Z 150 22Z 300 33Z 400 11Z and so on... yes it cycles back to 11Z on the 100 + 300k th iteration, and the Chinese remainder theorem can handle this, but the optimal solution does not necessarily stop at 11Z.
@@s1nc3r1ty Technically the number of steps also has to be a multiple of the number of steps in your input sequence. I don't know if this is strong enough to imply that But if this condition is also satisfied, then yes LCM works :)
good point. I guess really we have conditions like "t = a1 % b or a2 % b or a3 % b". I don't know how to solve this efficiently. (although if there are only 6 starting points, you can just try all possibilities)
Yeah, it was relief to discover that input has simple cycles w/o offsets. But, tbh, i think it would be too hard for AoC to have more complex loops. PS: WolframAlpha helped a bit with LCM :)
I wasn't expecting complex loops - but I *was* expecting the offsets to not be precisely the same from the start - come on! Give us a little linear algebra!
CRT has been required for at least one or two days of AoC before, so it's not exactly too hard for AoC. Honestly, it's probably still quite far away from the hardest problems. But definitely not on day 8 ofc.
It is not true, that after Z we will back to the A. But yes, the input is nice, because lenght of the cycle is the same as the lenght from A to Z Upd: yeah, you said it later in a video, sry :D
I was too stupid to understand the full complexity of the problem and thought LCM would work for all inputs. Worked this time, but I got lucky
POS = NP
So close to solving mathematics.
In this part, you need to use "Generalization to non-coprime moduli" Chinese remainder theorem. That should work.
I'm not sure that with the common cycle input string it is possible to not have an offset same as the cycle length for all the ghosts
Yes it can. In the example for part1, ZZZ points to itself in both direction, which would cancel out the cycle once it's reached. But the input was made so that the offset was always the same length as the cycle.
math.lcm actually does exist but only since Python 3.9. And (as I annoyingly found out today) it only takes integers as separate arguments so you need to splat them.
Can you even solve this problem in general with the CRT though? In theory, you can cycle through multiple Z states from a start, with different lengths between them. I guess it wouldn't change the cycle length but you'd have to compute it by checking when you've seen the same node again, not any node with Z. Or I guess really, the same node at the same instruction step. And then you could check all possible offsets that lead to a Z node in the cycle (for every different instruction step you see them at). So I guess still solvable using the CRT but definitely would be more complicated.
Kinda annoying, so far, I always expected part two to actually require something harder than brute-force and the first time it actually happens, I was sure it couldn't possibly already be CRT and didn't check it for a while.
Yeah, we always have a cycle for each xxA node, as the number of states (defined by (node, i) where i is position in the dir instructions) is finite, so eventually we'll reach the same state, but such cycle can contain multiple exists (or the same exit multiple times). So in general for xxA entry we have the same cycle length but multiple offsets. So we could do a cartesian of all offsets and then calculate CRT for all combinations - and finally get the lowest one. But complexity of this general solution depends of the number of exit nodes on each cycle.
In the data we all got it was just single exit in the whole cycle, and even better all offsets were 0 (it's not like @Jonathan said that from Z we go to A - as then the offset would be -1 - so the starting node is not at in the cycle) - so we got CRT in trivial form, reduced to LCM.
And yes - same here, two days ago I was sure brute force won't work and didn't even try it - while today I was pretty sure CRT won't work and also didn't try it ;-)
Oh, and my solution isn't complete either, as it doesn't account for exits you could encounter before getting onto cycle path.
In a fully generic input I don't even think directly applying the Chinese remainder theorem can give you the optimal answer... like suppose if the cycle went like
100 11Z
150 22Z
300 33Z
400 11Z
and so on... yes it cycles back to 11Z on the 100 + 300k th iteration, and the Chinese remainder theorem can handle this, but the optimal solution does not necessarily stop at 11Z.
With my tree I can check that the number of steps "**Z" -> "**Z" is equal to the steps "**A" -> "**Z". Hence LCM works?
@@s1nc3r1ty Technically the number of steps also has to be a multiple of the number of steps in your input sequence. I don't know if this is strong enough to imply that
But if this condition is also satisfied, then yes LCM works :)
good point. I guess really we have conditions like "t = a1 % b or a2 % b or a3 % b". I don't know how to solve this efficiently. (although if there are only 6 starting points, you can just try all possibilities)
background water is so relaxing hahaha
Are you doing this in the bath? I hear water.
I think he has a game open in the background 🤔 there's desktop audio according to his OBS
@@CAG2 Na definitely floating in the lagoon. ;)
Either background sounds from a game (I wonder which one) or calming white noise.
background sounds from Warcraft 3
Yeah, it was relief to discover that input has simple cycles w/o offsets. But, tbh, i think it would be too hard for AoC to have more complex loops.
PS: WolframAlpha helped a bit with LCM :)
I wasn't expecting complex loops - but I *was* expecting the offsets to not be precisely the same from the start - come on! Give us a little linear algebra!
CRT has been required for at least one or two days of AoC before, so it's not exactly too hard for AoC. Honestly, it's probably still quite far away from the hardest problems. But definitely not on day 8 ofc.
It is not true, that after Z we will back to the A. But yes, the input is nice, because lenght of the cycle is the same as the lenght from A to Z
Upd: yeah, you said it later in a video, sry :D