Task 24

Thorn Thaler - <

2025-07-25

1 Setup

1.1 Libraries

library(httr)
library(xml2)
library(tibble)
library(magrittr)
library(dplyr)
library(purrr)
library(stringr)
library(stringi)
library(knitr)
library(cli)
library(rlang)
library(DT)
library(bit64)
library(rlang)

1.2 Retrieve Data from AoC

session_cookie <- set_cookies(session = keyring::key_get("AoC-GitHub-Cookie"))
base_url <- paste0("https://adventofcode.com/", params$year, "/day/", params$task_nr)
puzzle <- GET(base_url,
              session_cookie) %>% 
  content(encoding = "UTF-8") %>% 
  xml_find_all("///article") %>% 
  lapply(as.character)

parse_puzzle_data <- function(text_block = readClipboard()) {
  if (length(text_block) == 1L) {
    text_block <- text_block %>% 
      str_split("\n") %>% 
      extract2(1L) %>% 
      keep(nzchar)
  }
  block_idx <- str_which(text_block, "^inp")
  map2(block_idx, c(tail(block_idx, -1L) - 1L, length(text_block)), ~
         text_block[.x:.y])
}

puzzle_data <- local({
  GET(paste0(base_url, "/input"),
      session_cookie) %>% 
    content(encoding = "UTF-8") %>% 
    parse_puzzle_data()
})

2 Puzzle Day 24

2.1 Part 1

2.1.1 Description

— Day 24: Arithmetic Logic Unit —

Magic smoke starts leaking from the submarine’s arithmetic logic unit (ALU). Without the ability to perform basic arithmetic and logic functions, the submarine can’t produce cool patterns with its Christmas lights!

It also can’t navigate. Or run the oxygen system.

Don’t worry, though - you probably have enough oxygen left to give you enough time to build a new ALU.

The ALU is a four-dimensional processing unit: it has integer variables w, x, y, and z. These variables all start with the value 0. The ALU also supports six instructions:

  • inp a - Read an input value and write it to variable a.
  • add a b - Add the value of a to the value of b, then store the result in variable a.
  • mul a b - Multiply the value of a by the value of b, then store the result in variable a.
  • div a b - Divide the value of a by the value of b, truncate the result to an integer, then store the result in variable a. (Here, “truncate” means to round the value toward zero.)
  • mod a b - Divide the value of a by the value of b, then store the remainder in variable a. (This is also called the modulo operation.)
  • eql a b - If the value of a and b are equal, then store the value 1 in variable a. Otherwise, store the value 0 in variable a.

In all of these instructions, a and b are placeholders; a will always be the variable where the result of the operation is stored (one of w, x, y, or z), while b can be either a variable or a number. Numbers can be positive or negative, but will always be integers.

The ALU has no jump instructions; in an ALU program, every instruction is run exactly once in order from top to bottom. The program halts after the last instruction has finished executing.

(Program authors should be especially cautious; attempting to execute div with b=0 or attempting to execute mod with a<0 or b<=0 will cause the program to crash and might even damage the ALU. These operations are never intended in any serious ALU program.)

For example, here is an ALU program which takes an input number, negates it, and stores it in x: 

inp x
mul x -1

Here is an ALU program which takes two input numbers, then sets z to 1 if the second input number is three times larger than the first input number, or sets z to 0 otherwise: 

inp z
inp x
mul z 3
eql z x

Here is an ALU program which takes a non-negative integer as input, converts it into binary, and stores the lowest (1’s) bit in z, the second-lowest (2’s) bit in y, the third-lowest (4’s) bit in x, and the fourth-lowest (8’s) bit in w: 

inp w
add z w
mod z 2
div w 2
add y w
mod y 2
div w 2
add x w
mod x 2
div w 2
mod w 2

Once you have built a replacement ALU, you can install it in the submarine, which will immediately resume what it was doing when the ALU failed: validating the submarine’s model number. To do this, the ALU will run the MOdel Number Automatic Detector program (MONAD, your puzzle input).

