Task 18

Thorn Thaler - <

2025-09-29

1 Setup

1.1 Libraries

library(httr)
library(xml2)
library(magrittr)
library(dplyr)
library(purrr)
library(stringr)
library(kableExtra)
library(collections)
library(bit64)

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)
  }
  text_block %>% 
    str_split(" ") %>% 
    map(~ c(.x, NA_character_)[1:3]) %>% 
    do.call(rbind, .) %>% 
    set_colnames(c("op", "arg1", "arg2")) %>% 
    as_tibble() %>% 
    mutate(op_original = text_block, .before = 1L)
}

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

2 Puzzle Day 18

2.1 Part 1

2.1.1 Description

— Day 18: Duet —

You discover a tablet containing some strange assembly code labeled simply “Duet”. Rather than bother the sound card with it, you decide to run the code yourself. Unfortunately, you don’t see any documentation, so you’re left to figure out what the instructions mean on your own.

It seems like the assembly is meant to operate on a set of registers that are each named with a single letter and that can each hold a single integer. You suppose each register should start with a value of 0.

There aren’t that many instructions, so it shouldn’t be hard to figure out what they do. Here’s what you determine:

  • snd X plays a sound with a frequency equal to the value of X.
  • set X Y sets register X to the value of Y.
  • add X Y increases register X by the value of Y.
  • mul X Y sets register X to the result of multiplying the value contained in register X by the value of Y.
  • mod X Y sets register X to the remainder of dividing the value contained in register X by the value of Y (that is, it sets X to the result of X modulo Y).
  • rcv X recovers the frequency of the last sound played, but only when the value of X is not zero. (If it is zero, the command does nothing.)
  • jgz X Y jumps with an offset of the value of Y, but only if the value of X is greater than zero. (An offset of 2 skips the next instruction, an offset of -1 jumps to the previous instruction, and so on.)

Many of the instructions can take either a register (a single letter) or a number. The value of a register is the integer it contains; the value of a number is that number.

After each jump instruction, the program continues with the instruction to which the jump jumped. After any other instruction, the program continues with the next instruction. Continuing (or jumping) off either end of the program terminates it.

For example: 

set a 1
add a 2
mul a a
mod a 5
snd a
set a 0
rcv a
jgz a -1
set a 1
jgz a -2
  • The first four instructions set a to 1, add 2 to it, square it, and then set it to itself modulo 5, resulting in a value of 4.
  • Then, a sound with frequency 4 (the value of a) is played.
  • After that, a is set to 0, causing the subsequent rcv and jgz instructions to both be skipped (rcv because a is 0, and jgz because a is not greater than 0).
  • Finally, a is set to 1, causing the next jgz instruction to activate, jumping back two instructions to another jump, which jumps again to the rcv, which ultimately triggers the recover operation.

At the time the recover operation is executed, the frequency of the last sound played is 4.

What is the value of the recovered frequency (the value of the most recently played sound) the first time a rcv instruction is executed with a non-zero value?

2.1.2 Solution

To solve the first part of the puzzle let’s have a look at the lines 1--28:

puzzle_data %>% 
  slice(1:26) %>% 
  select(Instruction = op_original) %>% 
  mutate(Loops = rep(c("", "<--+", "   |", "---+", "", "<--+", "   |", "---+", "-----+",
                   "<-+  |", "--+  |", "<----+", ""), 
                   c(4L, 1L, 1L, 1L, 3L, 1L, 8L, 1L, 1L, 1L, 1L, 1L, 2L))) %>% 
  mutate(Loops = paste0("<pre>", Loops, "</pre>")) %>% 
  kbl(escape = FALSE, row.names = TRUE) %>%
  kable_styling(bootstrap_options = c("striped", "hover", "condensed"), 
                full_width = FALSE) %>% 
  column_spec(2, monospace = TRUE)
Instruction Loops
1 set i 31 







2


set a 1










3


mul p 17










4


jgz p p










5


mul a 2



<--+







6


add i -1



   |







7


jgz i -2



---+







8


add a -1










9


set i 127










10


set p 464










11


mul p 8505



<--+







12


mod p a



   |







13


mul p 129749



   |







14


add p 12345



   |







15


mod p a



   |







16


set b p



   |







17


mod b 10000



   |







18


snd b



   |







19


add i -1



   |







20


jgz i -9



---+







21


jgz a 3



-----+







22


rcv b



<-+  |







23


jgz b -1



--+  |







24


set f 0



<----+







25


set i 126










26


rcv a











We see that lines 1 to 20 form a setup block, where registers are set. We also note, that
register a equals 2 ^ 31 - 1. The sound is set in the loop with the frequency derived
from the given instructions.


After the loop ends in line 20, we jump conditionally on a. Since a is not
zero at this stage, we will always continue with line 24 and we eventually hit line 26
which will return the frequency set in the loop.


