this post was submitted on 01 Dec 2023
17 points (100.0% liked)
NotAwfulTech
385 readers
4 users here now
a community for posting cool tech news you don’t want to sneer at
non-awfulness of tech is not required or else we wouldn’t have any posts
founded 1 year ago
MODERATORS
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
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: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.