# Advent of Code: Day 14

For part 1, I repurposed the code written for day 10 to get the knot-hash. For part 2, I decided to approach the problem using `igraph` again. It’s not very efficient (it takes about 4 minutes) on my laptop to build the tree but it seems that it would have taken me a long time to come up with an algorithm that did the job.

# Part 1

``````library(BMS) # for hex2bin

split_by_n <- function(x, n, ...) {
split(x, ceiling(seq_along(x)/n), ...)
}

knot_hash <- function(input) {
input <- strtoi(charToRaw(input), 16L)
extra <- as.numeric(strsplit("17, 31, 73, 47, 23", ", ")[[1]])
input <- c(input, extra)
skip <- 0
cur_pos <- 1
fixed <- 0:255
for (j in 1:64) {
for (i in seq_along(input)) {
indices <- cur_pos - 1 + seq_len(input[i])
prev_indices <- indices
indices[indices > length(fixed)] <-
indices[indices > length(fixed)] - length(fixed)
fixed[indices] <- rev(fixed[indices])
cur_pos <- cur_pos + input[i] + skip
while (cur_pos  > length(fixed)) {
cur_pos <- cur_pos - length(fixed)
}
skip <- skip + 1
}
}
fixed <- split_by_n(fixed, 16)
res <- lapply(fixed, function(x) Reduce(bitwXor, x))
res <- vapply(res, function(x) sprintf("%.2x", x), character(1))
paste(res, collapse = "")
}

part1 <- sapply(paste("nbysizxe", 0:127, sep = "-"),
function(x) hex2bin(knot_hash(x)))
sum(part1)
``````
``````## [1] 8216
``````

# Part 2

``````library(igraph)
library(tidyverse)

get_index <- function(.i, .j, m) {
.i + (.j - 1) * m
}

get_neighbor_coords <- function(.i, .j, m) {
data_frame(
i = c(.i, .i, .i - 1, .i, .i + 1),
j = c(.j, .j - 1, .j, .j + 1, .j)
) %>%
filter(i > 0, j > 0,
i <= m, j <= m) %>%
mutate(idx = get_index(i, j, m))
}

build_graph <- function(mat) {
m <- dim(mat)[1]
res <- expand.grid(i = 1:m,
j = 1:m) %>%
mutate(
mat_idx = row_number(),
neigh = pmap(., function(i, j, ...) {
get_neighbor_coords(i, j, m)
})) %>%
unnest() %>%
mutate(val_n = pmap(., function(i1, j1, ...) mat[i1, j1]))

res %>%
filter(val == 1 & val_n == 1) %>%
select(mat_idx, idx) %>%
graph_from_data_frame()

}

part2 <- build_graph(part1)
components(part2)\$no
``````
``````## [1] 1139
``````

Tags:

Categories:

Updated: