this post was submitted on 01 Dec 2023
17 points (100.0% liked)

NotAwfulTech

367 readers
1 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
[email protected]
17
The official awful.systems Advent of Code 2023 thread (awful.systems)
submitted 1 year ago* (last edited 1 year ago) by [email protected] to c/[email protected]
121 comments fedilink hide all child comments
 

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.

you are viewing a single comment's thread
view the rest of the comments
[–] [email protected] 1 points 11 months ago* (last edited 11 months ago)

8

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

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

bAs 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.