Rules: no spoilers.

The other rules are made up as we go along.

Share code by link to a forge, home page, pastebin (Eric Wastl has one here) or code section in a comment.

  • @swlabr
    cake
    link
    English
    1
    edit-2
    7 months ago

    8

    Hint for b

    The brute solution will take ~100 hours on my machine. You will need (to fudge) some very basic number theory to make it faster.

    a

    A straightforward implementation of the traversal was sufficient for performant code.

    b

    As suggested by the hint, I tried running the brute force solution. The pseudocode is something like this:

    count = 0
    while(all ghosts not on endpoint):
       for (all ghosts):
        move ghost to next node
      count++
    
    print count
    

    I put a timestamp for every 100mil iterations, which ticked once every two seconds.

    So, how do we solve it? As mentioned in my hint, some fudged number theory is required.

    Long story short, each ghost will eventually reach an end node. They could reach K endpoints, where K is the total number of end nodes available. They will follow the same path in a loop if they traverse infinitely.

    The fudge is this: assume each ghost only hits one end node repeatedly. In this case, the solution is just the LCM of the number of steps it takes for each ghost to reach its end node from the initial state.

    If given a case where a ghost hits multiple unique endpoints, you can probably find the configuration of counts and LCMs to yield the smallest one, but that proof is left to the reader.

    The answer that I got was in the magnitude of 10 trillion, close to 20 trillion.