this post was submitted on 08 Dec 2023
21 points (92.0% liked)

Advent Of Code

772 readers
8 users here now

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.

AoC 2023

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

Rules/Guidelines

Relevant Communities

Relevant Links

Credits

Icon base by Lorc under CC BY 3.0 with modifications to add a gradient

console.log('Hello World')

founded 1 year ago
MODERATORS
 

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

you are viewing a single comment's thread
view the rest of the comments
[โ€“] [email protected] 13 points 11 months ago* (last edited 11 months ago) (4 children)

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.

[โ€“] [email protected] 8 points 11 months ago

Yeah I got annoyed too. Because this is not implied in the problem statement and it definitely doesn't hold up in general...

[โ€“] [email protected] 2 points 11 months ago

For better or worse, this is to be expected for Advent of Code.

[โ€“] [email protected] 2 points 11 months ago (3 children)

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?

[โ€“] cvttsd2si 6 points 11 months ago* (last edited 11 months ago) (1 children)

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.

[โ€“] [email protected] 2 points 11 months ago

Thank you for this, it really helped me understand this more.

[โ€“] [email protected] 2 points 11 months ago

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.

A = (B, X)
B = (C, X)
C = (X, Z)
Z = (A, C)
X = (X, X)

L L R L L L R R R -> A B C Z A B C Z C Z
L L R R R L L L R -> A B C Z C Z A B C Z

Here the distance of Z cycling back into itself could be 2 or 4, depending on what the instruction string is doing.

[โ€“] [email protected] 2 points 11 months ago (1 children)

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, and N be the number of nodes. Since the number of states for each ghost is at most I*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 is c, and after a+c steps the ghost has entered the same state it was after a 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 after e states. If e >= a, this means that the ghost will encounter the end state also after e + c and e + 2c and so on, or for every number of steps s > e such that s = e (mod c). The assumption you formulated means e = 0 (mod c), or e = c.

Now, consider the K ghosts that are travelling simultaneously. If after n steps all ghosts have reached the end state, this means that n = e_i (mod c_i) for all ghosts i (1 <= i <= K). According to the Chinese remainder theorem, there is a solution if and only if e_1 = e_2 = ... = e_K (mod gcd(c_1, c_2, ... c_K)). If the assumption you formulated holds, then e_i = 0 (mod c_i), so lcm(c_1, ... c_K) works as a solution. If it doesn't, you can still find n, but it will be a bit more tricky (which is probably why the authors of the challenge made e = 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.

[โ€“] cvttsd2si 2 points 11 months ago (1 children)

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?

[โ€“] [email protected] 1 points 11 months ago

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 of e_i such that e_1 = e_2 = ... = e_K (mod gcd(c_1, c_2, ... c_K)), which is just an intersection of K sets of at most I*N elements.

[โ€“] [email protected] 1 points 11 months ago

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.