Task 23

2025-11-07

1 Setup

1.1 Libraries

library(httr)
library(xml2)
library(magrittr)
library(dplyr)
library(purrr)
library(stringr)

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_extract_all("-?\\d+") %>% 
    do.call(rbind, .) %>% 
    set_colnames(c("x", "y", "z", "r")) %>% 
    as_tibble() %>% 
    mutate(across(x:r, as.integer))
}

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

2 Puzzle Day 23

2.1 Part 1

2.1.1 Description

— Day 23: Experimental Emergency Teleportation —

Using your torch to search the darkness of the rocky cavern, you finally locate the man’s friend: a small reindeer.

You’re not sure how it got so far in this cave. It looks sick - too sick to walk - and too heavy for you to carry all the way back. Sleighs won’t be invented for another 1500 years, of course.

The only option is experimental emergency teleportation.

You hit the “experimental emergency teleportation” button on the device and push I accept the risk on no fewer than 18 different warning messages. Immediately, the device deploys hundreds of tiny nanobots which fly around the cavern, apparently assembling themselves into a very specific formation. The device lists the X,Y,Z position (pos) for each nanobot as well as its signal radius (r) on its tiny screen (your puzzle input).

Each nanobot can transmit signals to any integer coordinate which is a distance away from it less than or equal to its signal radius (as measured by Manhattan distance). Coordinates a distance away of less than or equal to a nanobot’s signal radius are said to be in range of that nanobot.

Before you start the teleportation process, you should determine which nanobot is the strongest (that is, which has the largest signal radius) and then, for that nanobot, the total number of nanobots that are in range of it, including itself.

For example, given the following nanobots:

pos=<0,0,0>, r=4
pos=<1,0,0>, r=1
pos=<4,0,0>, r=3
pos=<0,2,0>, r=1
pos=<0,5,0>, r=3
pos=<0,0,3>, r=1
pos=<1,1,1>, r=1
pos=<1,1,2>, r=1
pos=<1,3,1>, r=1

The strongest nanobot is the first one (position 0,0,0) because its signal radius, 4 is the largest. Using that nanobot’s location and signal radius, the following nanobots are in or out of range:

The nanobot at 0,0,0 is distance 0 away, and so it is in range.
The nanobot at 1,0,0 is distance 1 away, and so it is in range.
The nanobot at 4,0,0 is distance 4 away, and so it is in range.
The nanobot at 0,2,0 is distance 2 away, and so it is in range.
The nanobot at 0,5,0 is distance 5 away, and so it is not in range.
The nanobot at 0,0,3 is distance 3 away, and so it is in range.
The nanobot at 1,1,1 is distance 3 away, and so it is in range.
The nanobot at 1,1,2 is distance 4 away, and so it is in range.
The nanobot at 1,3,1 is distance 5 away, and so it is not in range.

In this example, in total, 7 nanobots are in range of the nanobot with the largest signal radius.

Find the nanobot with the largest signal radius. How many nanobots are in range of its signals?

2.1.2 Solution

The first part is straight forward: 1. Sort the nanobots by their radius. 1. Get the distance from each nanobot form the most powerful nanobot. 1. Count how many nanobots are within the range of the first nanobot.

count_nanobots <- function(bots = puzzle_data) {
  bots <- bots %>% 
    arrange(desc(r)) %>% 
    as.matrix()
  ref <- bots[1L, , drop = TRUE] 
  dis <- sweep(bots[, -4L], 2, ref[-4L], function(pos, ref) abs(pos - ref)) %>% 
    rowSums()
  sum(dis <= ref[4L])
}
count_nanobots(puzzle_data)

## [1] 309

2.2 Part 2

2.2.1 Description

— Part Two —

Now, you just need to figure out where to position yourself so that you’re actually teleported when the nanobots activate.

To increase the probability of success, you need to find the coordinate which puts you in range of the largest number of nanobots. If there are multiple, choose one closest to your position (0,0,0, measured by manhattan distance).

For example, given the following nanobot formation:

pos=<10,12,12>, r=2
pos=<12,14,12>, r=2
pos=<16,12,12>, r=4
pos=<14,14,14>, r=6
pos=<50,50,50>, r=200
pos=<10,10,10>, r=5

Many coordinates are in range of some of the nanobots in this formation. However, only the coordinate 12,12,12 is in range of the most nanobots: it is in range of the first five, but is not in range of the nanobot at 10,10,10. (All other coordinates are in range of fewer than five nanobots.) This coordinate’s distance from 0,0,0 is 36.

Find the coordinates that are in range of the largest number of nanobots. What is the shortest manhattan distance between any of those points and 0,0,0?

2.2.2 Solution

For the second part we fall back to C++ to be faster. The algorithm follows this idea:

First transform the coordinates of each cube to be parallel to the exes.
Then create a vector of all coordinates on the border of each cube. As we have now axes parallel cubes it is guaranteed that the best point must be on the border (as we are looking for the point closest to the origin).
As there are too many combinations of border points, we sample from those using a step size of 10 and find the point which intersects with the most cubes as a first approximation.
Finally, we look in the neighborhood of this first approximation using a diameter of
For each point in this cube, we re-calculate the coverage, and if it is better than the first approximation we update the results accordingly.
Eventually we return the sum of the coordinates of this point which corresponds to the Manhattan distance from the origin.

#ifndef STANDALONE
#include <Rcpp.h>
using namespace Rcpp;
#else
#include <iostream>
#endif
#include <algorithm>
#include <cmath>
#include <tuple>
#include <vector>

struct Ball {
    long long x, y, z, r;
};