Thus, all we need to do is to implement the first loop to get the deisred frequency.


get_frequency <- function() {
  p <- 464L
  a <- 2L ^ 31L - 1L
  for (i in 1:127) {
    p <- (((p * 8505) %% a) * 129749 + 12345) %% a 
    res <- p %% 10000
    
  }
  res
}
get_frequency()


## [1] 1187








2.2 Part 2




2.2.1 Description





— Part Two —




As you congratulate yourself for a job well done, you notice that the documentation has been on the back of the tablet this entire time. While you actually got most of the instructions correct, there are a few key differences. This assembly code isn’t about sound at all - it’s meant to be run twice at the same time.




Each running copy of the program has its own set of registers and follows the code independently - in fact, the programs don’t even necessarily run at the same speed. To coordinate, they use the send (snd) and receive (rcv) instructions:



    

  • 
snd X sends the value of X to the other program. These values wait in a queue until that program is ready to receive them. Each program has its own message queue, so a program can never receive a message it sent.

    • 

  • 
rcv X receives the next value and stores it in register X. If no values are in the queue, the program waits for a value to be sent to it. Programs do not continue to the next instruction until they have received a value. Values are received in the order they are sent.

    • 




Each program also has its own program ID (one 0 and the other 1); the register p should begin with this value.




For example:



snd 1
snd 2
snd p
rcv a
rcv b
rcv c
rcv d




Both programs begin by sending three values to the other. Program 0 sends 1, 2, 0; program 1 sends 1, 2, 1. Then, each program receives a value (both 1) and stores it in a, receives another value (both 2) and stores it in b, and then each receives the program ID of the other program (program 0 receives 1; program 1 receives 0) and stores it in c. Each program now sees a different value in its own copy of register c.




Finally, both programs try to rcv a fourth time, but no data is waiting for either of them, and they reach a deadlock. When this happens, both programs terminate.




It should be noted that it would be equally valid for the programs to run at different speeds; for example, program 0 might have sent all three values and then stopped at the first rcv before program 1 executed even its first instruction.




Once both of your programs have terminated (regardless of what caused them to do so), how many times did program 1 send a value?









2.2.2 Solution


For part 2, we develop a proper parser, which uses a message queue for the messages to be
exchanged. Then, we run program 0 until it blocks, followed by program 1 until it
blocks. If program 0 still blocks we are done, otherwise continue until a state is
reached where both programs block.


The R version is slow, hence, as usual, we switched to C++. The R code can be found
in the appendix.


#ifndef STANDALONE
#include <Rcpp.h>
using namespace Rcpp;
#else
#include <iostream>
#endif
#include <fstream>
#include <optional>
#include <queue>
#include <sstream>
#include <string>
#include <unordered_map>
#include <vector>

enum class OpCode { SND, RCV, SET, ADD, MUL, MOD, JGZ };
enum class ParamType { REG, VAL };

class Program;

class Parameter {
  public:
    Parameter();
    Parameter(const std::string&);

    long long operator()(const Program*) const;
    char operator()() const;

    friend std::ostream& operator<<(std::ostream&, const Parameter&);

  private:
    ParamType type;
    long long value;
    char register_name;
};

class Instruction {
  public:
    Instruction(const std::string&);
    bool operator()(Program*) const;

    friend std::ostream& operator<<(std::ostream&, const Instruction&);

  private:
    OpCode opcode;
    Parameter param1;
    std::optional<Parameter> param2;
    static const std::unordered_map<std::string, OpCode> opcode_map;

    static OpCode parse_opcode(const std::string& token);
};

class Program {
  public:
    Program(int, std::vector<Instruction>&, std::queue<long long>&, std::queue<long long>&);

    Program& operator++();

    void set_register(char reg, long long);
    long long get_register(char) const;

    void send(long long);
    std::optional<long long> receive();

    void jump(long long);

    bool run();

    long long get_send_count() const;

  private:
    long long line_count;
    long long snd_count;
    std::queue<long long>& rcv_queue;
    std::queue<long long>& snd_queue;
    std::vector<Instruction>& instructions;
    std::unordered_map<char, long long> registers;
};

Parameter::Parameter()
    : type(ParamType::VAL)
    , value(0)
    , register_name('\0') { }

Parameter::Parameter(const std::string& token)
    : type(ParamType::VAL)
    , value(0)
    , register_name('\0') {
  if (std::isdigit(token[0]) || token[0] == '-') {
    value = std::stoll(token);
    type = ParamType::VAL;
  } else {
    register_name = token[0];
    type = ParamType::REG;
  }
}

long long Parameter::operator()(const Program* program) const {
  if (type == ParamType::VAL) {
    return value;
  } else {
    return program->get_register(register_name);
  }
}

