Advent of Code: Day 3
Today was way more difficult (at least for me) compared to day 1 and day 2. I spent way too much time trying to figure it out…
Solution part 1
Because of the spiral pattern, the bottom right corner of the grid will be the square value of the size of the grid. When the grid is 3x3, the bottom right corner will be 9, 25 when the grid is 5x5, etc.
So based on the input value, we first calculate the size of the grid. From that, we work backwards to infer the values on the outer edge of the grid. We find the absolute coordinates (with (0,0) being the center of the square). And then use the formula of the Manhattan distance to calculate the distance for the center.
library(tidyverse)
input <- 368078
get_distance <- function(input) {
max_square_size <- ceiling(sqrt(input))
if (max_square_size %% 2 == 0) max_square_size <- max_square_size + 1
max_val <- max_square_size^2
size <- max_square_size - 1
side1 <- (max_val-size):max_val
side2 <- (max_val - 2*size):(max_val-size)
side3 <- (max_val - 3*size):(max_val - 2*size)
side4 <- ((max_val - 4*size):(max_val - 3*size))[-1]
side4 <- c(max_val, side4)
y_coords <- data_frame(side1=side1, side2=side2,
side3=side3, side4=side4) %>%
gather(side, value) %>%
group_by(side) %>%
mutate(coord = abs(row_number() - (n()+1)/2)) %>%
filter(value == input) %>%
pull(coord)
sum(c((max_square_size - 1)/2, y_coords[1]))
}
get_distance(input)
## [1] 371
Solution part 2
With the first part, I tried to avoid having to create an algorithm to build the spiral. With this second solution, it seems that it was actually inevitable.
First, I wrote make_simple_spiral() (below) to make sure that the spiraling worked correctly. I then modified the function that assigns the value of the cell to sum the content of the neighboring cells (make_stress_test_spiral()). The function is pretty inefficient, and I kept the old way to calculate the size of the matrix which is way too large for this problem, but it still gets the job done.
move_right <- function(pos) c(pos[1] , pos[2] + 1)
move_up <- function(pos) c(pos[1] - 1, pos[2])
move_left <- function(pos) c(pos[1] , pos[2] - 1)
move_down <- function(pos) c(pos[1] + 1, pos[2] )
make_stress_test_spiral <- function(input) {
## get size of grid:
m_size <- ceiling(sqrt(input))
if (m_size %% 2 == 0) m_size <- m_size + 1
mat <- array(NA, dim = c(m_size, m_size))
middle <- (m_size + 1) / 2
i_square_size <- 1
pos <- c(0, 0)
curr_val <- 1
assign_to_mat <- function(mat, middle, pos, val) {
mat[middle + pos[1], middle + pos[2]] <- val
mat
}
compute_val <- function(mat, pos) {
pos <- pos + middle
sum(c(
mat[max(0, pos[1] - 1), max(0, pos[2] - 1)],
mat[pos[1] , max(0, pos[2] - 1)],
mat[max(0, pos[1] - 1), pos[2]],
mat[max(0, pos[1] - 1), pos[2] + 1],
mat[pos[1] + 1, max(0, pos[2]- 1)],
mat[pos[1] + 1, pos[2]],
mat[pos[1] , pos[2] + 1],
mat[pos[1] + 1, pos[2] + 1]),
na.rm = TRUE)
}
while(curr_val < input) {
if (i_square_size > 1) {
pos <- move_right(pos)
curr_val <- compute_val(mat, pos)
mat <- assign_to_mat(mat, middle, pos, curr_val)
} else {
mat <- assign_to_mat(mat, middle, pos, curr_val)
}
j <- 0
while (j < (max(0, i_square_size - 2)) && curr_val < input) {
pos <- move_up(pos)
curr_val <- compute_val(mat, pos)
mat <- assign_to_mat(mat, middle, pos, curr_val)
j <- j + 1
}
i <- 1
while (i <= (i_square_size - 1) && curr_val < input) {
pos <- move_left(pos)
curr_val <- compute_val(mat, pos)
mat <- assign_to_mat(mat, middle, pos, curr_val)
i <- i + 1
}
j <- 1
while (j <= (i_square_size - 1) && curr_val < input) {
pos <- move_down(pos)
curr_val <- compute_val(mat, pos)
mat <- assign_to_mat(mat, middle, pos, curr_val)
j <- j + 1
}
i <- 1
while (i <= (i_square_size - 1) && curr_val < input) {
pos <- move_right(pos)
curr_val <- compute_val(mat, pos)
mat <- assign_to_mat(mat, middle, pos, curr_val)
i <- i + 1
}
i_square_size <- i_square_size + 2
}
max(mat, na.rm = TRUE)
}
make_stress_test_spiral(input)
## [1] 369601
## initial function to build the spiral matrix
make_simple_spiral <- function(input) {
## get size of grid:
m_size <- ceiling(sqrt(input))
if (m_size %% 2 == 0) m_size <- m_size + 1
mat <- array(NA, dim = c(m_size, m_size))
middle <- (m_size + 1) / 2
i_square_size <- 1
pos <- c(0, 0)
curr_val <- 1
assign_to_mat <- function(mat, middle, pos, val) {
mat[middle + pos[1], middle + pos[2]] <- val
mat
}
while(curr_val < input) {
if (i_square_size > 1) {
pos <- move_right(pos)
curr_val <- curr_val + 1
mat <- assign_to_mat(mat, middle, pos, curr_val)
} else {
mat <- assign_to_mat(mat, middle, pos, curr_val)
}
j <- 0
while (j < (max(0, i_square_size - 2)) && curr_val < input) {
pos <- move_up(pos)
curr_val <- curr_val + 1
mat <- assign_to_mat(mat, middle, pos, curr_val)
j <- j + 1
}
i <- 1
while (i <= (i_square_size - 1) && curr_val < input) {
pos <- move_left(pos)
curr_val <- curr_val + 1
mat <- assign_to_mat(mat, middle, pos, curr_val)
i <- i + 1
}
j <- 1
while (j <= (i_square_size - 1) && curr_val < input) {
pos <- move_down(pos)
curr_val <- curr_val + 1
mat <- assign_to_mat(mat, middle, pos, curr_val)
j <- j + 1
}
i <- 1
while (i <= (i_square_size - 1) && curr_val < input) {
pos <- move_right(pos)
curr_val <- curr_val + 1
mat <- assign_to_mat(mat, middle, pos, curr_val)
i <- i + 1
}
i_square_size <- i_square_size + 2
}
mat
}
make_simple_spiral(18)
## [,1] [,2] [,3] [,4] [,5]
## [1,] 17 16 15 14 13
## [2,] 18 5 4 3 12
## [3,] NA 6 1 2 11
## [4,] NA 7 8 9 10
## [5,] NA NA NA NA NA
Comments