— Day 3: Spiral Memory —
annakrystalli
2017-12-03
Last updated: 2017-12-03
Code version: 905fb98
Session information
sessionInfo()R version 3.4.2 (2017-09-28)
Platform: x86_64-apple-darwin15.6.0 (64-bit)
Running under: macOS Sierra 10.12.6
Matrix products: default
BLAS: /Library/Frameworks/R.framework/Versions/3.4/Resources/lib/libRblas.0.dylib
LAPACK: /Library/Frameworks/R.framework/Versions/3.4/Resources/lib/libRlapack.dylib
locale:
[1] en_GB.UTF-8/en_GB.UTF-8/en_GB.UTF-8/C/en_GB.UTF-8/en_GB.UTF-8
attached base packages:
[1] stats graphics grDevices utils datasets methods base
loaded via a namespace (and not attached):
[1] compiler_3.4.2 backports_1.1.1 magrittr_1.5 rprojroot_1.2
[5] tools_3.4.2 htmltools_0.3.6 yaml_2.1.15 Rcpp_0.12.14
[9] stringi_1.1.6 rmarkdown_1.8 knitr_1.17 git2r_0.19.0
[13] stringr_1.2.0 digest_0.6.12 evaluate_0.10.1Brief
You come across an experimental new kind of memory stored on an infinite two-dimensional grid.
Each square on the grid is allocated in a spiral pattern starting at a location marked 1 and then counting up while spiraling outward. For example, the first few squares are allocated like this:
17 16 15 14 13
18 5 4 3 12
19 6 1 2 11
20 7 8 9 10
21 22 23---> ...While this is very space-efficient (no squares are skipped), requested data must be carried back to square 1 (the location of the only access port for this memory system) by programs that can only move up, down, left, or right. They always take the shortest path: the Manhattan Distance between the location of the data and square 1.
For example:
Data from square 1 is carried 0 steps, since it’s at the access port. Data from square 12 is carried 3 steps, such as: down, left, left. Data from square 23 is carried only 2 steps: up twice. Data from square 1024 must be carried 31 steps. How many steps are required to carry the data from the square identified in your puzzle input all the way to the access port?
Let’s go
Packages & functions
library(tidyverse)
library(testthat)
library(aocodeR)Input
input <- aoc_get_input(day = 3, cookie_path = paste0(rprojroot::find_rstudio_root_file(),
"/secrets/session_cookie.txt")) %>%
as.numeric()
input[1] 325489Functions
# gets some parameters associated with the outer spiral in which the input value falls
get_spiral_params <- function(input){
sp_start <- 2
dist <- 1
diam <- 2 * dist + 1
out <- tibble(dist = dist, sp_start = sp_start, diam = diam)
while(sp_start < input){
dist <- dist + 1
sp_start <- (dist + (dist - 1))^2
diam <- 2 * dist + 1
out <- out %>% bind_rows(
tibble(dist = dist, sp_start = sp_start, diam = diam))
}
out
}
# gets any additional distance as a result of the position of the value in the outer spiral
get_dist <- function(input, sp = sps %>% filter(sp_start <= input) %>% tail(1)){
abs(1:(sp$diam - 1) - mean(1:sp$diam))[
(input - sp$sp_start) %% (sp$diam - 1) + 1] + sp$dist
}Test
expect_equal({
sps <- get_spiral_params(12)
get_dist(12)},3)
expect_equal({
sps <- get_spiral_params(23)
get_dist(23)},2)
expect_equal({
sps <- get_spiral_params(1024)
get_dist(1024)},31)deploy
sps <- get_spiral_params(input)
sps# A tibble: 286 x 3
dist sp_start diam
<dbl> <dbl> <dbl>
1 1 2 3
2 2 9 5
3 3 25 7
4 4 49 9
5 5 81 11
6 6 121 13
7 7 169 15
8 8 225 17
9 9 289 19
10 10 361 21
# ... with 276 more rowsget_dist(input)[1] 552Success!
—- Part 2 —-
Brief
As a stress test on the system, the programs here clear the grid and then store the value 1 in square 1. Then, in the same allocation order as shown above, they store the sum of the values in all adjacent squares, including diagonals.
So, the first few squares’ values are chosen as follows:
Square 1 starts with the value 1. Square 2 has only one adjacent filled square (with value 1), so it also stores 1. Square 3 has both of the above squares as neighbors and stores the sum of their values, 2. Square 4 has all three of the aforementioned squares as neighbors and stores the sum of their values, 4. Square 5 only has the first and fourth squares as neighbors, so it gets the value 5. Once a square is written, its value does not change. Therefore, the first few squares would receive the following values:
147 142 133 122 59 304 5 4 2 57 330 10 1 1 54 351 11 23 25 26 362 747 806—> …
What is the first value written that is larger than your puzzle input?
Let’s go
# filter values which are in the neighbourhood of the location given and sum
get_move_value <- function(grid, loc){
grid %>% filter(x %in% (-1:1 + loc$x) , y %in% (-1:1 + loc$y)) %>% select(value) %>% sum}
get_value_row <- function(grid){
last_row <- tail(grid, 1)
spiral_ <- last_row$spiral # which spiral are we on? Spirals are corner trajectories spaning two axis directions, each of steps equal to spiral
spiral_moves <- grid %>% filter(spiral == spiral_) %>% nrow # how many steps have we taken on this spiral.
if(spiral_moves >= (spiral_ * 2)){
spiral_ <- spiral_ + 1 # shift to next spiral
spiral_moves <- grid %>% filter(spiral == spiral_) %>% nrow # reset the number of steps
}
# set the sign of the step in coordinate space
if(spiral_ %% 2 == 1){sign = +1}else{sign = -1}
# set the axis of travel
if(spiral_moves < spiral_){move <- c(1,0) * sign}else{move <- c(0,1) * sign}
loc <- last_row %>% select(x,y) + move
grid %>% bind_rows(
tibble(value = get_move_value(grid, loc), spiral = spiral_) %>% bind_cols(loc))
}
get_first_sum <- function(input){
grid <- tibble(value = 1, spiral = 0, x = 0, y = 0)
while(tail(grid$value, 1) < input){
grid <- get_value_row(grid)
}
tail(grid$value, 1)
}See what the functions do:
grid <- tibble(value = 1, spiral = 0, x = 0, y = 0)
grid# A tibble: 1 x 4
value spiral x y
<dbl> <dbl> <dbl> <dbl>
1 1 0 0 0get_value_row(grid)# A tibble: 2 x 4
value spiral x y
<dbl> <dbl> <dbl> <dbl>
1 1 0 0 0
2 1 1 1 0Test
expect_equal(get_first_sum(2), 2)
expect_equal(get_first_sum(4), 4)
expect_equal(get_first_sum(5), 5)deploy
get_first_sum(input)[1] 330785