Submarine model numbers are always fourteen-digit numbers consisting only of digits 1 through 9. The digit 0 cannot appear in a model number.

When MONAD checks a hypothetical fourteen-digit model number, it uses fourteen separate inp instructions, each expecting a single digit of the model number in order of most to least significant. (So, to check the model number 13579246899999, you would give 1 to the first inp instruction, 3 to the second inp instruction, 5 to the third inp instruction, and so on.) This means that when operating MONAD, each input instruction should only ever be given an integer value of at least 1 and at most 9.

Then, after MONAD has finished running all of its instructions, it will indicate that the model number was valid by leaving a 0 in variable z. However, if the model number was invalid, it will leave some other non-zero value in z.

MONAD imposes additional, mysterious restrictions on model numbers, and legend says the last copy of the MONAD documentation was eaten by a tanuki. You’ll need to figure out what MONAD does some other way.

To enable as many submarine features as possible, find the largest valid fourteen-digit model number that contains no 0 digits. What is the largest model number accepted by MONAD?

2.1.2 Solution

Our first observation is that the instructions are largely the same for each digit, except at positions 5, 6, 16. In particular the usage of the internal registers is the same for each instruction and only some constants change.

codes <- do.call(rbind, puzzle_data) %>% 
  set_colnames(paste("Step", 1:ncol(.))) %>% 
  set_rownames(paste("Instruction", 1:nrow(.)))

diffs <- do.call(rbind, puzzle_data) %>% 
  apply(2L, \(c) length(unique(c)) != 1L) %>% 
  which()

datatable(
  codes, 
  class = c("compact", "nowrap", "hover", "row-border"),
  options = list(
    pageLength = nrow(codes),
    dom = "t",
    ordering = FALSE,
    columnDefs = list(
      list(
        className = "dt-center", targets = "_all"
      )
    ))
)%>% 
  formatStyle(diffs, 
              backgroundColor = "firebrick", 
              color = "white", 
              fontStyle = "italic")

Now we can translate each instruction set to native R code:

  • inp w: Read input (d, say) and store it in w: w <- d.
  • mul x 0, add x z, mod x 26, div z 1, add x 10: Copy the value of z to x, take it modulo 26 and add a constant c1 (this was one of the changing instructions). Replace z by z divided by c2 (again a differnt constant for each instruction): x <- z %% 26 + c1 and z <- z %/% c2.
  • eql x w, eql x 0: Store 1 in x, if xdoes not equal w, otherwise store 0: x <- as.integer(x != w).
  • mul y 0, add y 25, mul y x, add y 1: Multiply xby 25 and add 1 and sore the reuslt in y: y <- 25L * x + 1L.
  • mul z y: Multiply z by y and store it in z: z <- z * y.
  • mul y 0, add y w, add y 1, mul y x: Add constant c3 to to w, multiply by x and store the result in y: y <- (w + c3) * x.
  • add z y: Add z to y and store the result in z: z <- z + y.

To find valid codes, we start at the end where we know that z must equal 0 in order to result in a valid code. From there, with a given digit we simply brute-force all possible z of the previous digit and recurse with all valid digits.

Since this is a rather heavy brute-force algorithm, we fall back to C++ to gain a considerable amount of speed.

A smarter algorithm would be to limit the list of candidates z to make the search space smaller and to introduce some hash table to avoid recalculating known values.

As a matter of fact the first version used a hash map which reduced the amount of runs by a factor of 11, but overall the algorithm was slower due to the overhead involved in checking feasible values.

#ifndef STANDALONE
#include <Rcpp.h>
using namespace Rcpp;
#else
#include <iostream>
#define Rcout std::cout
#endif
#include <array>
#include <set>
#include <string>

class NomadSolver {
  public:
    NomadSolver(const std::array<std::array<int, 3>, 14>&, bool);
    std::set<std::string> start(bool);

  private:
    unsigned int runs;
    bool is_verbose;
    const std::array<int, 9> digits = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    std::set<std::string> solutions;
    std::array<std::array<int, 3>, 14> params;

    void solve(int, int, int, std::string);
};

