Day 24

Advent of Code: Worked Solutions

Setup

Import libraries:

library(tidyverse)
library(unglue)

Read and parse text input from file:

input <- read_lines("../input/day24.txt") |> 
  unglue_data(patterns = c("{f=...} {a=.}", "{f} {a=.} {b}"))

Part 1

By visual inspection, the instructions are all minor variations on the same repeated set of instructions. Block 1 is interpreted below:

Instruction	Description	Output Value
inp w	Read a new digit into w	w = {1:9}
mul x 0	Zero out x	x = 0
add x z	Set x equal to z	x = 0
mod x 26	Modulo x by 26 (0)	x = 0
div z 1	Divide z by 1 (no effect)	z = 0
add x 14	Add 14 to x (14)	x = 14
eql x w	Check if x equals w	x = 0
eql x 0	Check if above is true	x = 1
mul y 0	Zero out y	y = 0
add y 25	Set y to 25	y = 25
mul y x	Multiply y by x (either 1 or 0)	y = 25
add y 1	Add 1 to y	y = 26
mul z y	Multiply z by y	z = 0
mul y 0	Zero out y	y = 0
add y w	Set y to w	y = w
add y 12	Add 12 to y	y = w + 12
mul y x	Multiply y by x (either 1 or 0)	y = w + 12
add z y	Add y to z	z = w + 12

If we represent the set of 3 integers that vary from block to block as “c1[i]”, “c2[i]”, and “c3[i]”, with i indicating the block number ranging from 1:14, this series of instructions is equivalent to the following code:

# Example 14-digit number
w <- c(1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4)  
z <- 0

for (i in 1:length(w)) {
  if (z %% 26 + c2[i] == w[i]) 
    z <- floor(z / c1[i]) 
  else 
    z <- floor(z / c1[i]) * 26 + w[i] + c3[i]
}

Extract the c1, c2, and c3 values from the input:

const <- input |> 
  mutate(grp = cumsum(f == "inp")) |> 
  mutate(row = row_number(), .by = grp) |> 
  summarize(b = list(b), .by = row) |> 
  pull(b) |> 
  keep_at(c(5, 6, 16)) |> 
  map(parse_number)

c1 <- const[[1]]
c2 <- const[[2]]
c3 <- const[[3]]

Below, we define the set of code blocks as a recursive function to loop through possible input values and find one that ends on zero.

To improve performance, we prune branches early on if they can never reach zero in the remaining rounds: - Each round, the best-case scenario for a large z to shrink toward zero is for the if-else statement to be true, which would result in z becoming floor(z / c1[i]). - If z is greater than or equal to the product of the remaining c1 values, it can’t be reduced to zero by the last round. - Example: as a test case, imagine that c1 = 2 in every round. - When there’s 1 round remaining, the final output is 0 if the input z is no greater than 0 or 1. - When there’s 2 rounds remaining, the round’s output can be 0/1 if the input z is no greater than 0/1/2/3. - When there’s 3 rounds remaining, the round’s output can be 0/1/2/3 if the input z is no greater than 0/1/2/3/4/5/6/7, i.e., if the input z < 2^3. - Generalizing, in the 14th round, the input z must be less than c1[14]. In the 13th round, the input z must be less than c1[14] * c1[13], etc.

zmax <- accumulate(c1, prod, .dir = "backward")

Define our recursive search funtion as described above:

f <- function(z = 0, vec = c(), i = 1, digits) {
  
  # Check if the last round has been reached. Return success if z is 0.
  if (i == 15) {
    if (z == 0) 
      return(vec) 
    else 
      return()
  }
  
  # Abort early if z is too large and can never reach 0 by the end
  if (z >= zmax[i])
    return()
  
  # Loop through possible input values (in increasing or decreasing order)
  for (w in digits) {
    if (z %% 26 + c2[i] == w)
      result <- f(floor(z / c1[i]), c(vec, w), i + 1, digits)
    else 
      result <- f(floor(z / c1[i]) * 26 + w + c3[i], c(vec, w), i + 1, digits)
    
    if (!is.null(result))
      return(result)
  }
}

Search in order from highest to lowest input values:

cat(f(digits = 9:1), sep = "")

Part 2

Reverse the search vector from 9:1 to 1:9 to search from lowest to highest values, and re-run:

cat(f(digits = 1:9), sep = "")