— Day 9: Stream Processing —

Last updated: 2017-12-10

Code version: 32d98f0

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] rlist_0.4.6.1   jsonlite_1.5    bindrcpp_0.2    aocodeR_0.1.1   testthat_1.0.2 
 [6] forcats_0.2.0   stringr_1.2.0   dplyr_0.7.4     purrr_0.2.4     readr_1.1.1    
[11] tidyr_0.7.2     tibble_1.3.4    ggplot2_2.2.1   tidyverse_1.2.1

loaded via a namespace (and not attached):
 [1] reshape2_1.4.2      haven_1.1.0         lattice_0.20-35     colorspace_1.3-2   
 [5] htmltools_0.3.6     base64enc_0.1-3     yaml_2.1.15         rlang_0.1.4        
 [9] foreign_0.8-69      glue_1.2.0          modelr_0.1.1        readxl_1.0.0       
[13] bindr_0.1           plyr_1.8.4          munsell_0.4.3       gtable_0.2.0       
[17] cellranger_1.1.0    rvest_0.3.2         evaluate_0.10.1     psych_1.7.8        
[21] knitr_1.17          curl_3.0            parallel_3.4.2      broom_0.4.2        
[25] Rcpp_0.12.14        scales_0.5.0        backports_1.1.1     mnormt_1.5-5       
[29] digest_0.6.12       hms_0.4.0           stringi_1.1.6       grid_3.4.2         
[33] rprojroot_1.2       cli_1.0.0           tools_3.4.2         magrittr_1.5       
[37] lazyeval_0.2.1      crayon_1.3.4        pkgconfig_2.0.1     data.table_1.10.4-3
[41] rsconnect_0.8.5     xml2_1.1.1          lubridate_1.7.1     assertthat_0.2.0   
[45] rmarkdown_1.8       httr_1.3.1          rstudioapi_0.7      R6_2.2.2           
[49] nlme_3.1-131        compiler_3.4.2      git2r_0.19.0       

Brief

A large stream blocks your path. According to the locals, it’s not safe to cross the stream at the moment because it’s full of garbage. You look down at the stream; rather than water, you discover that it’s a stream of characters.

You sit for a while and record part of the stream (your puzzle input). The characters represent groups - sequences that begin with { and end with }. Within a group, there are zero or more other things, separated by commas: either another group or garbage. Since groups can contain other groups, a } only closes the most-recently-opened unclosed group - that is, they are nestable. Your puzzle input represents a single, large group which itself contains many smaller ones.

Sometimes, instead of a group, you will find garbage. Garbage begins with < and ends with >. Between those angle brackets, almost any character can appear, including { and }. Within garbage, < has no special meaning.

In a futile attempt to clean up the garbage, some program has canceled some of the characters within it using !: inside garbage, any character that comes after ! should be ignored, including <, >, and even another !.

You don’t see any characters that deviate from these rules. Outside garbage, you only find well-formed groups, and garbage always terminates according to the rules above.

Let’s go

Today there was quite a bit of REGEX

Packages & functions

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

Input

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

Functions

grp_chr_sets <- function (input){
    input %>% gsub("!.", "", .)  %>% gsub("(<[^>]*>,?)", "", .)
}
score_sets <- function(input) {
    chr_sets <-  input %>% grp_chr_sets
    sets <- chr_sets %>% gregexpr("\\}", .)
    score <- function(i, chr_sets){
        substr(chr_sets,1, i -1) %>% str_count("\\{") - 
            substr(chr_sets,1, i -1) %>% str_count("\\}")
    }
    sets %>% unlist %>% map_int(~score(.x, chr_sets)) %>% sum
}

count_junk <- function(input){
    stream <- input %>% gsub("!.", "", .) %>% strsplit(.,split ="") %>% unlist
    score <- 0
    record <- F
    for(i in 1:length(stream)){
        c <- stream[i]
        if(c == "<"){if(record){
            score <- score + 1
            next
        }else{
            record <- TRUE}
            next}
        
        if(record){
            if(stream[i] != ">"){
                score <- score + 1}else{
                    record <- F
                }}
    }
    score
} 