NomadSolver::NomadSolver(const std::array<std::array<int, 3>, 14>& df, bool verbose = false)
    : runs(0)
    , is_verbose(verbose)
    , params(df) { }

void NomadSolver::solve(int d, int z_goal, int depth, std::string code) {
  int x0, y0, y1, z0, z1, zc;
  std::set<int> z_prev;
  if (++runs % 10000000 == 0) {
    if (is_verbose) {
      Rcout << runs << std::endl;
    }
  }
  if (depth == -1) {
    solutions.insert(code.substr(1));
    return;
  }
  const int c1 = params[depth][0], c2 = params[depth][1], c3 = params[depth][2];
  for (int x1 = 0; x1 <= 1; x1++) {
    y1 = (d + c3) * x1;
    z1 = z_goal - y1;
    y0 = 25 * x1 + 1;
    if ((z1 % y0) == 0) {
      z0 = z1 / y0;
      for (int i = 0; i < c1; i++) {
        zc = z0 * c1 + i;
        x0 = zc % 26 + c2;
        if ((x0 != d) == x1) {
          z_prev.insert(zc);
        }
      }
    }
  }
  for (auto z_new : z_prev) {
    for (auto d_new : digits) {
      solve(d_new, z_new, depth - 1, std::to_string(d_new) + code);
    }
  }
}

std::set<std::string> NomadSolver::start(bool force = false) {
  if (solutions.empty() || force) {
    solutions.clear();
    runs = 0;
    for (auto d : digits) {
      solve(d, 0, 13, std::to_string(d));
    }
    if (is_verbose) {
      Rcout << "Total runs:" << runs << std::endl;
    }
  }
  return solutions;
}
#ifndef STANDALONE
// [[Rcpp::export]]
CharacterVector solve_nomad(const DataFrame& df) {
  int nr_rows = df.nrows(), nr_cols = df.length();
  std::array<std::array<int, 3>, 14> params;
  if (nr_cols != 3 || nr_rows != 14) {
    stop("'df' must have 14 rows and 3 columns (got %i x %i)", nr_rows, nr_cols);
  }
  for (R_xlen_t j = 0; j < nr_cols; j++) {
    NumericVector col = df[j];
    for (R_xlen_t i = 0; i < nr_rows; i++) {
      params[i][j] = col[i];
    }
  }
  NomadSolver solver(params);
  return wrap(solver.start());
}
#else
int main() {
  std::array<std::array<int, 3>, 14> params = {{{1, 10, 1},
                                                {1, 11, 9},
                                                {1, 14, 12},
                                                {1, 13, 6},
                                                {26, -6, 9},
                                                {26, -14, 15},
                                                {1, 14, 7},
                                                {1, 13, 12},
                                                {26, -8, 15},
                                                {26, -15, 3},
                                                {1, 10, 6},
                                                {26, -11, 2},
                                                {26, -13, 10},
                                                {26, -4, 12}}};
  NomadSolver solver(params, true);
  auto solutions = solver.start(true);

  long long max_val = LLONG_MIN;
  for (const auto& str : solutions) {
    long long val = std::stoll(str);
    if (val > max_val) {
      max_val = val;
    }
  }
  std::cout << "Largest solution: " << max_val << std::endl;
  return 0;
}
#endif
consts <- map(puzzle_data, 
              ~ str_extract(.x[c(5:6, 16)], "-?\\d+") %>% 
                as.integer() %>% 
                set_names(paste0("c", 1:3))) %>% 
  do.call(rbind, .) %>% 
  as_tibble()

all_solutions <- solve_nomad(consts) %>% 
  as.integer64()

max(all_solutions)
## integer64
## [1] 99999795919456

2.2 Part 2

2.2.1 Description

— Part Two —

As the submarine starts booting up things like the Retro Encabulator, you realize that maybe you don’t need all these submarine features after all.

What is the smallest model number accepted by MONAD?

2.2.2 Solution

As we generated already all valid codes for part 1, we simply need to return the smallest code for this part.

min(all_solutions)
## integer64
## [1] 45311191516111