1 Setup
1.1 Libraries
library(httr)
library(xml2)
library(tibble)
library(magrittr)
library(dplyr)
library(purrr)
library(stringr)
library(stringi)
library(knitr)
library(cli)
library(igraph)
library(gtools)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_split(" to | = ") %>%
do.call(rbind, .) %>%
set_colnames(c("from", "to", "weight")) %>%
as_tibble() %>%
mutate(weight = as.integer(weight))
}
puzzle_data <- local({
GET(paste0(base_url, "/input"),
session_cookie) %>%
content(encoding = "UTF-8") %>%
parse_puzzle_data()
})2 Puzzle Day 9
2.1 Part 1
2.1.1 Description
— Day 9: All in a Single Night —
Every year, Santa manages to deliver all of his presents in a single night.
This year, however, he has some new locations to visit; his elves have provided him the distances between every pair of locations. He can start and end at any two (different) locations he wants, but he must visit each location exactly once. What is the shortest distance he can travel to achieve this?
For example, given the following distances:
London to Dublin = 464
London to Belfast = 518
Dublin to Belfast = 141
The possible routes are therefore:
Dublin -> London -> Belfast = 982
London -> Dublin -> Belfast = 605
London -> Belfast -> Dublin = 659
Dublin -> Belfast -> London = 659
Belfast -> Dublin -> London = 605
Belfast -> London -> Dublin = 982
The shortest of these is London -> Dublin -> Belfast = 605, and so the answer is 605 in this example.
What is the distance of the shortest route?
2.1.2 Solution
This is a Travelling Salesman Path Problem which is known to be NP hard. However, given
the small amount of cities, we still can brute-force the solution. A quick and dirty
solution is to get all permutations of the cities, get the paths of these trips and sum up
their weights.
get_all_trips <- function(data) {
G <- graph_from_data_frame(data, directed = FALSE)
trips <- permutations(vcount(G), vcount(G))
costs <- trips %>%
apply(1L, function(path) {
idx <- get_edge_ids(G,
c(head(path, 1L),
rep(path[c(-1L, -length(path))], each = 2L),
tail(path, 1L)))
costs <- E(G)[idx]$weight
sum(costs)
})
cbind(trips, costs)
}
trips <- get_all_trips(puzzle_data)
min(trips[, 9])## [1] 2072.2 Part 2
2.2.1 Description
— Part Two —
The next year, just to show off, Santa decides to take the route with the longest distance instead.
He can still start and end at any two (different) locations he wants, and he still must visit each location exactly once.
For example, given the distances above, the longest route would be 982 via (for example) Dublin -> London -> Belfast.
What is the distance of the longest route?
2.2.2 Solution
As we generated all paths already in part 1, we simply need to return the maximum length this time.
max(trips[, 9])## [1] 804