Test

# test ! removing gsub
expect_equal("<!!e!!>>" %>% gsub("(!.)", "", .) , "<e>>")
expect_equal("<!!!!>>" %>% gsub("!.", "", .) , "<>>")
expect_equal("<!!!>>" %>% gsub("!.", "", .) , "<>")
expect_equal("<!!!>>" %>% gsub("!.", "", .) , "<>")
# test garbage cleaning gsub
expect_equal("{{<a>},{<a>},{<a>},{<a>}}" %>% gsub("(<[^>]*>)", "", .) , "{{},{},{},{}}")
expect_equal("{<{},{},{{}}>}" %>% gsub("(<[^>]*>)", "", .) , "{}")
# test group 
expect_equal("<{o'i!a,<{i<a>" %>% grp_chr_sets, "")
expect_equal("{<{},{},{{}}>}" %>% grp_chr_sets , "{}")
expect_equal("{{<!>},{<!>},{<!>},{<a>}}" %>% grp_chr_sets , "{{}}")
expect_equal("{<a>,<a>,<a>,<a>}" %>% grp_chr_sets , "{}")
expect_equal("{{{},{},{{}}}}"  %>% score_sets, 16)
expect_equal("{{<ab>},{<ab>},{<ab>},{<ab>}}"  %>% score_sets, 9)
expect_equal("{{<!!>},{<!!>},{<!!>},{<!!>}}"  %>% score_sets, 9)
expect_equal("{{<a!>},{<a!>},{<a!>},{<ab>}}"  %>% score_sets, 3)
expect_equal("<{o'i!a,<{i<a>" %>% count_junk, 10)
expect_equal("<!!>" %>% count_junk, 0)
expect_equal("<random characters>" %>% count_junk, 17)
expect_equal("<!!!>>" %>% count_junk, 0)
expect_equal("<{!>}>" %>% count_junk, 2)
expect_equal("<{!><}>" %>% count_junk, 3)
expect_equal("{<{o'i!a,<{i<a>, <{!><}>}" %>% count_junk, 13)

deploy

input %>% score_sets

[1] 14204

Success!

---

—- Part 2 —-

Brief

Now, you’re ready to remove the garbage.

To prove you’ve removed it, you need to count all of the characters within the garbage. The leading and trailing < and > don’t count, nor do any canceled characters or the ! doing the canceling.

<>, 0 characters. <random characters>, 17 characters. <<<<>, 3 characters. <{!>}>, 2 characters. <!!>, 0 characters. <!!!>>, 0 characters. <{o"i!a,<{i<a>, 10 characters.

How many non-canceled characters are within the garbage in your puzzle input?

Let’s go

This one really stumped me in parts because I think I was continuously trying to use the wrong tool.

• I tried regex
• trying to work with a nested list
• turn it into json and trying to extract information about the substructure.

I also managed to develop many solutions that would pass the tests but the result was wrong. I finally gave in an wrote an element by element recording algorithm is 20 mins…and it worked. I don’t why I kept thinking there’s some better way than building this sort of algorithm. Alas in the end, the simplest approach worked just fine!

Anyroad, I did learn a lot more about regex, the different flavours and thinking about how to extract set nestedness information from a series of curly braces

Test

expect_equal("<{o'i!a,<{i<a>" %>% count_junk, 10)
expect_equal("<!!>" %>% count_junk, 0)
expect_equal("<random characters>" %>% count_junk, 17)
expect_equal("<!!!>>" %>% count_junk, 0)
expect_equal("<{!>}>" %>% count_junk, 2)
expect_equal("<{!><}>" %>% count_junk, 3)
expect_equal("{<{o'i!a,<{i<a>, <{!><}>}" %>% count_junk, 13)

deploy

input %>% count_junk

[1] 6622

Success!

---

template based on the workflowr standalone template