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

  • cvttsd2si@programming.dev
    link
    fedilink
    arrow-up
    6
    ·
    edit-2
    1 year 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.