— Day 13: Packet Scanners —

Last updated: 2018-01-09

Code version: 51ed8cf

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     

loaded via a namespace (and not attached):
[1] compiler_3.4.2 tools_3.4.2    yaml_2.1.15    knitr_1.17     git2r_0.19.0  

Brief

— Day 13: Packet Scanners —

You need to cross a vast firewall. The firewall consists of several layers, each with a security scanner that moves back and forth across the layer. To succeed, you must not be detected by a scanner.

By studying the firewall briefly, you are able to record (in your puzzle input) the depth of each layer and the range of the scanning area for the scanner within it, written as depth: range. Each layer has a thickness of exactly 1. A layer at depth 0 begins immediately inside the firewall; a layer at depth 1 would start immediately after that.

For example, suppose you’ve recorded the following:

0: 3
1: 2
4: 4
6: 4

This means that there is a layer immediately inside the firewall (with range 3), a second layer immediately after that (with range 2), a third layer which begins at depth 4 (with range 4), and a fourth layer which begins at depth 6 (also with range 4). Visually, it might look like this:

 0   1   2   3   4   5   6
[ ] [ ] ... ... [ ] ... [ ]
[ ] [ ]         [ ]     [ ]
[ ]             [ ]     [ ]
                [ ]     [ ]

Within each layer, a security scanner moves back and forth within its range. Each security scanner starts at the top and moves down until it reaches the bottom, then moves up until it reaches the top, and repeats. A security scanner takes one picosecond to move one step. Drawing scanners as S, the first few picoseconds look like this:

Picosecond 0:

 0   1   2   3   4   5   6
[S] [S] ... ... [S] ... [S]
[ ] [ ]         [ ]     [ ]
[ ]             [ ]     [ ]
                [ ]     [ ]

Picosecond 1:

 0   1   2   3   4   5   6
[ ] [ ] ... ... [ ] ... [ ]
[S] [S]         [S]     [S]
[ ]             [ ]     [ ]
                [ ]     [ ]
                

Picosecond 2:

 0   1   2   3   4   5   6
[ ] [S] ... ... [ ] ... [ ]
[ ] [ ]         [ ]     [ ]
[S]             [S]     [S]
                [ ]     [ ]

Picosecond 3:

 0   1   2   3   4   5   6
[ ] [ ] ... ... [ ] ... [ ]
[S] [S]         [ ]     [ ]
[ ]             [ ]     [ ]
                [S]     [S]
                

Your plan is to hitch a ride on a packet about to move through the firewall. The packet will travel along the top of each layer, and it moves at one layer per picosecond. Each picosecond, the packet moves one layer forward (its first move takes it into layer 0), and then the scanners move one step. If there is a scanner at the top of the layer as your packet enters it, you are caught. (If a scanner moves into the top of its layer while you are there, you are not caught: it doesn’t have time to notice you before you leave.) If you were to do this in the configuration above, marking your current position with parentheses, your passage through the firewall would look like this:

Initial state:

 0   1   2   3   4   5   6
[S] [S] ... ... [S] ... [S]
[ ] [ ]         [ ]     [ ]
[ ]             [ ]     [ ]
                [ ]     [ ]

Picosecond 0:

 0   1   2   3   4   5   6
(S) [S] ... ... [S] ... [S]
[ ] [ ]         [ ]     [ ]
[ ]             [ ]     [ ]
                [ ]     [ ]

 0   1   2   3   4   5   6
( ) [ ] ... ... [ ] ... [ ]
[S] [S]         [S]     [S]
[ ]             [ ]     [ ]
                [ ]     [ ]

Picosecond 1:

 0   1   2   3   4   5   6
[ ] ( ) ... ... [ ] ... [ ]
[S] [S]         [S]     [S]
[ ]             [ ]     [ ]
                [ ]     [ ]

 0   1   2   3   4   5   6
[ ] (S) ... ... [ ] ... [ ]
[ ] [ ]         [ ]     [ ]
[S]             [S]     [S]
                [ ]     [ ]

Picosecond 2:

 0   1   2   3   4   5   6
[ ] [S] (.) ... [ ] ... [ ]
[ ] [ ]         [ ]     [ ]
[S]             [S]     [S]
                [ ]     [ ]

 0   1   2   3   4   5   6
[ ] [ ] (.) ... [ ] ... [ ]
[S] [S]         [ ]     [ ]
[ ]             [ ]     [ ]
                [S]     [S]

Picosecond 3:

 0   1   2   3   4   5   6
[ ] [ ] ... (.) [ ] ... [ ]
[S] [S]         [ ]     [ ]
[ ]             [ ]     [ ]
                [S]     [S]

 0   1   2   3   4   5   6
[S] [S] ... (.) [ ] ... [ ]
[ ] [ ]         [ ]     [ ]
[ ]             [S]     [S]
                [ ]     [ ]

Picosecond 4:

 0   1   2   3   4   5   6
[S] [S] ... ... ( ) ... [ ]
[ ] [ ]         [ ]     [ ]
[ ]             [S]     [S]
                [ ]     [ ]

 0   1   2   3   4   5   6
[ ] [ ] ... ... ( ) ... [ ]
[S] [S]         [S]     [S]
[ ]             [ ]     [ ]
                [ ]     [ ]

Picosecond 5:

 0   1   2   3   4   5   6
[ ] [ ] ... ... [ ] (.) [ ]
[S] [S]         [S]     [S]
[ ]             [ ]     [ ]
                [ ]     [ ]

 0   1   2   3   4   5   6
[ ] [S] ... ... [S] (.) [S]
[ ] [ ]         [ ]     [ ]
[S]             [ ]     [ ]
                [ ]     [ ]

