1 Setup
1.1 Libraries
library(httr)
library(xml2)
library(magrittr)
library(dplyr)
library(purrr)
library(stringr)
library(igraph)
library(collections)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)
}
map <- text_block[nzchar(text_block)] %>%
str_split("") %>%
do.call(rbind, .)
start <- cbind(row = 1, col = which(map[1L, ] == "."))
goal <- cbind(row = nrow(map), col = which(map[nrow(map), ] == "."))
attr(map, "start") <- start
attr(map, "goal") <- goal
map
}
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: A Long Walk —
The Elves resume water filtering operations! Clean water starts flowing over the edge of Island Island.
They offer to help you go over the edge of Island Island, too! Just hold on tight to one end of this impossibly long rope and they’ll lower you down a safe distance from the massive waterfall you just created.
As you finally reach Snow Island, you see that the water isn’t really reaching the ground: it’s being absorbed by the air itself. It looks like you’ll finally have a little downtime while the moisture builds up to snow-producing levels. Snow Island is pretty scenic, even without any snow; why not take a walk?
There’s a map of nearby hiking trails (your puzzle input) that indicates paths (.), forest (#), and steep slopes (^, >, v, and <).
For example:
#.#####################
#.......#########...###
#######.#########.#.###
###.....#.>.>.###.#.###
###v#####.#v#.###.#.###
###.>...#.#.#.....#...#
###v###.#.#.#########.#
###...#.#.#.......#...#
#####.#.#.#######.#.###
#.....#.#.#.......#...#
#.#####.#.#.#########v#
#.#...#...#...###...>.#
#.#.#v#######v###.###v#
#...#.>.#...>.>.#.###.#
#####v#.#.###v#.#.###.#
#.....#...#...#.#.#...#
#.#########.###.#.#.###
#...###...#...#...#.###
###.###.#.###v#####v###
#...#...#.#.>.>.#.>.###
#.###.###.#.###.#.#v###
#.....###...###...#...#
#####################.#
You’re currently on the single path tile in the top row; your goal is to reach the single path tile in the bottom row. Because of all the mist from the waterfall, the slopes are probably quite icy; if you step onto a slope tile, your next step must be downhill (in the direction the arrow is pointing). To make sure you have the most scenic hike possible, never step onto the same tile twice. What is the longest hike you can take?
In the example above, the longest hike you can take is marked with O, and your starting position is marked S:
#S#####################
#OOOOOOO#########...###
#######O#########.#.###
###OOOOO#OOO>.###.#.###
###O#####O#O#.###.#.###
###OOOOO#O#O#.....#...#
###v###O#O#O#########.#
###...#O#O#OOOOOOO#...#
#####.#O#O#######O#.###
#.....#O#O#OOOOOOO#...#
#.#####O#O#O#########v#
#.#...#OOO#OOO###OOOOO#
#.#.#v#######O###O###O#
#...#.>.#...>OOO#O###O#
#####v#.#.###v#O#O###O#
#.....#...#...#O#O#OOO#
#.#########.###O#O#O###
#...###...#...#OOO#O###
###.###.#.###v#####O###
#...#...#.#.>.>.#.>O###
#.###.###.#.###.#.#O###
#.....###...###...#OOO#
#####################O#
This hike contains 94 steps. (The other possible hikes you could have taken were 90, 86, 82, 82, and 74 steps long.)
Find the longest hike you can take through the hiking trails listed on your map. How many steps long is the longest hike?
2.1.2 Solution
We construct a graph from the input data and then use a depth first search to find the longest path from the start to the goal. We also use a simple upper bound to prune the search space. The upper bound is based on the number of reachable nodes from the current node that have not been visited yet. The slides are handled by removing the edges that lead to invalid neighbors. This is done by checking the direction of the slide and removing the edges that lead to neighbors that are not in the direction of the slide. This way, we can ensure that we only consider valid paths when we encounter a slide.
The slides allow for an effective pruning of the search space, as they can lead to a large number of reachable nodes that are not valid. By removing the edges that lead to invalid neighbors, we can significantly reduce the number of nodes that we need to consider in our search, which can lead to a much faster solution.
construct_graph <- function(winter_map, use_slides) {
nr <- nrow(winter_map)
nc <- ncol(winter_map)
dirs <- rbind(
"^" = c(-1L, 0L),
">" = c(0L, 1L),
"v" = c(1L, 0L),
"<" = c(0L, -1L)
)
G <- make_lattice(c(nr, nc), directed = TRUE, mutual = TRUE)
V(G)$name <- c(outer(seq_len(nr), seq_len(nc), paste, sep = ","))
walls <- which(winter_map == "#", arr.ind = TRUE)
G <- delete_vertices(G, apply(walls, 1L, paste, collapse = ","))
if (use_slides) {
slides <- which(winter_map == "^" |
winter_map == ">" |
winter_map == "v" |
winter_map == "<", arr.ind = TRUE)
for (s in seq_len(nrow(slides))) {
slide_pos <- slides[s, , drop = FALSE]
slide_id <- paste(slide_pos[, 1L], slide_pos[, 2L], sep = ",")
slide_dir <- winter_map[slide_pos]
nbs <- slide_pos + dirs[slide_dir, ]
nbs_id <- paste(nbs[, 1L], nbs[, 2L], sep = ",")
invalid_nbs <- neighbors(G, slide_id, mode = "out") %>%
setdiff(V(G)[nbs_id])
G <- delete_edges(G, c(
paste(slide_id, invalid_nbs$name, sep = "|"),
paste(nbs_id, slide_id, sep = "|")
))
}
}
G
}
hike_map <- function(winter_map, use_slides) {
G <- construct_graph(winter_map, use_slides)
make_key <- function(node) {
paste(node[, 1L], node[, 2L], sep = ",")
}
dfs <- function(G, start, goal) {
upper_bound <- function(u) {
sum(!visited[reachable[[u]]])
}
d_goal <- distances(G, v = goal, mode = "in")
adj <- adjacent_vertices(G, V(G)) %>%
map(~ .x[order(d_goal[.x], decreasing = TRUE)])
reachable <- ego(G, order = vcount(G), mode = "out")
act_path <- best_path <- 0L
visited <- rep(FALSE, vcount(G))
stack <- stack()
stack$push(list(node = start, next_child = 1L))
visited[start] <- TRUE
while (stack$size() > 0L) {
state <- stack$peek()
node <- state$node
next_child <- state$next_child
if (node == goal) {
if (act_path > best_path) {
best_path <- act_path
}
stack$pop()
visited[node] <- FALSE
act_path <- act_path - 1L
next
}
remaining_max <- upper_bound(node)
if (act_path + remaining_max <= best_path) {
stack$pop()
visited[node] <- FALSE
act_path <- act_path - 1L
next
}
nbs <- adj[[node]]
if (next_child > length(nbs)) {
stack$pop()
visited[node] <- FALSE
act_path <- act_path - 1L
next
}
child <- nbs[next_child]
stack$pop()
stack$push(list(node = node, next_child = next_child + 1L))
if (!visited[child]) {
stack$push(list(node = child, next_child = 1L))
act_path <- act_path + 1L
visited[child] <- TRUE
}
}
return(best_path)
}
start <- attr(winter_map, "start")
goal <- attr(winter_map, "goal")
dfs(G, V(G)[make_key(start)], V(G)[make_key(goal)])
}
hike_map(puzzle_data, TRUE)## [1] 22102.2 Part 2
2.2.1 Description
— Part Two —
As you reach the trailhead, you realize that the ground isn’t as slippery as you expected; you’ll have no problem climbing up the steep slopes.
Now, treat all slopes as if they were normal paths (.). You still want to make sure you have the most scenic hike possible, so continue to ensure that you never step onto the same tile twice. What is the longest hike you can take?
In the example above, this increases the longest hike to 154 steps:
#S#####################
#OOOOOOO#########OOO###
#######O#########O#O###
###OOOOO#.>OOO###O#O###
###O#####.#O#O###O#O###
###O>...#.#O#OOOOO#OOO#
###O###.#.#O#########O#
###OOO#.#.#OOOOOOO#OOO#
#####O#.#.#######O#O###
#OOOOO#.#.#OOOOOOO#OOO#
#O#####.#.#O#########O#
#O#OOO#...#OOO###...>O#
#O#O#O#######O###.###O#
#OOO#O>.#...>O>.#.###O#
#####O#.#.###O#.#.###O#
#OOOOO#...#OOO#.#.#OOO#
#O#########O###.#.#O###
#OOO###OOO#OOO#...#O###
###O###O#O###O#####O###
#OOO#OOO#O#OOO>.#.>O###
#O###O###O#O###.#.#O###
#OOOOO###OOO###...#OOO#
#####################O#
Find the longest hike you can take through the surprisingly dry hiking trails listed on your map. How many steps long is the longest hike?
2.2.2 Solution
Theoretically, we could use the same approach as in part 1 and count the longest path in
the map where we have removed the slides. However, the search space is too large to be
solved in a reasonable time with R. Hence, we re-implement the solution in C++ and use
Rcpp to call the C++ function from R. The C++ implementation is a mere clone of the
R implementation, but it is significantly faster. Removing the slides basically prevents
any pruning of the search space, as we can no longer use the slides to effectively reduce
the number of reachable nodes. This means that we have to consider a much larger number of
nodes in our search, which can lead to a much longer runtime. The C++ implementation is
able to handle this larger search space, while the R implementation is not.
#ifndef STANDALONE
#include <Rcpp.h>
using namespace Rcpp;
#else
#include <iostream>
#endif
#include <vector>
int find_longest_path(std::vector<std::vector<int>>& adj_list, int start, int goal) {
// Implement DFS to find the longest path from start to goal
const size_t n = adj_list.size();
std::vector<bool> visited(n, false);
visited[start] = true;
int longest_path = 0, act_path = 0;
// use vector instead of stack as it is faster
std::vector<std::pair<int, int>> stack; // node id and next neighbor
stack.reserve(n - 1);
stack.emplace_back(start, 0);
auto prune = [&](int u) {
visited[u] = false;
act_path--;
stack.pop_back();
};
while (!stack.empty()) {
auto& top = stack.back();
int u = top.first;
int idx = top.second;
if (u == goal) {
if (act_path > longest_path) {
longest_path = act_path;
}
prune(u);
continue;
}
const auto& neighbors = adj_list[u];
if (idx >= static_cast<int> (neighbors.size())) {
prune(u);
continue;
}
int v = neighbors[idx];
top.second++;
if (!visited[v]) {
visited[v] = true;
++act_path;
stack.emplace_back(v, 0);
}
}
return longest_path;
}
#ifndef STANDALONE
// [[Rcpp::export]]
int find_longest_path(List adj_list, int start, int goal) {
std::vector<std::vector<int>> adj(adj_list.size());
for (int i = 0; i < adj_list.size(); ++i) {
IntegerVector neighbors = adj_list[i];
adj[i] = std::vector<int>(neighbors.begin(), neighbors.end());
}
return find_longest_path(adj, start, goal);
}
#else
int main() {
return 0;
}
#endifhike_map_no_slides <- function(winter_map) {
G <- construct_graph(winter_map, use_slides = FALSE)
get_node_id <- function(node) {
V(G)[paste(node[, 1L], node[, 2L], sep = ",")] %>%
as.integer() %>%
subtract(1L)
}
adj <- adjacent_vertices(G, V(G)) %>%
map(~ as.integer(.x) - 1L) %>%
unname()
start <- attr(winter_map, "start")
goal <- attr(winter_map, "goal")
find_longest_path(adj, get_node_id(start), get_node_id(goal))
}
hike_map_no_slides(puzzle_data)## [1] 6522