Serial Serious Replyer Advent of Code is an annual Christmas themed coding challenge that runs from December 1st until christmas. Each day the coding problems get progressively harder. We have a leaderboard and pretty good turnout, so feel free to hop in at any time and show your stuff!
Whether you have a single line monstrosity or a beautiful phone book sized stack of OOP code, you can export it in a nice little image for sharing at https://carbon.vercel.app
What did you think about today's problem?
Our Code is 2416137-393b284c (No need to share your profile, you have the option to join anonymously if you don't want us to see your github)
Jump in the discussion.
No email address required.
Easy and fun
I wonder how long it takes without using lcm
Jump in the discussion.
No email address required.
I considered doing this but I didn't think it would work because there's multiple results ending in Z.
Is there only one possible Z ending per value? How do you guarantee periodicity?
Jump in the discussion.
No email address required.
You can't guarantee it in general, but the guy who writes the problems tailored all the inputs to go around in circles. All the periods in my input were between 10 and 20 thousand and always arrived at the same endpoint. It was clearly very intentional, like I think he imagined people would try to brute force it (which seriously doesn't work unless you want to wait for a very long time) then they would have to put some debug output statements in their loop, which is how I eventually figured out what the heck was going on.
Jump in the discussion.
No email address required.
More options
Context
I ran the loops on real data and checked that they all are multiples of the command sequence length. They are all prime numbers (multiplied by that) too, by the way.
Looking at the data, and not even with a naked eye, is an integral part of some of the AoC puzzles.
Jump in the discussion.
No email address required.
In this case it seems less like looking at the data and more like intuitively guessing "what might they have done?" and checking if your hunch was right.
Makes sense though, I'll have to try to be a little more wary of that going forwards and just listen to my intuition
Jump in the discussion.
No email address required.
I'd call it a confirmed educated guess. It's not like I assumed that there would be no Z's in the middle of each full cycle and proceeded to implement the full algorithm and checked if the final answer is correct. I actually printed out the cycle lengths divided by the command sequence length first. They were cleanly divisible resulting in prime numbers.
Jump in the discussion.
No email address required.
More options
Context
More options
Context
Well I'm disappointed, my solution doesn't assume complete loops, which makes things a lot more complicated.
Jump in the discussion.
No email address required.
More options
Context
More options
Context
Consider each starting point Sn. Let Sn(k) be the kth successor of Sn following the directions. (Whichever node you are on after following k many directions)
Assuming the problem has a solution all Sn have an m such that Sn(m) = ZZZ. Call it Xn.
If for some An only one succesor = ZZZ thn trivially the answer is Xn. Otherwise there must be a cycle in the succesors of An starting at the Xnth succesor (the succesor that equals ZZZ). Let the length of this cycle be Cn.
If a solution exists it is of the form Xn + Cn * k where k is some positive integer. (These are the only points the succesors of An = ZZZ). Rephrase this as SOLUTION = Xn mod Cn. Im fudging this a bit since Xn can be greater than Cn but that can be repaired later.
We have one of these modulus equations for each starting point. SOLUTION = X1 mod C1 = X2 mod C2....... this equation is solvable with Chinese Remainder Theorum.
In this case the data is aranged such that the CR solution reduces into finding an LCM.
Wait, the succesors can pass through ZZZ multiple times per cycle frick
Jump in the discussion.
No email address required.
More options
Context
Feed in each A-value, then feed back in each resulting Z-value:
This
guaranteesstrongly suggests the loops are simple and the lcm is the solution. If any Z-value found a different Z-value, or had a different number of steps, you'd be dealing with linear congruences, but that's too much of a pain in the ass for day 8.If you want to prove the loops are simple, check that every loop length is a multiple of the LRLRLRLLR sequence length. But that's way too much formality for AoC, you've gotta go with your intuition.
Jump in the discussion.
No email address required.
More options
Context
More options
Context
It would take 21,003,205,388,413 loops.
Jump in the discussion.
No email address required.
More options
Context
I let it run for like 5 minutes at one point. It wasn't even close to being done. I think it might take a couple hours.
Jump in the discussion.
No email address required.
More options
Context
More options
Context