2020: Day 8

Setup

The original challenge

My data

Part 1

Our programme gets stuck in an infinite loop. As well as keeping track of the accumulator, we need to keep track of where we’ve visited, and stop when we visit the same instruction twice. We use a data.frame() rather than a tibble() as the former is easier to index into.

instructions <- 
  read.table(here::here("2020", "day", "8", "input"), 
             col.names = c("instruction", "value"))

We start with a pretty straight-forward loop, noting that at most it can run for one more than the number of instructions in the programme until it hits an instruction it’s already visited. We update row number to visit next and the accumulator as appropriate.

instructions$visited <- 0

row <- 1
accumulator <- 0

num_rows <- nrow(instructions)

for (i in 1:(num_rows+1)) {

  if (instructions[row, "visited"] != 0) break
  
  # +1 on number of times the row is visited
  instructions[row, "visited"] <- instructions[row, "visited"] + 1

  # case when the instruction is "acc"
  if (instructions[row, "instruction"] == "acc") {
    accumulator <- accumulator + instructions[row, "value"]
    row <- row + 1
  }
  
  # case when the instruction is "jmp"
  else if (instructions[row, "instruction"] == "jmp") {
    row <- row + instructions[row, "value"]
  }

  # case when the instruction is "nop"
  else if (instructions[row, "instruction"] == "nop") {
    row <- row + 1
  }
}
  
accumulator

[1] 1915

Part 2: Fixing the programme

To break the loop, one of the nop instructions in the programme should be a jmp or vice versa. The plan is to swap these out one by one and check if the programme completes. It’s not a sophisticated approach, but it works fast enough (about a second).

First we note that the broken instruction must be one that we visited in Part 1. Also, an instruction of jmp with a value of 0 will get us stuck in a one-line infinite loop, so we avoid that.

library(dplyr)

rows_to_check <- instructions %>%
  mutate(row_id = row_number()) %>%
  filter(visited != 0) %>%
  filter(instruction != "acc") %>%
  filter(!(instruction == "nop" & value == 0)) %>%
  pull(row_id)

We have 93 instruction to check. We modify our code from Part 1 slightly, converting it into a function and returning a list with values completes and accumulator. completes is FALSE as soon as we visit a row twice and TRUE if the number of our next row to visit is greater than the number of rows in the programme.

programme_completes <- function(instructions) {
  
  row <- 1L
  accumulator <- 0
  
  num_rows <- nrow(instructions)
  
  for (i in 1:(num_rows+1)) {
  
    if (instructions[row, "visited"] != 0) {
      return(list(completes = FALSE, accumulator = accumulator)) 
    }
    
    # +1 on number of times the row is visited
    instructions[row, "visited"] <- instructions[row, "visited"] + 1
  
    # case when the instruction is "acc"
    if (instructions[row, "instruction"] == "acc") {
      accumulator <- accumulator + instructions[row, "value"]
      row <- row + 1
    }
  
    else if (instructions[row, "instruction"] == "jmp") {
      row <- row + instructions[row, "value"]
    }
  
    else if (instructions[row, "instruction"] == "nop") {
      row <- row + 1
    }
  
    if (row > num_rows) {
      return(list(completes = TRUE, accumulator = accumulator)) 
    }
  }
}  

We now loop over the rows we’ve identified to check, breaking the loop as soon as we find a programme that completes. Finally, we extract the accumulator value from the successful programme.

instructions$visited <- 0

for (row in rows_to_check) {
  
  # modify one row of the instructions,
  # copying data frame so we don't have to modify it back
  modified_instructions <- instructions
  
  ifelse(instructions[row, 1] == "jmp", 
         modified_instructions[row, 1] <- "nop", 
         modified_instructions[row, 1] <- "jmp") 
  
  # check if the modified programme completes
  check_programme <- programme_completes(modified_instructions)
  
  if (check_programme$completes) 
    break
}

check_programme$accumulator

[1] 944

Session info

Toggle

─ Session info ───────────────────────────────────────────────────────────────
 setting  value
 version  R version 4.3.1 (2023-06-16)
 os       macOS Sonoma 14.0
 system   aarch64, darwin20
 ui       X11
 language (EN)
 collate  en_US.UTF-8
 ctype    en_US.UTF-8
 tz       Europe/London
 date     2023-11-06
 pandoc   3.1.1 @ /Applications/RStudio.app/Contents/Resources/app/quarto/bin/tools/ (via rmarkdown)
 quarto   1.4.466 @ /usr/local/bin/quarto

─ Packages ───────────────────────────────────────────────────────────────────
 package     * version date (UTC) lib source
 dplyr       * 1.1.2   2023-04-20 [1] CRAN (R 4.3.0)
 sessioninfo * 1.2.2   2021-12-06 [1] CRAN (R 4.3.0)

 [1] /Users/ellakaye/Library/R/arm64/4.3/library
 [2] /Library/Frameworks/R.framework/Versions/4.3-arm64/Resources/library

──────────────────────────────────────────────────────────────────────────────