— Day 20: Particle Swarm —

Last updated: 2017-12-27

Code version: 626c9ea

See more puzzles

Advent of Code

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: /System/Library/Frameworks/Accelerate.framework/Versions/A/Frameworks/vecLib.framework/Versions/A/libBLAS.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     

other attached packages:
 [1] bindrcpp_0.2       prodlim_1.6.1      future_1.6.2       hashmap_0.2.2      aocodeR_0.1.1     
 [6] testthat_1.0.2     forcats_0.2.0      stringr_1.2.0      dplyr_0.7.4        purrr_0.2.4       
[11] readr_1.1.1        tidyr_0.7.2        tibble_1.3.4       ggplot2_2.2.1.9000 tidyverse_1.2.1   

loaded via a namespace (and not attached):
 [1] Rcpp_0.12.14      lubridate_1.7.1   lattice_0.20-35   listenv_0.6.0     assertthat_0.2.0 
 [6] rprojroot_1.2     digest_0.6.12     psych_1.7.8       R6_2.2.2          cellranger_1.1.0 
[11] plyr_1.8.4        backports_1.1.1   evaluate_0.10.1   httr_1.3.1        rlang_0.1.4      
[16] lazyeval_0.2.1    curl_3.0          readxl_1.0.0      rstudioapi_0.7    Matrix_1.2-12    
[21] rmarkdown_1.8     splines_3.4.2     foreign_0.8-69    munsell_0.4.3     broom_0.4.2      
[26] compiler_3.4.2    modelr_0.1.1      pkgconfig_2.0.1   base64enc_0.1-3   mnormt_1.5-5     
[31] globals_0.10.3    htmltools_0.3.6   codetools_0.2-15  crayon_1.3.4      grid_3.4.2       
[36] nlme_3.1-131      jsonlite_1.5      gtable_0.2.0      git2r_0.19.0      magrittr_1.5     
[41] scales_0.5.0.9000 cli_1.0.0         stringi_1.1.6     reshape2_1.4.2    xml2_1.1.1       
[46] lava_1.5.1        tools_3.4.2       glue_1.2.0        hms_0.4.0         rsconnect_0.8.5  
[51] parallel_3.4.2    survival_2.41-3   yaml_2.1.15       colorspace_1.3-2  rvest_0.3.2      
[56] knitr_1.17        bindr_0.1         haven_1.1.0      

Brief

Suddenly, the GPU contacts you, asking for help. Someone has asked it to simulate too many particles, and it won’t be able to finish them all in time to render the next frame at this rate.

It transmits to you a buffer (your puzzle input) listing each particle in order (starting with particle 0, then particle 1, particle 2, and so on). For each particle, it provides the X, Y, and Z coordinates for the particle’s position (p), velocity (v), and acceleration (a), each in the format .

Each tick, all particles are updated simultaneously. A particle’s properties are updated in the following order:

• Increase the X velocity by the X acceleration.
• Increase the Y velocity by the Y acceleration.
• Increase the Z velocity by the Z acceleration.
• Increase the X position by the X velocity.
• Increase the Y position by the Y velocity.
• Increase the Z position by the Z velocity.

Because of seemingly tenuous rationale involving z-buffering, the GPU would like to know which particle will stay closest to position <0,0,0> in the long term. Measure this using the Manhattan distance, which in this situation is simply the sum of the absolute values of a particle’s X, Y, and Z position.

For example, suppose you are only given two particles, both of which stay entirely on the X-axis (for simplicity). Drawing the current states of particles 0 and 1 (in that order) with an adjacent a number line and diagram of current X positions (marked in parenthesis), the following would take place:

p=< 3,0,0>, v=< 2,0,0>, a=<-1,0,0>    -4 -3 -2 -1  0  1  2  3  4
p=< 4,0,0>, v=< 0,0,0>, a=<-2,0,0>                         (0)(1)

p=< 4,0,0>, v=< 1,0,0>, a=<-1,0,0>    -4 -3 -2 -1  0  1  2  3  4
p=< 2,0,0>, v=<-2,0,0>, a=<-2,0,0>                      (1)   (0)

p=< 4,0,0>, v=< 0,0,0>, a=<-1,0,0>    -4 -3 -2 -1  0  1  2  3  4
p=<-2,0,0>, v=<-4,0,0>, a=<-2,0,0>          (1)               (0)

p=< 3,0,0>, v=<-1,0,0>, a=<-1,0,0>    -4 -3 -2 -1  0  1  2  3  4
p=<-8,0,0>, v=<-6,0,0>, a=<-2,0,0>                         (0)  

At this point, particle 1 will never be closer to <0,0,0> than particle 0, and so, in the long run, particle 0 will stay closest.

