Advent of Code: Day 14

• Problem

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) %>%
        add_column(val = as.vector(mat)) %>%
        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