Day 22

Advent of Code: Worked Solutions

Setup

Import libraries:

library(tidyverse)

Read input from txt file into a numeric vector:

input <- scan("../input/day22.txt")

Part 1

R only has bitwise operations for integers up to 32 bits. First, we have to define functions to convert between large numeric values and 64-“bit” 1/0 vectors:

base64 <- 2^(63:0)  # (pre-compute this vector to reduce runtime)

as_b64 <- \(x) x %/% base64 %% 2
as_num <- \(x) sum(x * base64)

Define a function to perform xor operations on large integers:

b64xor <- \(x, y) as_num(base::xor(as_b64(x), as_b64(y)))

Define the algorithm for producing a sequence of “secret” numbers:

prune <- \(x) x %% 16777216

secret_alg <- function(x0) {
  x1 <- prune(b64xor(x0, x0 * 64))
  x2 <- prune(b64xor(x1, x1 %/% 32))
  x3 <- prune(b64xor(x2, x2 * 2048))
  
  x3
}

secret_seq <- function(init, n) {
  map(init, \(init) accumulate(1:n, \(x, y) secret_alg(x), .init = init))
}

Generate 2000 “secret numbers” for each initial value in the puzzle input:

secret_nums <- secret_seq(input, n = 2000)

Sum the 2000th “secret number” for each value in our input:

secret_nums |> 
  map_dbl(~ tail(.x, n = 1)) |> 
  sum()

Part 2

Convert the set of secret number sequences to a dataframe organized by buyer and time:

diffs <- secret_nums |> 
  enframe(name = "buyer_id", value = "secret_number") |> 
  unnest_longer(secret_number, indices_to = "time") |> 
  mutate(
    
    # Get the price at each time by taking the ones digit of each secret number
    price = secret_number %% 10L,
    
    # Compute the difference in price at the current time vs the previous time
    diff = price - lag(price),
    
    # Compute the sequence of 4 price changes preceeding the current price
    lag1 = lag(diff, n = 1L),
    lag2 = lag(diff, n = 2L),
    lag3 = lag(diff, n = 3L),
    diff_seq = str_c(lag3, lag2, lag1, diff, sep = ","),
    
    .by = buyer_id
  ) |> 
  arrange(buyer_id, time)

For each price change sequence, compute the bananas you will get from each buyer:

bananas_by_seq <- diffs |> 
  filter(!is.na(diff_seq)) |> 
  summarize(
    bananas = head(price, 1),
    .by = c(buyer_id, diff_seq)
  )

Find the most advantageous sequence:

bananas_by_seq |> 
  summarize(bananas = sum(bananas), .by = diff_seq) |> 
  slice_max(bananas) |> 
  pull(bananas)