char Parameter::operator()() const {
  return register_name;
}

std::ostream& operator<<(std::ostream& os, const Parameter& param) {
  if (param.type == ParamType::VAL) {
    os << param.value;
  } else {
    os << param.register_name;
  }
  return os;
}

const std::unordered_map<std::string, OpCode> Instruction::opcode_map = {{"snd", OpCode::SND},
                                                                         {"rcv", OpCode::RCV},
                                                                         {"set", OpCode::SET},
                                                                         {"add", OpCode::ADD},
                                                                         {"mul", OpCode::MUL},
                                                                         {"mod", OpCode::MOD},
                                                                         {"jgz", OpCode::JGZ}};

Instruction::Instruction(const std::string& line) {
  std::istringstream iss(line);
  std::string op_str, p1_str, p2_str;
  iss >> op_str >> p1_str;

  opcode = parse_opcode(op_str);
  param1 = Parameter(p1_str);

  if (iss >> p2_str) {
    param2 = Parameter(p2_str);
  } else {
    param2 = std::nullopt;
  }
}

bool Instruction::operator()(Program* program) const {
  bool blocked = false;
  switch (opcode) {
  case OpCode::SND:
    program->send(param1(program));
    ++(*program);
    break;
  case OpCode::RCV: {
    auto val = program->receive();
    if (val.has_value()) {
      program->set_register(param1(), val.value());
      ++(*program);
    } else {
      blocked = true;
    }
    break;
  }
  case OpCode::SET:
    program->set_register(param1(), (*param2)(program));
    ++(*program);
    break;
  case OpCode::ADD:
    program->set_register(param1(), param1(program) + (*param2)(program));
    ++(*program);
    break;
  case OpCode::MUL: {
    program->set_register(param1(), param1(program) * (*param2)(program));
    ++(*program);
    break;
  }
  case OpCode::MOD:
    program->set_register(param1(), param1(program) % (*param2)(program));
    ++(*program);
    break;
  case OpCode::JGZ:
    if (param1(program) > 0) {
      program->jump((*param2)(program));
    } else {
      ++(*program);
    }
    break;
  }
  return !blocked;
}

OpCode Instruction::parse_opcode(const std::string& token) {
  auto it = opcode_map.find(token);
  return it->second;
}

std::ostream& operator<<(std::ostream& os, const Instruction& instr) {
  std::string key = "NOP";
  for (const auto& [k, v] : Instruction::opcode_map) {
    if (v == instr.opcode) {
      key = k;
      break;
    }
  }
  os << key << " " << instr.param1;
  if (instr.param2.has_value()) {
    os << " " << *instr.param2;
  }
  return os;
}

Program::Program(int id,
                 std::vector<Instruction>& instrs,
                 std::queue<long long>& rcv_q,
                 std::queue<long long>& snd_q)
    : line_count(0)
    , snd_count(0)
    , rcv_queue(rcv_q)
    , snd_queue(snd_q)
    , instructions(instrs) {
  registers = {{'a', 0}, {'b', 0}, {'f', 0}, {'i', 0}, {'p', id}};
}

Program& Program::operator++() {
  ++line_count;
  return *this;
}

void Program::set_register(char reg, long long value) {
  registers[reg] = value;
}

long long Program::get_register(char reg) const {
  auto it = registers.find(reg);
  if (it != registers.end()) {
    return it->second;
  } else {
    return 0;
  }
}

void Program::send(long long value) {
  snd_queue.push(value);
  snd_count++;
}

std::optional<long long> Program::receive() {
  if (rcv_queue.empty()) {
    return std::nullopt;
  } else {
    long long value = rcv_queue.front();
    rcv_queue.pop();
    return value;
  }
}

void Program::jump(long long offset) {
  line_count += offset;
}

long long Program::get_send_count() const {
  return snd_count;
}

bool Program::run() {
  bool done = line_count < 0 || line_count >= instructions.size();
  bool blocked = false;
  bool has_run = false;
  while (!done && !blocked) {
    Instruction& instr = instructions[line_count];
    bool success = instr(this);
    blocked = !success;
    has_run = has_run || success;
    done = line_count < 0 || line_count >= instructions.size();
  }
  return has_run;
}

long long get_send_count(const std::vector<std::string>& instruction_lines) {
  std::vector<Instruction> instructions;
  for (const auto& line : instruction_lines) {
    instructions.emplace_back(line);
  }

  std::queue<long long> queue_0_to_1;
  std::queue<long long> queue_1_to_0;

  Program p0(0, instructions, queue_1_to_0, queue_0_to_1);
  Program p1(1, instructions, queue_0_to_1, queue_1_to_0);

  bool prog0_ran = true;
  bool prog1_ran = true;

  while (prog0_ran || prog1_ran) {
    prog0_ran = p0.run();
    prog1_ran = p1.run();
  }

  return p1.get_send_count();
}

