Task 7

Thorn Thaler - <

2025-03-07

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(igraph)

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)
  }
  ops <- text_block %>% 
    str_split("\\s") %>% 
    map(function(ops) {
      c(rep(NA_character_, 5L - length(ops)), ops)
    }) %>% 
    do.call(rbind, .)
  ops <- ops[, -4]
  colnames(ops) <- c("lhs", "op", "rhs", "res")
  as_tibble(ops)
}

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

2 Puzzle Day 7

2.1 Part 1

2.1.1 Description

— Day 7: Some Assembly Required —

This year, Santa brought little Bobby Tables a set of wires and bitwise logic gates! Unfortunately, little Bobby is a little under the recommended age range, and he needs help assembling the circuit.

Each wire has an identifier (some lowercase letters) and can carry a 16-bit signal (a number from 0 to 65535). A signal is provided to each wire by a gate, another wire, or some specific value. Each wire can only get a signal from one source, but can provide its signal to multiple destinations. A gate provides no signal until all of its inputs have a signal.

The included instructions booklet describes how to connect the parts together: x AND y -> z means to connect wires x and y to an AND gate, and then connect its output to wire z.

For example:

  • 123 -> x means that the signal 123 is provided to wire x.
  • x AND y -> z means that the bitwise AND of wire x and wire y is provided to wire z.
  • p LSHIFT 2 -> q means that the value from wire p is left-shifted by 2 and then provided to wire q.
  • NOT e -> f means that the bitwise complement of the value from wire e is provided to wire f.

Other possible gates include OR (bitwise OR) and RSHIFT (right-shift). If, for some reason, you’d like to emulate the circuit instead, almost all programming languages (for example, C, JavaScript, or Python) provide operators for these gates.

For example, here is a simple circuit: 

123 -> x
456 -> y
x AND y -> d
x OR y -> e
x LSHIFT 2 -> f
y RSHIFT 2 -> g
NOT x -> h
NOT y -> i

After it is run, these are the signals on the wires: 

d: 72
e: 507
f: 492
g: 114
h: 65412
i: 65079
x: 123
y: 456

In little Bobby’s kit’s instructions booklet (provided as your puzzle input), what signal is ultimately provided to wire a?

2.1.2 Solution

We solve this puzzle by means of graph theory.

  1. For each operation lhs op rhs -> res we create the nodes lhs -> op, rhs -> op and op -> res (note that the NOT operator has no lhs and a pure assignment has neither op nor lhs).
  2. We sort the graph then topologically, that is nodes with no incoming nodes (this will be the number literals) come first, followed by their dependent nodes and so on.
  3. Then all what is left, is to iterate through the graph in topological order:
    1. If we hit a node with a number literal, assign this value to the node.
    2. If we hit an operator node, perform the corresponding operation with the value from its predecessors (some care has to be taken for the non-commutative SHIFT operators to make sure their operands are used in the right order)
    3. If we hit a output node, simply copy the value from its predecessor.
  4. The final result will then be stored in node a.
construct_graph <- function(ops) {
  ops <- ops %>% 
    mutate(
      op_label = case_when(
      is.na(op) ~ op,
      is.na(lhs) ~ paste(op, rhs, sep = "_"),
      TRUE ~ paste(lhs, op, rhs, sep = "_")
    )
    )
  el <- matrix(character(0), 0, 2) %>% 
    set_colnames(c("from", "to"))
  for (i in seq_len(nrow(ops))) {
    gate <- ops %>% 
      slice(i) %>% 
      as.list()
    if (is.na(gate$op)) {
      ## assignment operator
      el <- el %>% 
        rbind(
          cbind(gate$rhs, gate$res)
        )
    } else if (gate$op == "NOT") {
      el <- el %>% 
        rbind(
          cbind(gate$rhs, gate$op_label),
          cbind(gate$op_label, gate$res)
          )
    } else {
      el <- el %>% 
        rbind(
          cbind(gate$lhs, gate$op_label),
          cbind(gate$rhs, gate$op_label),
          cbind(gate$op_label, gate$res)
        )
    }
  }
  G <- graph_from_edgelist(
    el
  )
  V(G)$type <- case_when(
    !is.na(strtoi(V(G)$name)) ~ "literal",
    str_detect(V(G)$name, "^NOT") ~ "not",
    str_detect(V(G)$name, "_LSHIFT_") ~ "lshift",
    str_detect(V(G)$name, "_RSHIFT_") ~ "rshift",
    str_detect(V(G)$name, "_AND_") ~ "and",
    str_detect(V(G)$name, "_OR_") ~ "or",
    TRUE ~ "var"
  )
  G
}

calculate_wires <- function(G) {
  V(G)$value <- NA_integer_
  v_sorted <- topo_sort(G)
  for (vi in v_sorted) {
    me <- V(G)[vi]$name
    nbs <- neighbors(G, vi, "in")
    type <- V(G)[vi]$type
    if (type == "literal") {
      stopifnot(length(nbs) == 0L)
      ## it is a literal node with a value
      V(G)[vi]$value <- strtoi(V(G)[vi]$name)
    } else if (type == "var") {
      stopifnot(length(nbs) == 1L)
      V(G)[vi]$value <- nbs$value
    } else if (type == "not") {
      stopifnot(length(nbs) == 1L)
      V(G)[vi]$value <- bitwNot(nbs$value) %% 2 ^ 16
    } else if (type == "and") {
      stopifnot(length(nbs) == 2L)
      V(G)[vi]$value <- bitwAnd(nbs[1L]$value, nbs[2L]$value) %% 2L ^ 16L
    } else if (type == "or") {
      stopifnot(length(nbs) == 2L)
      V(G)[vi]$value <- bitwOr(nbs[1L]$value, nbs[2L]$value) %% 2L ^ 16L
    } else if (type == "lshift") {
      stopifnot(length(nbs) == 2L)
      parts <- str_split(me, "_[^_]+_") %>% 
        extract2(1L)
      nbs <- nbs[match(nbs$name, parts)]
      V(G)[vi]$value <- bitwShiftL(nbs[1L]$value, nbs[2L]$value) %% 2L ^ 16L
    } else if (type == "rshift") {
      stopifnot(length(nbs) == 2L)
      parts <- str_split(me, "_[^_]+_") %>% 
        extract2(1L)
      nbs <- nbs[match(nbs$name, parts)]
      V(G)[vi]$value <- bitwShiftR(nbs[1L]$value, nbs[2L]$value) %% 2L ^ 16L
    }
  }
  G
}
  
G <- construct_graph(puzzle_data) %>% 
  calculate_wires()

(res <- V(G)["a"]$value)
## [1] 16076

2.2 Part 2

2.2.1 Description

— Part Two —

Now, take the signal you got on wire a, override wire b to that signal, and reset the other wires (including wire a). What new signal is ultimately provided to wire a?

2.2.2 Solution

We have to simply rename the incoming node to b to hold the result from part 1 and recalculate the graph.

rewire_graph <- function(G, new_val) {
  b_in <- neighbors(G, "b", "in")
  V(G)[b_in]$name <- new_val
  G
}

G2 <- rewire_graph(G, res) %>% 
  calculate_wires()
V(G2)["a"]$value
## [1] 2797