Picosecond 6:

 0   1   2   3   4   5   6
[ ] [S] ... ... [S] ... (S)
[ ] [ ]         [ ]     [ ]
[S]             [ ]     [ ]
                [ ]     [ ]

 0   1   2   3   4   5   6
[ ] [ ] ... ... [ ] ... ( )
[S] [S]         [S]     [S]
[ ]             [ ]     [ ]
                [ ]     [ ]

In this situation, you are caught in layers 0 and 6, because your packet entered the layer when its scanner was at the top when you entered it. You are not caught in layer 1, since the scanner moved into the top of the layer once you were already there.

The severity of getting caught on a layer is equal to its depth multiplied by its range. (Ignore layers in which you do not get caught.) The severity of the whole trip is the sum of these values. In the example above, the trip severity is 03 + 64 = 24.

Given the details of the firewall you’ve recorded, if you leave immediately, what is the severity of your whole trip?

Let’s go

Packages & functions

library(tidyverse)

── Attaching packages ─────────────────────────────────────────────────────────── tidyverse 1.2.1 ──
✔ ggplot2 2.2.1.9000     ✔ purrr   0.2.4     
✔ tibble  1.3.4          ✔ dplyr   0.7.4     
✔ tidyr   0.7.2          ✔ stringr 1.2.0     
✔ readr   1.1.1          ✔ forcats 0.2.0     
── Conflicts ────────────────────────────────────────────────────────────── tidyverse_conflicts() ──
✖ dplyr::filter() masks stats::filter()
✖ dplyr::lag()    masks stats::lag()

library(testthat)

Attaching package: ‘testthat’

The following object is masked from ‘package:dplyr’:

    matches

The following object is masked from ‘package:purrr’:

    is_null

library(aocodeR)

Input

input <- aoc_get_input(day = 13, cookie_path = paste0(rprojroot::find_rstudio_root_file(),
                                                 "/secrets/session_cookie.txt")) 
input

[1] "0: 3\n1: 2\n2: 5\n4: 4\n6: 6\n8: 4\n10: 8\n12: 8\n14: 6\n16: 8\n18: 6\n20: 6\n22: 8\n24: 12\n26: 12\n28: 8\n30: 12\n32: 12\n34: 8\n36: 10\n38: 9\n40: 12\n42: 10\n44: 12\n46: 14\n48: 14\n50: 12\n52: 14\n56: 12\n58: 12\n60: 14\n62: 14\n64: 12\n66: 14\n68: 14\n70: 14\n74: 24\n76: 14\n80: 18\n82: 14\n84: 14\n90: 14\n94: 17"

Functions

# preprocess the input
clean_i <- function(input){
  input %>% str_split("\n") %>% unlist() %>% str_split(": ", simplify = T) %>% 
        as_tibble %>% setNames(c("l", "d")) %>% mutate_all(as.numeric)
}
# scan each layer and record whether packet caught. Either return severity or logical
# on whether packet caught by scan
scan_l <- function(d, l, delay, severity = T, max.l){
    ls <- c(rep(-1, delay), 0:max.l)
    pic <- 0:(max.l + delay)
    scan <- pic %% ((d -1) *2)
    caught <- (scan == 0 & ls == l) %>% any 
    if(severity){
        caught %>% prod(l, d)
    }else{
            caught
        }
}
# apply scan across all layers
firewall_scan <- function(input, delay = 0, severity = T) {
    max.l <- max(input$l)
 input  %>% purrr::pmap_dbl(scan_l, delay, severity, max.l) %>% sum()   
}
# run firewall scan on processed input and return severity of trip
severity_trip <- function(input, delay = 0, severity = T){
input %>% clean_i %>% firewall_scan(delay, severity)    
}
# run firewall scan on processed input, delaying until
min_delay <- function(input) {
    delay <- 0
    while(severity_trip(input, delay, severity = F)){
        delay <- delay + 1 
    }
    delay
}

Test

test_input <- tibble(l = c(0, 1, 4, 6), d = c(3, 2, 4, 4))
expect_equal(firewall_scan(test_input), 24)
expect_equal(severity_trip("0: 3\n1: 2\n4: 4\n6: 4"), 24) 

deploy

severity_trip(input, delay = 0, severity = T)

[1] 1960

Success!

---

—- Part 2 —-

❗️ HELP NEEDED ❗️

Too slow or caught in infinite loop?

Any feedback? let me know here!

---

Brief

Let’s go

Test

Tests passing

expect_equal(test_input  %>% firewall_scan(delay = 10),0)
expect_equal("0: 3\n1: 2\n4: 4\n6: 4" %>% min_delay, 10)

Deployment takes forever. Is there an analytical way to calculate this??

input %>% min_delay

dput(aoc_get_input(day = 13, cookie_path = paste0(rprojroot::find_rstudio_root_file(),
                                                 "/secrets/session_cookie.txt")))

"0: 3\n1: 2\n2: 5\n4: 4\n6: 6\n8: 4\n10: 8\n12: 8\n14: 6\n16: 8\n18: 6\n20: 6\n22: 8\n24: 12\n26: 12\n28: 8\n30: 12\n32: 12\n34: 8\n36: 10\n38: 9\n40: 12\n42: 10\n44: 12\n46: 14\n48: 14\n50: 12\n52: 14\n56: 12\n58: 12\n60: 14\n62: 14\n64: 12\n66: 14\n68: 14\n70: 14\n74: 24\n76: 14\n80: 18\n82: 14\n84: 14\n90: 14\n94: 17"

---

template based on the workflowr standalone template