Advent of Code 2023 - Day 8Haunted Wasteland

R | Problem statement | Source code | Tags: Period finding

Part 1

I parse the input into a list of source and targets pairs, and then because each source can have exactly two targets, into a dataframe where each source is a row:

map <- lapply(data[3:length(data)], function(l) {
  parts <- strsplit(l, " = ")[[1]]
  targets <- strsplit(substr(parts[2], 2, nchar(parts[2]) - 1), ", ")[[1]]
  list(source = parts[1], targets = targets)
})
map <- setNames(lapply(map, `[[`, "targets"), lapply(map, `[[`, "source"))
map <- t(data.frame(map))
R

Then it's just a straightforward simulation of going left/right. I use the counter to determine which instruction to follow.

count <- 0
cur <- "AAA"
while (cur != "ZZZ") {
  if (instructions[count %% length(instructions) + 1] == "L") {
    cur <- map[cur, 1]
  } else {
    cur <- map[cur, 2]
  }
  count <- count + 1
}
cat(count, "\n")
R

Part 2

I upgrade cur from a single string to a vector of strings that start with A:

cur <- row.names(map)[grepl("A$", row.names(map))]
R

Theoretically, I can run the same loop, until all the strings start with Z. This turned out to never finish though. The next observation is that the ghosts are all independent, so I can find the period of each ghost and then find the least common multiple of all the periods, similar to 2019 day 12.

But period finding is a bit complicated here. I can know when the ghost first gets to an end point, but: (a) it may be in the middle of the instruction list, so the state does not perfectly repeat afterwards (b) it may not take the same steps back to the starting point (c) it may reach multiple end points in one circle, yada yada, so I was very afraid with any solution. But it turned out that the most naïve version works: just record the first time tt each ghost reaches an end point, and then assume it always reaches that end point at ktkt, and no other end points:

loop_count <- rep(0, length(cur))
while (!all(loop_count > 0)) {
  if (instructions[count %% length(instructions) + 1] == "L") {
    cur <- map[cur, 1]
  } else {
    cur <- map[cur, 2]
  }
  count <- count + 1
  reached_end <- grepl("Z$", cur)
  loop_count[reached_end & loop_count[reached_end] == 0] <- count
}
print(loop_count)
cat(as.character(Reduce(lcm.bigz, loop_count)), "\n")
R

(By the way, another disappointment: R does not have built-in 64 bit integers, so I had to use gmp. This year had so many problems with more than 32 bit integers, so it's quite inconvenient.)

The bigger question is why does this work?? I printed the periods:

14893 20513 22199 19951 17141 12083

It turns out that the instruction list is 281 steps long, and all these periods are odd multiples of 281. So doubt (a) is cleared because by the time the ghost reaches the end point, the instruction list is always fully cycled through. As for doubts (b) and (c), I printed the state every time a ghost reaches an end point, and it turns out that, indeed, the ghost always reaches the same end point at the same time, and never reaches any other end points. So I guess this solution is just by mercy of the input shape. But I don't want to devote any more time to a day 8 problem.