Task 11

Thorn Thaler - <

2026-02-24

1 Setup

1.1 Libraries

library(httr)
library(xml2)
library(magrittr)
library(dplyr)
library(purrr)
library(stringr)
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)
  }
  text_block[nzchar(text_block)] %>% 
    str_split(": |\\s") %>% 
    map(~ tibble(from = .x[[1]], to = .x[-1])) %>% 
    list_rbind()
}

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

2 Puzzle Day 11

2.1 Part 1

2.1.1 Description

— Day 11: Reactor —

You hear some loud beeping coming from a hatch in the floor of the factory, so you decide to check it out. Inside, you find several large electrical conduits and a ladder.

Climbing down the ladder, you discover the source of the beeping: a large, toroidal reactor which powers the factory above. Some Elves here are hurriedly running between the reactor and a nearby server rack, apparently trying to fix something.

One of the Elves notices you and rushes over. “It’s a good thing you’re here! We just installed a new server rack, but we aren’t having any luck getting the reactor to communicate with it!” You glance around the room and see a tangle of cables and devices running from the server rack to the reactor. She rushes off, returning a moment later with a list of the devices and their outputs (your puzzle input).

For example: 

aaa: you hhh
you: bbb ccc
bbb: ddd eee
ccc: ddd eee fff
ddd: ggg
eee: out
fff: out
ggg: out
hhh: ccc fff iii
iii: out

Each line gives the name of a device followed by a list of the devices to which its outputs are attached. So, bbb: ddd eee means that device bbb has two outputs, one leading to device ddd and the other leading to device eee.

The Elves are pretty sure that the issue isn’t due to any specific device, but rather that the issue is triggered by data following some specific path through the devices. Data only ever flows from a device through its outputs; it can’t flow backwards.

After dividing up the work, the Elves would like you to focus on the devices starting with the one next to you (an Elf hastily attaches a label which just says you) and ending with the main output to the reactor (which is the device with the label out).

To help the Elves figure out which path is causing the issue, they need you to find every path from you to out.

In this example, these are all of the paths from you to out:

  • Data could take the connection from you to bbb, then from bbb to ddd, then from ddd to ggg, then from ggg to out.
  • Data could take the connection to bbb, then to eee, then to out.
  • Data could go to ccc, then ddd, then ggg, then out.
  • Data could go to ccc, then eee, then out.
  • Data could go to ccc, then fff, then out.

In total, there are 5 different paths leading from you to out.

How many different paths lead from you to out?

2.1.2 Solution

We can solve the first part of the puzzle by first creating a directed graph from the input data. Then we set the weight for the target node to 1 and all other nodes to NA. We can then iterate through the nodes in reverse topological order and set the weight of each node to the sum of the weights of its outgoing neighbors. Finally, we return the weight of the start node.

count_paths <- function(G, start, goal) {
  sg <- intersect(
    subcomponent(G, start, mode = "out"),
    subcomponent(G, goal, mode = "in")
  )
  if (length(sg) == 0) {
    return(0L)
  }
  G <- induced_subgraph(G, sg)
  V(G)$nr_path <- NA_real_
  V(G)[goal]$nr_path <- 1
  for (v in rev(topo_sort(G))) {
    if (V(G)[v]$name != goal) {
      V(G)[v]$nr_path <- sum(V(G)[neighbors(G, v, mode = "out")]$nr_path)
    }
  }
  V(G)[start]$nr_path
}

G <- graph_from_data_frame(puzzle_data, directed = TRUE)
count_paths(G, "you", "out")
## [1] 466

2.2 Part 2

2.2.1 Description

— Part Two —

Thanks in part to your analysis, the Elves have figured out a little bit about the issue. They now know that the problematic data path passes through both dac (a digital-to-analog converter) and fft (a device which performs a fast Fourier transform).

They’re still not sure which specific path is the problem, and so they now need you to find every path from svr (the server rack) to out. However, the paths you find must all also visit both dac and fft (in any order).

For example: 

svr: aaa bbb
aaa: fft
fft: ccc
bbb: tty
tty: ccc
ccc: ddd eee
ddd: hub
hub: fff
eee: dac
dac: fff
fff: ggg hhh
ggg: out
hhh: out

This new list of devices contains many paths from svr to out: 

svr,aaa,fft,ccc,ddd,hub,fff,ggg,out
svr,aaa,fft,ccc,ddd,hub,fff,hhh,out
svr,aaa,fft,ccc,eee,dac,fff,ggg,out
svr,aaa,fft,ccc,eee,dac,fff,hhh,out
svr,bbb,tty,ccc,ddd,hub,fff,ggg,out
svr,bbb,tty,ccc,ddd,hub,fff,hhh,out
svr,bbb,tty,ccc,eee,dac,fff,ggg,out
svr,bbb,tty,ccc,eee,dac,fff,hhh,out

However, only 2 paths from svr to out visit both dac and fft.

Find all of the paths that lead from svr to out. How many of those paths visit both dac and fft?

2.2.2 Solution

To count all paths which passes through both fft and dac we can use the following formula: \[ \#(\text{svr} \to \text{fft}) \cdot \#(\text{fft} \to \text{dac}) \cdot \#(\text{dac} \to \text{out}) + \#(\text{svr} \to \text{dac}) \cdot \#(\text{dac} \to \text{fft}) \cdot \#(\text{fft} \to \text{out}) \] That is we first count all paths between \(\text{svr} \to \text{fft}\), \(\text{fft} \to \text{dac}\) and \(\text{dac} \to \text{out}\) and multiply them. This counts all paths which passes first through fft and then through dac. We do the same for the paths which passes first through dac and then through fft and add the two results together.

count_paths_through <- function(G, path) {
  stopifnot(length(path) == 4L)
  start <- path[1L]
  i1 <- path[2L]
  i2 <- path[3L]
  end <- path[4L]
  
  count_paths(G, start, i1) *
    count_paths(G, i1, i2) *
    count_paths(G, i2, end) +
    count_paths(G, start, i2) *
    count_paths(G, i2, i1) *
    count_paths(G, i1, end)
}

count_paths_through(G, c("svr", "fft", "dac", "out")) %>% 
  print(digits = 16L)
## [1] 549705036748518