Solving #AdventOfCode day 1 and 2 with R
Solving the first four puzzles of Advent of Code with R.
[Disclaimer] Obviously, this post contains a big spoiler about Advent of Code, as it gives solutions for solving day 1 and 2.
Advent of Code
Advent of Code is an Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like. About Advent of Code
Day one, part one
Let’s read the inputs for day one:
inputs <- read.csv("input.txt", header = FALSE)[, 1]
The story behind this is, to sum up: you’ve got a frequency of X, and a series of moves to apply to this frequency.
So, here’s the challenge: we are starting at 0, then each element of our
input vector is a “shift”, so the idea is to do 0 + v[1] + v[2] + ... +
v[n]. We need to get the value of the last element.
head(inputs, 10)
## [1] 11 14 10 -8 -13 -2 8 14 -11 -4
Function factory
[Disclaimer bis] I’ve been looking for an opportunity to write a blog post about this for a while. It seems like I finally found one ;)
Here’s a way to do it, using closures, functional programming, and vectorisation. We’re going to create a function factory, which is a family of high order functions that takes a vector and returns a function See there for more info.
with_start_at <- function(start){
start <- start
function(x){
start <<- start + x
start
}
}
Let’s test against the example from AoC.
tail( vapply(c(1, 1, 1), with_start_at(0), numeric(1)), 1)
## [1] 3
tail( vapply(c(1, 1, -2), with_start_at(0), numeric(1)), 1)
## [1] 0
tail( vapply(c(-1, -2, -3), with_start_at(0), numeric(1)), 1)
## [1] -6
And finally, let’s get the answer to the question:
tail( vapply(inputs, with_start_at(0), numeric(1)), 1)
## [1] 402
How does it work
Basically, each function creates its own environment. When you create a
function Y inside another function X, the function Y, when
returned, carries along the environment in which it has been
created. In other word, when I create a function Y with
with_start_at, the start object, even if in the parent environment
at the time of the function creation, is still accessible to the Y
function via the <<- operator.
In a conceptual sense, it’s like defining a start inside your global
environment and changing it on each iteration of the vapply. The big
difference being that you don’t mess with the global environment:
everything happening inside the function stays inside the function.
Benchmark
Let’s benchmark a for loop against our functional solution:
bench::mark(
iterations = 100,
check = FALSE,
`for` = {
start <- 0
for (i in seq_along(inputs)){
start <- start + inputs[i]
}
start},
functional = {
tail( vapply(inputs, with_start_at(0), numeric(1)), 1)
}
)
##
##
## expression min mean median max
## ----------- --------- --------- --------- -------
## for 1.54ms 2.01ms 1.75ms 5.28ms
## functional 623.91µs 803.32µs 735.35µs 1.45ms
Side note
Once I had completed this, I looked for other ways to do it, and
stumbled upon a solution with cumsum, which is basically what my
solution does, but faster and more idiomatic (so yes, better). The only
difference being (on a more general sense), that the cumsum does only
one task (totally valid for our case), but on the long run is less
flexibile: the functional solution would allow us to start at any entry
point, and also to apply any kind of transformation to our
start_object.
Day one, part two
Now, the second challenge is: given our list of frequencies and starting at 0, which frequency is encountered twice first? Note: our list of moves can be repeated as many time as possible until we find our answer.
On this one, I decided to go for the “brute force” solution - the idea
is to: + start from the vector of moves + apply the with_start_at +
test if there is any duplicated + if there are, extract the duplicated,
get the first element, and break + if there is none, multiply i by
10 and rep the original move i times + repeat until I have an answer
i <- 1
while(TRUE){
alls <- sapply( rep(inputs, i), with_start_at(0) )
dup <- duplicated(alls)
if ( any(dup)){
x <- head( alls[dup], 1)
break
} else {
i <- i * 10
}
}
x
## [1] 481
Day Two
Day Two, part one
Day two is a string manipulation challenge.
inputs <- read.csv("input2.txt", header = FALSE, stringsAsFactors = FALSE)[, 1]
head(inputs, 10)
## [1] "qcsnyvpigkxmrdawlfdefotxbh" "qcsnyvligkymrdawljujfotxbh"
## [3] "qmsnyvpigkzmrnawzjuefotxbh" "qosnyvpigkzmrnawljuefouxbh"
## [5] "qcsnhlpigkzmrtawljuefotxbh" "qcsnyvpigkzmrdapljuyfotxih"
## [7] "qcsnbvpiokzmrdawljuerotxbh" "qcfnyvmigkzmrdawljuefotdbh"
## [9] "qcsnynpigkzmrdawljuefptxbp" "qcsgyapigkzmrdawljuafotxbh"
Here is the challenge: get the number of words with a letter repeated twice, and the number of words with a letter repeated three time, and multiply these two words.
Let’s use {purrr} and {dplyr} to do
that.
library(tidyverse)
## ── Attaching packages ────────────────────────────── tidyverse 1.2.1 ──
## ✔ ggplot2 3.1.0 ✔ purrr 0.2.5
## ✔ tibble 1.4.2 ✔ dplyr 0.7.8
## ✔ tidyr 0.8.1 ✔ stringr 1.3.1
## ✔ readr 1.1.1 ✔ forcats 0.3.0
## ── Conflicts ───────────────────────────────── tidyverse_conflicts() ──
## ✖ dplyr::filter() masks stats::filter()
## ✖ dplyr::lag() masks stats::lag()
# Create a splitter and counter
split_and_count <- compose(
table,
flatten_chr,
partial(strsplit, split = "")
)
# Split them all
map(inputs, split_and_count) %>%
map_df(function(x){
tibble(
two = any(x == 2),
three = any(x == 3)
)
}) %>%
# Get the result
summarise(
res = sum(two) * sum(three)
)
## # A tibble: 1 x 1
## res
## <int>
## 1 6422
Day Two, part two
The second part of the challenge was to detect, from the inputs, the two “words” with just one different character, and extract from these two the common pattern.
Good news: I’ve been working on {tidystringdist}, a tidy framework
for the {stringdist} package, which can be used to compute exactly
that. We’ll use the Levenshtein
distance, which (to
sum up) compute the number of permutations necessary to move from one
string to another. As we are looking for two words with a permutation of
one character, the Levenshtein distance should be of one.
library(tidystringdist)
res <- tidy_comb_all(inputs) %>%
tidy_stringdist(method = "lv") %>%
filter(lv == 1)
res
## # A tibble: 1 x 3
## V1 V2 lv
## <chr> <chr> <dbl>
## 1 qcslyvphgkrmddawljuefotxbh qcslyvphgkrmrdawljuefotxbh 1
Now we’ve got that, we are looking for the common string. Here’s a quick and dirty way to do this:
splt <- compose(
flatten_chr,
partial(strsplit, split = "")
)
v1 <- splt(res$V1)
v2 <- splt(res$V2)
v1[v1 == v2] %>% paste(collapse = "")
## [1] "qcslyvphgkrmdawljuefotxbh"
What do you think?