20
๐ - 2023 DAY 8 SOLUTIONS -๐
(programming.dev)
An unofficial home for the advent of code community on programming.dev!
Advent of Code is an annual Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like.
Solution Threads
M | T | W | T | F | S | S |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 |
Icon base by Lorc under CC BY 3.0 with modifications to add a gradient
console.log('Hello World')
I can prove the opposite for you. The assumption that Gobbel2000 describes is wrong in general. For example, take
the first Z is reached after 3 steps, but then every cycle only takes 2 steps.
The matches are still at consistent intervals, but you can easily find a counterexample for that as well:
now the intervals will be 2, 1, 2, 1, ...
However, it is easy to prove that there will be a loop of finite length, and that the intervals will behave somewhat nicely:
Identify a "position" by a node you are at, and your current index in the LRL instruction sequence. If you ever repeat a position P, you will repeat the exact path away from the position you took the last time, and the last time you later reached P, so you will keep reaching P again and again. There are finitely many positions, so you can't keep not repeating any forever, you will run out.
Walking in circles along this loop you eventually find yourself in, the intervals between Zs you see will definitely be a repeating sequence (as you will keep seeing not just same-length intervals, but in fact the exact same paths between Zs).
So in total, you will see some finite list of prefix-intervals, and then a repeating cycle of loop-intervals. I have no idea if this can be exploited to compute the answer efficiently, but see my solution-comment for something that only assumes that only one Z will be encountered each cycle.
Thank you for this, it really helped me understand this more.