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

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