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

  • vole@lemmy.world
    link
    fedilink
    English
    arrow-up
    13
    ·
    edit-2
    11 months ago

    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.

    • reboot6675@sopuli.xyz
      link
      fedilink
      arrow-up
      8
      ·
      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…

    • bamboo@lemmy.blahaj.zone
      link
      fedilink
      English
      arrow-up
      2
      ·
      11 months ago

      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@programming.dev
        link
        fedilink
        arrow-up
        6
        ·
        edit-2
        11 months ago

        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.

      • hades@lemm.ee
        link
        fedilink
        arrow-up
        2
        ·
        11 months ago

        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@programming.dev
          link
          fedilink
          arrow-up
          2
          ·
          11 months ago

          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?

          • hades@lemm.ee
            link
            fedilink
            arrow-up
            1
            ·
            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.

      • reboot6675@sopuli.xyz
        link
        fedilink
        arrow-up
        2
        ·
        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.

    • hades@lemm.ee
      link
      fedilink
      arrow-up
      2
      ·
      11 months ago

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

    • Gobbel2000@feddit.de
      link
      fedilink
      arrow-up
      1
      ·
      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.