std::pair<std::vector<int>, long long> count_nanobots(std::vector<Ball> balls,
                                                      int coarse_grid = 10,
                                                      int fine_grid = 50) {
  size_t n = balls.size();
  std::vector<long long> coords1, coords2, coords3;
  coords1.reserve(2 * n);
  coords2.reserve(2 * n);
  coords3.reserve(2 * n);
  // transform centers to u-coordinates (axes parallel)
  for (size_t i = 0; i < n; ++i) {
    long long x = balls[i].x, y = balls[i].y, z = balls[i].z, r = balls[i].r;
    long long u1 = x + y + z;
    long long u2 = x + y - z;
    long long u3 = x - y + z;
    coords1.push_back(u1 - r);
    coords1.push_back(u1 + r);
    coords2.push_back(u2 - r);
    coords2.push_back(u2 + r);
    coords3.push_back(u3 - r);
    coords3.push_back(u3 + r);
  }

  // create sorted list without duplicates
  auto compress = [](std::vector<long long>& v) {
    std::sort(v.begin(), v.end());
    v.erase(std::unique(v.begin(), v.end()), v.end());
    return v;
  };

  // check if point inside L1-ball
  auto is_in_ball = [](long long x, long long y, long long z, const Ball& b) {
    return llabs(x - b.x) + llabs(y - b.y) + llabs(z - b.z) <= b.r;
  };

  // back transformation u->(x,y,z)
  auto inv_from_u = [](long long u1, long long u2, long long u3) {
    // x=(u2+u3)/2, y=(u1-u3)/2, z=(u1-u2)/2
    if (((u2 + u3) & 1) || ((u1 - u3) & 1) || ((u1 - u2) & 1)) {
      // x, y or z is not an integer
      return std::make_tuple(false, 0LL, 0LL, 0LL);
    }
    long long x = (u2 + u3) / 2;
    long long y = (u1 - u3) / 2;
    long long z = (u1 - u2) / 2;
    return std::make_tuple(true, x, y, z);
  };

  // update best point if needed
  auto update_best_point = [balls, is_in_ball](
                               long long x,
                               long long y,
                               long long z,
                               long long& best_count,
                               long long& best_dist,
                               std::tuple<long long, long long, long long>& best_point) {
    long long count = 0;
    for (auto& b : balls) {
      if (is_in_ball(x, y, z, b)) {
        ++count;
      }
    }
    long long dist = llabs(x) + llabs(y) + llabs(z);
    if (count > best_count || (count == best_count && dist < best_dist)) {
      best_count = count;
      best_dist = dist;
      best_point = std::make_tuple(x, y, z);
    }
  };

  coords1 = compress(coords1);
  coords2 = compress(coords2);
  coords3 = compress(coords3);

  long long best_count = -1, best_dist = LLONG_MAX;
  std::tuple<long long, long long, long long> best_point(0, 0, 0);

  // Phase 1: Coarse search, sample points from all borders
  std::vector<long long> c1, c2, c3;
  for (size_t i = 0; i < coords1.size(); i += coarse_grid) {
    c1.push_back(coords1[i]);
  }
  for (size_t i = 0; i < coords2.size(); i += coarse_grid) {
    c2.push_back(coords2[i]);
  }
  for (size_t i = 0; i < coords3.size(); i += coarse_grid) {
    c3.push_back(coords3[i]);
  }
  long long x, y, z;
  for (long long u1 : c1) {
    for (long long u2 : c2) {
      for (long long u3 : c3) {
        bool ok;
        std::tie(ok, x, y, z) = inv_from_u(u1, u2, u3);
        if (!ok) {
          continue;
        }
        update_best_point(x, y, z, best_count, best_dist, best_point);
      }
    }
  }

  // Phase 2: Refinement
  if (coarse_grid > 1) {
    auto [bx, by, bz] = best_point;
    for (int dx = -fine_grid; dx <= fine_grid; ++dx) {
      for (int dy = -fine_grid; dy <= fine_grid; ++dy) {
        for (int dz = -fine_grid; dz <= fine_grid; ++dz) {
          x = bx + dx;
          y = by + dy;
          z = bz + dz;
          update_best_point(x, y, z, best_count, best_dist, best_point);
        }
      }
    }
  }
  std::vector<int> pos(3);
  pos[0] = std::get<0>(best_point);
  pos[1] = std::get<1>(best_point);
  pos[2] = std::get<2>(best_point);
  return std::make_pair(pos, best_count);
}
#ifndef STANDALONE

// [[Rcpp::export]]
List count_nanobots(const IntegerMatrix& bots, int coarse_grid = 10, int fine_grid = 50) {
  size_t n = bots.nrow();
  std::vector<Ball> balls(n);
  for (size_t i = 0; i < n; ++i) {
    balls[i].x = bots(i, 0);
    balls[i].y = bots(i, 1);
    balls[i].z = bots(i, 2);
    balls[i].r = bots(i, 3);
  }
  auto result = count_nanobots(balls, coarse_grid, fine_grid);
  return List::create(Named("pos") = result.first, Named("count") = result.second);
}

#else
int main() {
  std::vector<Ball> balls = {{10, 12, 12, 2},
                             {12, 14, 12, 2},
                             {16, 12, 12, 4},
                             {14, 14, 14, 6},
                             {50, 50, 50, 200},
                             {10, 10, 10, 5}};
  auto result = count_nanobots(balls, 1, 1);
  for (int i = 0; i < result.first.size(); ++i) {
    std::cout << result.first[i] << " ";
  }
  return 0;
}
#endif

coarse_step_size <- 10L
fine_grid <- 50L
sum(count_nanobots(as.matrix(puzzle_data), coarse_step_size, fine_grid)$pos)

## [1] 119011326