Which particle will stay closest to position <0,0,0> in the long term?

Let’s go

Packages & functions

library(tidyverse)
library(testthat)
library(aocodeR)

Input

input <- aoc_get_input(day = 20, cookie_path = paste0(rprojroot::find_rstudio_root_file(),
                                                 "/secrets/session_cookie.txt")) %>% 
    strsplit(., "\n") %>% unlist
names(input) <- 1:length(input) - 1

Functions

mh_dist <- function(x, n = 1000){
    y <- x %>% strsplit(., ",") %>% unlist %>%  gsub("[\\<,\\>,=, a-z]", "", .) %>% as.numeric
    for(i in 1:n){
        y[4:6] <- y[4:6] + y[7:9]
        y[1:3] <- y[1:3] + y[4:6]
    }
    y[1:3] %>% abs %>% sum
}

Test

x <- "p=< 3,0,0>, v=< 2,0,0>, a=<-1,0,0>"
expect_equal(mh_dist(x, 1),4)
expect_equal(mh_dist(x, 3),3)

deploy

input %>% map_dbl(mh_dist, n = 2000) %>% which.min() %>% names

[1] "308"

Success!

via GIPHY

---

—- Part 2 —-

Brief

To simplify the problem further, the GPU would like to remove any particles that collide. Particles collide if their positions ever exactly match. Because particles are updated simultaneously, more than two particles can collide at the same time and place. Once particles collide, they are removed and cannot collide with anything else after that tick.

For example:

p=<-6,0,0>, v=< 3,0,0>, a=< 0,0,0>    
p=<-4,0,0>, v=< 2,0,0>, a=< 0,0,0>    -6 -5 -4 -3 -2 -1  0  1  2  3
p=<-2,0,0>, v=< 1,0,0>, a=< 0,0,0>    (0)   (1)   (2)            (3)
p=< 3,0,0>, v=<-1,0,0>, a=< 0,0,0>

p=<-3,0,0>, v=< 3,0,0>, a=< 0,0,0>    
p=<-2,0,0>, v=< 2,0,0>, a=< 0,0,0>    -6 -5 -4 -3 -2 -1  0  1  2  3
p=<-1,0,0>, v=< 1,0,0>, a=< 0,0,0>             (0)(1)(2)      (3)   
p=< 2,0,0>, v=<-1,0,0>, a=< 0,0,0>

p=< 0,0,0>, v=< 3,0,0>, a=< 0,0,0>    
p=< 0,0,0>, v=< 2,0,0>, a=< 0,0,0>    -6 -5 -4 -3 -2 -1  0  1  2  3
p=< 0,0,0>, v=< 1,0,0>, a=< 0,0,0>                       X (3)      
p=< 1,0,0>, v=<-1,0,0>, a=< 0,0,0>

------destroyed by collision------    
------destroyed by collision------    -6 -5 -4 -3 -2 -1  0  1  2  3
------destroyed by collision------                      (3)         
p=< 0,0,0>, v=<-1,0,0>, a=< 0,0,0>

In this example, particles 0, 1, and 2 are simultaneously destroyed at the time and place marked X. On the next tick, particle 3 passes through unharmed.

How many particles are left after all collisions are resolved?

Let’s go

track_locs <- function(x, n = 1000){
    y <- x %>% strsplit(., ",") %>% unlist %>%  gsub("[\\<,\\>,=, a-z]", "", .) %>% as.numeric
    p <- paste0(y[1:3], collapse = "")
    for(i in 1:n){
        y[4:6] <- y[4:6] + y[7:9]
        y[1:3] <- y[1:3] + y[4:6]
        
        p <- c(p, paste0(y[1:3], collapse = ""))
    }
    names(p) <- paste0("t", 0:n)
    p
}
clean_collisions <- function(input, n = 2000){
    locs <- input %>% map(track_locs, n = n) %>% do.call("rbind", .)
    
    for(i in 1:ncol(locs)){
        collisions <- locs[which(duplicated(locs[,i])),i] %>% unique
        locs <- locs[!locs[,i] %in% collisions, ,drop = F]
    }
    nrow(locs)
}

Test

test_input <- c("p=<-6,0,0>, v=< 3,0,0>, a=< 0,0,0>",   
"p=<-4,0,0>, v=< 2,0,0>, a=< 0,0,0>", 
"p=<-2,0,0>, v=< 1,0,0>, a=< 0,0,0>",    
"p=< 3,0,0>, v=<-1,0,0>, a=< 0,0,0>")
expect_equal(clean_collisions(test_input, 10), 1)

deploy

clean_collisions(input, 1000)

[1] 504

Success!

via GIPHY

---

template based on the workflowr standalone template