1 Setup
1.1 Libraries
library(httr)
library(xml2)
library(magrittr)
library(tibble)
library(dplyr)
library(tidyr)
library(purrr)
library(stringr)
library(digest)1.2 Retrieve Data from AoC
session_cookie <- set_cookies(session = keyring::key_get("AoC-GitHub-Cookie"))
base_url <- paste0("https://adventofcode.com/2021/day/", params$task_nr)
puzzle <- GET(base_url,
session_cookie) %>%
content(encoding = "UTF-8") %>%
xml_find_all("///article") %>%
lapply(as.character)
puzzle_data <- local({
lines <- GET(paste0(base_url, "/input"),
session_cookie) %>%
content(encoding = "UTF-8") %>%
str_split("\n") %>%
`[[`(1L) %>%
Filter(nzchar, .)
idx <- lines %>%
str_which("^---")
map2(idx + 1L,
c(tail(idx, -1L) - 1L, length(lines)),
~ lines[.x:.y] %>%
str_split(",") %>%
do.call(rbind, .) %>%
{matrix(as.numeric(.), nrow(.))})
})2 Puzzle Day 19
2.1 Part 1
2.1.1 Description
— Day 19: Beacon Scanner —
As your probe drifted down through this area, it released an assortment of beacons and scanners into the water. It’s difficult to navigate in the pitch black open waters of the ocean trench, but if you can build a map of the trench using data from the scanners, you should be able to safely reach the bottom.
The beacons and scanners float motionless in the water; they’re designed to maintain the same position for long periods of time. Each scanner is capable of detecting all beacons in a large cube centered on the scanner; beacons that are at most 1000 units away from the scanner in each of the three axes (x, y, and z) have their precise position determined relative to the scanner. However, scanners cannot detect other scanners. The submarine has automatically summarized the relative positions of beacons detected by each scanner (your puzzle input).
For example, if a scanner is at x,y,z coordinates 500,0,-500 and there are beacons at -500,1000,-1500 and 1501,0,-500, the scanner could report that the first beacon is at -1000,1000,-1000 (relative to the scanner) but would not detect the second beacon at all.
Unfortunately, while each scanner can report the positions of all detected beacons relative to itself, the scanners do not know their own position. You’ll need to determine the positions of the beacons and scanners yourself.
The scanners and beacons map a single contiguous 3d region. This region can be reconstructed by finding pairs of scanners that have overlapping detection regions such that there are at least 12 beacons that both scanners detect within the overlap. By establishing 12 common beacons, you can precisely determine where the scanners are relative to each other, allowing you to reconstruct the beacon map one scanner at a time.
For a moment, consider only two dimensions. Suppose you have the following scanner reports:
--- scanner 0 ---
0,2
4,1
3,3
--- scanner 1 ---
-1,-1
-5,0
-2,1
Drawing x increasing rightward, y increasing upward, scanners as S, and beacons as B, scanner 0 detects this:
...B.
B....
....B
S....
Scanner 1 detects this:
...B..
B....S
....B.
For this example, assume scanners only need 3 overlapping beacons. Then, the beacons visible to both scanners overlap to produce the following complete map:
...B..
B....S
....B.
S.....
Unfortunately, there’s a second problem: the scanners also don’t know their rotation or facing direction. Due to magnetic alignment, each scanner is rotated some integer number of 90-degree turns around all of the x, y, and z axes. That is, one scanner might call a direction positive x, while another scanner might call that direction negative y. Or, two scanners might agree on which direction is positive x, but one scanner might be upside-down from the perspective of the other scanner. In total, each scanner could be in any of 24 different orientations: facing positive or negative x, y, or z, and considering any of four directions “up” from that facing.
For example, here is an arrangement of beacons as seen from a scanner in the same position but in different orientations:
--- scanner 0 ---
-1,-1,1
-2,-2,2
-3,-3,3
-2,-3,1
5,6,-4
8,0,7
--- scanner 0 ---
1,-1,1
2,-2,2
3,-3,3
2,-1,3
-5,4,-6
-8,-7,0
--- scanner 0 ---
-1,-1,-1
-2,-2,-2
-3,-3,-3
-1,-3,-2
4,6,5
-7,0,8
--- scanner 0 ---
1,1,-1
2,2,-2
3,3,-3
1,3,-2
-4,-6,5
7,0,8
--- scanner 0 ---
1,1,1
2,2,2
3,3,3
3,1,2
-6,-4,-5
0,7,-8
By finding pairs of scanners that both see at least 12 of the same beacons, you can assemble the entire map. For example, consider the following report:
--- scanner 0 ---
404,-588,-901
528,-643,409
-838,591,734
390,-675,-793
-537,-823,-458
-485,-357,347
-345,-311,381
-661,-816,-575
-876,649,763
-618,-824,-621
553,345,-567
474,580,667
-447,-329,318
-584,868,-557
544,-627,-890
564,392,-477
455,729,728
-892,524,684
-689,845,-530
423,-701,434
7,-33,-71
630,319,-379
443,580,662
-789,900,-551
459,-707,401
--- scanner 1 ---
686,422,578
605,423,415
515,917,-361
-336,658,858
95,138,22
-476,619,847
-340,-569,-846
567,-361,727
-460,603,-452
669,-402,600
729,430,532
-500,-761,534
-322,571,750
-466,-666,-811
-429,-592,574
-355,545,-477
703,-491,-529
-328,-685,520
413,935,-424
-391,539,-444
586,-435,557
-364,-763,-893
807,-499,-711
755,-354,-619
553,889,-390
--- scanner 2 ---
649,640,665
682,-795,504
-784,533,-524
-644,584,-595
-588,-843,648
-30,6,44
-674,560,763
500,723,-460
609,671,-379
-555,-800,653
-675,-892,-343
697,-426,-610
578,704,681
493,664,-388
-671,-858,530
-667,343,800
571,-461,-707
-138,-166,112
-889,563,-600
646,-828,498
640,759,510
-630,509,768
-681,-892,-333
673,-379,-804
-742,-814,-386
577,-820,562
--- scanner 3 ---
-589,542,597
605,-692,669
-500,565,-823
-660,373,557
-458,-679,-417
-488,449,543
-626,468,-788
338,-750,-386
528,-832,-391
562,-778,733
-938,-730,414
543,643,-506
-524,371,-870
407,773,750
-104,29,83
378,-903,-323
-778,-728,485
426,699,580
-438,-605,-362
-469,-447,-387
509,732,623
647,635,-688
-868,-804,481
614,-800,639
595,780,-596
--- scanner 4 ---
727,592,562
-293,-554,779
441,611,-461
-714,465,-776
-743,427,-804
-660,-479,-426
832,-632,460
927,-485,-438
408,393,-506
466,436,-512
110,16,151
-258,-428,682
-393,719,612
-211,-452,876
808,-476,-593
-575,615,604
-485,667,467
-680,325,-822
-627,-443,-432
872,-547,-609
833,512,582
807,604,487
839,-516,451
891,-625,532
-652,-548,-490
30,-46,-14
Because all coordinates are relative, in this example, all “absolute” positions will be expressed relative to scanner 0 (using the orientation of scanner 0 and as if scanner 0 is at coordinates 0,0,0).
Scanners 0 and 1 have overlapping detection cubes; the 12 beacons they both detect (relative to scanner 0) are at the following coordinates:
-618,-824,-621
-537,-823,-458
-447,-329,318
404,-588,-901
544,-627,-890
528,-643,409
-661,-816,-575
390,-675,-793
423,-701,434
-345,-311,381
459,-707,401
-485,-357,347
These same 12 beacons (in the same order) but from the perspective of scanner 1 are:
686,422,578
605,423,415
515,917,-361
-336,658,858
-476,619,847
-460,603,-452
729,430,532
-322,571,750
-355,545,-477
413,935,-424
-391,539,-444
553,889,-390
Because of this, scanner 1 must be at 68,-1246,-43 (relative to scanner 0).
Scanner 4 overlaps with scanner 1; the 12 beacons they both detect (relative to scanner 0) are:
459,-707,401
-739,-1745,668
-485,-357,347
432,-2009,850
528,-643,409
423,-701,434
-345,-311,381
408,-1815,803
534,-1912,768
-687,-1600,576
-447,-329,318
-635,-1737,486
So, scanner 4 is at -20,-1133,1061 (relative to scanner 0).
Following this process, scanner 2 must be at 1105,-1205,1229 (relative to scanner 0) and scanner 3 must be at -92,-2380,-20 (relative to scanner 0).
The full list of beacons (relative to scanner 0) is:
-892,524,684
-876,649,763
-838,591,734
-789,900,-551
-739,-1745,668
-706,-3180,-659
-697,-3072,-689
-689,845,-530
-687,-1600,576
-661,-816,-575
-654,-3158,-753
-635,-1737,486
-631,-672,1502
-624,-1620,1868
-620,-3212,371
-618,-824,-621
-612,-1695,1788
-601,-1648,-643
-584,868,-557
-537,-823,-458
-532,-1715,1894
-518,-1681,-600
-499,-1607,-770
-485,-357,347
-470,-3283,303
-456,-621,1527
-447,-329,318
-430,-3130,366
-413,-627,1469
-345,-311,381
-36,-1284,1171
-27,-1108,-65
7,-33,-71
12,-2351,-103
26,-1119,1091
346,-2985,342
366,-3059,397
377,-2827,367
390,-675,-793
396,-1931,-563
404,-588,-901
408,-1815,803
423,-701,434
432,-2009,850
443,580,662
455,729,728
456,-540,1869
459,-707,401
465,-695,1988
474,580,667
496,-1584,1900
497,-1838,-617
527,-524,1933
528,-643,409
534,-1912,768
544,-627,-890
553,345,-567
564,392,-477
568,-2007,-577
605,-1665,1952
612,-1593,1893
630,319,-379
686,-3108,-505
776,-3184,-501
846,-3110,-434
1135,-1161,1235
1243,-1093,1063
1660,-552,429
1693,-557,386
1735,-437,1738
1749,-1800,1813
1772,-405,1572
1776,-675,371
1779,-442,1789
1780,-1548,337
1786,-1538,337
1847,-1591,415
1889,-1729,1762
1994,-1805,1792
In total, there are 79 beacons.
Assemble the full map of beacons. How many beacons are there?
2.1.2 Solution
In a first step we have to find out which beacons any 2 scanners have in common. Since we do not have a reference point, we will calculate all distances between each beacon and match according to this distance. This works nicely, as the distance is invariant to any rotation (we do not stretch).
If, for instance, beacons 1 and 2 are 123.45 units apart for scanner 1,
and beacons 4 and 14 are also 123.45 units apart, we can conclude that
beacons map as follows between scanner 1 and 2: 1->4 and 2->14.
Once we established the common beacons, we have to apply all possible rotations and check if the difference between the common beacons of scanner 1 and the beacons of the rotated scanner 2 became constant across all beacons. This yields the offset between scanner 1 and 2.
We apply this idea to the initial list of scanners to get all scanners which have beacons in common with scanner 1. These scanners are removed from the list of unmatched scanners. If the list of unmatched scanners is not empty yet, we continue with the first element in the list of matched scanners after scanner 1. In this way we will eventually match all scanners. All we have to do then is to align all scanners by recursively applying the rotation and adding the offset and count the unique beacons.
rotate <- function(alpha, beta, gamma) {
c(cos(beta) * cos(gamma),
cos(beta) * sin(gamma),
-sin(beta),
sin(alpha) * sin(beta) * cos(gamma) - cos(alpha) * sin(gamma),
sin(alpha) * sin(beta) * sin(gamma) + cos(alpha) * cos(gamma),
sin(alpha) * cos(beta),
cos(alpha) * sin(beta) * cos(gamma) + sin(alpha) * sin(gamma),
cos(alpha) * sin(beta) * sin(gamma) - sin(alpha) * cos(gamma),
cos(alpha) * cos(beta)) %>%
round(0) %>%
as.integer() %>%
matrix(3, 3)
}
angle <- 0:3 * pi / 2
par <- expand.grid(alpha = angle, beta = angle, gamma = angle) %>%
as_tibble()
## remove identical rotation matrices
rot_mat <- par %>%
pmap(rotate) %>%
`[`(!duplicated(.))
match_scanners <- function(coords1, coords2) {
## get pairwise distances
d1 <- dist(coords1)
d2 <- dist(coords2)
## find out how many matching distances there are per beacon
nr_matches <- d1 %>%
as.matrix() %>%
{`dim<-`(. %in% d2, dim(.))} %>%
colSums()
if (sum(rel_beacons <- nr_matches == 11L) >= 12L) {
## if we have at least 12 matching beacons...
## ... reduce first scanner results to these
c1 <- coords1[rel_beacons, ]
## ... recalculate the distances for the matching beacons
rel_dist <- dist(c1)
## for each of these distances get row and col in the second
## distance matrix
match_coords <- map(rel_dist[seq(1L, nrow(c1) - 1L)],
~ which(`dim<-`(as.matrix(d2) == .x,
dim(as.matrix(d2))),
arr.ind = TRUE))
## however, for each matching we will get 2 positions (matrix is symmetric)
## chose the one which occurs everywhere and bring it to long format
match_coords <- match_coords %>%
reduce(~ inner_join(as_tibble(.x),
as_tibble(.y),
"row")) %>%
pivot_longer(everything())
## now match_coords$value contains the beacons in order for the second
## scanner
c2 <- coords2[match_coords$value, ]
stopifnot(isTRUE(all.equal(dist(c1), dist(c2), check.attributes = FALSE)))
## c1 and c2 are not the common beacons and also aligned
## find proper rotation such that diff is constant
for (rm in rot_mat) {
offset <- c1 - c2 %*% rm
if (sum(!duplicated(offset)) == 1L) {
## we have one single offset
break;
}
}
stopifnot(all.equal(c1, t(t(c2 %*% rm) + offset[1, ])))
res <- tibble(base = digest(coords1),
self = digest(coords2),
orig = list(coords2),
offset = list(matrix(offset[1, ], 1, 3)),
rotation = list(rm))
} else {
## no matching beacons
res <- tibble(base = list(), self = list(), orig = list(),
offset = list(), rotation = list())
}
res
}
remove_from_list <- function(lst, el) {
dupes <- !duplicated(c(list(el), lst))
lst[tail(dupes, -1L)]
}
rebase <- function(res) {
get_value <- function(hash, what) {
res %>% filter(self == hash) %>%
pull(what) %>%
`[[`(1L)
}
## each scanner is relative to another scanner, that is
## self->base, we follow these path until we reach the
## baseline
lkp <- res %>%
pull(base) %>%
set_names(res %>% pull(self))
base0 <- lkp[lkp == names(lkp)]
new_offsets <- new_rotations <- vector("list", nrow(res)) %>%
set_names(names(lkp))
for (hash in names(lkp)) {
orig_hash <- hash
offset <- get_value(hash, "offset")
rm <- get_value(hash, "rotation")
while (hash != base0) {
## we follow the path at each offset is already in terms of
## coordinates of the new base, that is we have first to
## rotate the old offsets to align them to the new base
## and then add the offset of this base (which is already in
## coorindates of the base of this base)
hash <- lkp[hash]
offset <- (offset %*% get_value(hash, "rotation")) +
get_value(hash, "offset")
## also rotate the rotation matrix such that in the end offset
## and rotation are relative to base0
rm <- rm %*% get_value(hash, "rotation")
}
new_offsets[[orig_hash]] <- offset
new_rotations[[orig_hash]] <- rm
}
res %>%
mutate(offset = new_offsets,
rotation = new_rotations)
}
count_unique_beacons <- function(res) {
## we need to pass the rebased offsets and rotations,
## then all we have to is to rotate and add the offset
shift <- function(orig, offset, rotation, ...) {
t(t(orig %*% rotation) + c(offset))
}
## and count the number of unique beacons
pmap(res, shift) %>%
do.call(rbind, .) %>%
unique() %>%
nrow()
}
get_all_offsets <- function(scanner_data = puzzle_data) {
## start wiht the first scanner
matched <- head(scanner_data, 1L)
## all other scanners are unmatched
unmatched <- tail(scanner_data, -1L)
offsets <- vector("list", length(scanner_data))
idx <- 1L
coords0 <- tail(matched, 1L)[[1L]]
offsets[[1L]] <- tibble(base = digest(coords0), self = digest(coords0),
orig = list(coords0),
offset = list(matrix(rep(0, 3), 1, 3)),
rotation = list(diag(3)))
while (length(unmatched)) {
## while there are unmatched sensors, pop the last matched sensor
coords0 <- tail(matched, 1L)[[1L]]
matched <- head(matched, -1L)
for (coords1 in unmatched) {
## and loop through all unmatched sensors
res <- match_scanners(coords0, coords1)
if (nrow(res)) {
## if we find a match
idx <- idx + 1L
offsets[[idx]] <- res
## store the results and rmeove the matched sensor from
## the unmatched list
## N.B. to later identify sensors we hash them to be able
## to walk back eventually to base0
matched <- c(matched, list(coords1))
unmatched <- remove_from_list(unmatched, coords1)
}
}
}
do.call(rbind, offsets)
}
coords <- get_all_offsets() %>%
rebase()
coords %>%
count_unique_beacons()## [1] 3182.2 Part 2
2.2.1 Description
— Part Two —
Sometimes, it’s a good idea to appreciate just how big the ocean is. Using the Manhattan distance, how far apart do the scanners get?
In the above example, scanners 2 (1105,-1205,1229) and 3 (-92,-2380,-20) are the largest Manhattan distance apart. In total, they are 1197 + 1175 + 1249 = 3621 units apart.
What is the largest Manhattan distance between any two scanners?
2.2.2 Solution
As we calculated already the relative positions of the scanners for part 1, all we need to do is to get all pairwise distances.
outer(coords$offset,
coords$offset,
\(x, y) map2_dbl(x, y, ~ sum(abs(.x - .y)))) %>%
max()## [1] 12166