#ifndef STANDALONE
// [[Rcpp::export]]
long long get_send_count(const CharacterVector& instruction_lines) {
  return get_send_count(as<std::vector<std::string>>(instruction_lines));
}

#else
int main() {
  // program 1 sends 6 messages
  std::vector<std::string> instructions = {"add p 1",
                                           "mod p 2",
                                           "mul p 5",
                                           "snd p",
                                           "rcv a",
                                           "jgz a 3",
                                           "rcv b",
                                           "jgz 1 -1",
                                           "snd a",
                                           "add a -1",
                                           "jgz a -2",
                                           "rcv b",
                                           "jgz 1 -2"};
  std::cout << get_send_count(instructions) << std::endl;
}
#endif


get_send_count(puzzle_data %>% 
                 pull(op_original))


## [1] 5969








2.3 R - Version


program <- function(ops, rcv_queue, snd_queue, p) {
  me <- paste0("[P", p, "]")
  reg <- c(0, 0, 0, 0, as.integer(p)) %>% 
    as.integer64() %>% 
    set_names(c("a", "b", "f", "i", "p"))
  line_counter <- 1L
  snd_counter <- 0L
  empty_queue <- structure(list(
    message = paste("Queue for program", p, "is empty"),
    call = NULL),
    class = c("empty_queue", "error", "condition"))
  
  val <- function(arg, set = FALSE) {
    val <- as.integer(arg) %>% 
      suppressWarnings()
    if (set) {
      stopifnot("Cannot use a number to save results" = is.na(val),
                "Unknown register name" = arg %in% names(reg))
      arg
    } else {
      if (is.na(val)) {
        reg[arg]
      } else {
        val        
      }
    }
  }
  set <- function(arg1, arg2, ...) {
    reg[val(arg1, TRUE)] <<- val(arg2)
    line_counter <<- line_counter + 1L
  }
  
  add <- function(arg1, arg2, ...) {
    reg[val(arg1, TRUE)] <<- reg[val(arg1, TRUE)] + val(arg2)
    line_counter <<- line_counter + 1L
  }
  
  mul <- function(arg1, arg2, ...) {
    reg[val(arg1, TRUE)] <<- reg[val(arg1, TRUE)] * val(arg2)
    line_counter <<- line_counter + 1L
  }
  
  mod <- function(arg1, arg2, ...) {
    reg[val(arg1, TRUE)] <<- reg[val(arg1, TRUE)] %% val(arg2)
    line_counter <<- line_counter + 1L
  }
  
  jgz <- function(arg1, arg2, ...) {
    if (val(arg1) > 0L) {
      line_counter <<- line_counter + as.integer(val(arg2))
    } else {
      line_counter <<- line_counter + 1L
    }
  }
  
  snd <- function(arg1, ...) {
    cat(me, ": Send msg #", snd_counter, "\r", sep = "")
    snd_queue$push(val(arg1))
    snd_counter <<- snd_counter + 1L
    line_counter <<- line_counter + 1L
  }
  
  rcv <- function(arg1, ...) {
    if (rcv_queue$size() == 0L) {
      signalCondition(empty_queue)
    } else {
      reg[val(arg1, TRUE)] <<- rcv_queue$pop()
      line_counter <<- line_counter + 1L
    }
  }
  
  get_snd_cnt <- function() {
    snd_counter
  }
  
  run <- function() {
    done <- !between(line_counter, 1L, nrow(ops))
    blocked <- FALSE
    has_run <- FALSE
    while (!done && !blocked) {
      line <- ops %>% 
        slice(line_counter) %>% 
        select(op:arg2) %>% 
        as.list()
      op_orig <- ops %>% 
        slice(line_counter) %>% 
        pull(op_original)
      
      run <- tryCatch({
        do.call(line[[1L]], line[-1L])
        TRUE
      },
      empty_queue = function(err) {
        FALSE
      })
      if (run) {
        has_run <- TRUE
      } else {
        blocked <- TRUE
      }
      done <- !between(line_counter, 1L, nrow(ops))
    }
    cat("\n")
    has_run
  }
  
  list(run = run,
       get_snd_cnt = get_snd_cnt,
       get_state = function() {
         list(
           reg = reg,
           line_counter = line_counter
         )
       })
}

duet <- function(ops = puzzle_data) {
  is_deadlock <- FALSE
  q0 <- queue()
  q1 <- queue()
  p0 <- program(ops, q0, q1, 0L)
  p1 <- program(ops, q1, q0, 1L)
  while(!is_deadlock) {
    p0_ran <- p0$run()
    browser()
    p1_ran <- p1$run()
    is_deadlock <- !p0_ran && !p1_ran
  }
  p1$get_snd_cnt()
  
}