Day 8: Haunted Wasteland
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- Code block support is not fully rolled out yet but likely will be in the middle of the event. Try to share solutions as both code blocks and using something such as https://topaz.github.io/paste/ , pastebin, or github (code blocks to future proof it for when 0.19 comes out and since code blocks currently function in some apps and some instances as well if they are running a 0.19 beta)
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
Personally, I’m not a fan of requiring analysis of the individualized input to reach the correct (sufficiently efficient) solution for part 2. Or maybe I’m just resentful because I feel like I’ve been duped after writing an generalized-to-the-puzzle-description-but-insufficiently-efficient solution. 😔
These quantum ghosts need to come back down to reality.
Yeah I got annoyed too. Because this is not implied in the problem statement and it definitely doesn’t hold up in general…
Perhaps there’s a mathematical way to prove that this assumption will actually always happen despite the input? I wanted to test this assumption, and edited the map and randomly changes the destinations for keys ending in Z, and it looks like the matches are still at consistent intervals. Is it possible to have an input map which breaks the assumption?
I can prove the opposite for you. The assumption that Gobbel2000 describes is wrong in general. For example, take
L A -> B, X B -> C, X C -> Z, X Z -> C, X X -> X, X
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:
L A -> 1Z, X 1Z -> 2Z, X 2Z -> A, X X -> X, X
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.
This assumption doesn’t hold in general, however you can construct an efficient algorithm, even if it doesn’t hold.
First, let’s show that a cycle always exists. Let
I
be the size of the instruction string, andN
be the number of nodes. Since the number of states for each ghost is at mostI*N
, after a finite number of steps, the ghost will go into one of the previous states and cycle forever. Let’s say that the cycle length isc
, and aftera+c
steps the ghost has entered the same state it was aftera
steps.Let’s assume[^1] that during the first
a+c
steps the ghost has only once encounter an end state (a node ending with ‘Z’), specifically aftere
states. Ife >= a
, this means that the ghost will encounter the end state also aftere + c
ande + 2c
and so on, or for every number of stepss > e
such thats = e (mod c)
. The assumption you formulated meanse = 0 (mod c)
, ore = c
.Now, consider the
K
ghosts that are travelling simultaneously. If aftern
steps all ghosts have reached the end state, this means thatn = e_i (mod c_i)
for all ghostsi
(1 <= i <= K
). According to the Chinese remainder theorem, there is a solution if and only ife_1 = e_2 = ... = e_K (mod gcd(c_1, c_2, ... c_K))
. If the assumption you formulated holds, thene_i = 0 (mod c_i)
, solcm(c_1, ... c_K)
works as a solution. If it doesn’t, you can still findn
, but it will be a bit more tricky (which is probably why the authors of the challenge madee = c
always).[^1] – this is another assumption you’ve implicitly made, and that happens to hold for all the inputs. However, if this assumption doesn’t hold, we can check all possible combination of end state positions.
re [^1]: yeah, but that may explode the runtime again. Do you have any idea if this is possible to solve without brute forcing the combinations?
I don’t think it will explode the runtime. If you have multiple feasible values for
e
per ghost, you just need to find a combination ofe_i
such thate_1 = e_2 = ... = e_K (mod gcd(c_1, c_2, ... c_K))
, which is just an intersection ofK
sets of at mostI*N
elements.I crafted a simple counter-example (single letters for brevity). The way the sequence goes totally depends on the instructions, and we don’t have any guarantees on that. It could be anything. Of course, looking at the input data we could find what the instructions are, but the assumption doesn’t hold in general.
Here the distance of Z cycling back into itself could be 2 or 4, depending on what the instruction string is doing.
For better or worse, this is to be expected for Advent of Code.
I kind of agree, props for getting a general solution. I actually realized this issue only after I got both stars and didn’t feel like changing it again.