Last updated: 2017-12-27

Code version: 58d53c2

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

You find a program trying to generate some art. It uses a strange process that involves repeatedly enhancing the detail of an image through a set of rules.

The image consists of a two-dimensional square grid of pixels that are either on (#) or off (.). The program always begins with this pattern:

.#.
..#
###

Because the pattern is both 3 pixels wide and 3 pixels tall, it is said to have a size of 3.

Then, the program repeats the following process:

If the size is evenly divisible by 2, break the pixels up into 2x2 squares, and convert each 2x2 square into a 3x3 square by following the corresponding enhancement rule. Otherwise, the size is evenly divisible by 3; break the pixels up into 3x3 squares, and convert each 3x3 square into a 4x4 square by following the corresponding enhancement rule. Because each square of pixels is replaced by a larger one, the image gains pixels and so its size increases.

The artist’s book of enhancement rules is nearby (your puzzle input); however, it seems to be missing rules. The artist explains that sometimes, one must rotate or flip the input pattern to find a match. (Never rotate or flip the output pattern, though.) Each pattern is written concisely: rows are listed as single units, ordered top-down, and separated by slashes. For example, the following rules correspond to the adjacent patterns:

../.#  =  ..
          .#

                .#.
.#./..#/###  =  ..#
                ###

                        #..#
#..#/..../#..#/.##.  =  ....
                        #..#
                        .##.

When searching for a rule to use, rotate and flip the pattern as necessary. For example, all of the following patterns match the same rule:

.#.   .#.   #..   ###
..#   #..   #.#   ..#
###   ###   ##.   .#.

Suppose the book contained the following two rules:

../.# => ##./#../...
.#./..#/### => #..#/..../..../#..#

As before, the program begins with this pattern:

.#.
..#
###

The size of the grid (3) is not divisible by 2, but it is divisible by 3. It divides evenly into a single square; the square matches the second rule, which produces:

#..#
....
....
#..#

The size of this enhanced grid (4) is evenly divisible by 2, so that rule is used. It divides evenly into four squares:

#.|.#
..|..
--+--
..|..
#.|.#

Each of these squares matches the same rule (../.# => ##./#../…), three of which require some flipping and rotation to line up with the rule. The output for the rule is the same in all four cases:

##.|##.
#..|#..
...|...
---+---
##.|##.
#..|#..
...|...

Finally, the squares are joined into a new grid:

##.##.
#..#..
......
##.##.
#..#..
......

Thus, after 2 iterations, the grid contains 12 pixels that are on.

How many pixels stay on after 5 iterations?

Let’s go

Packages & functions

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

Input

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

Functions

pat2mat <- function(pattern){
    pattern %>% strsplit("/") %>% unlist %>% strsplit(numeric())  %>% do.call("rbind", .)
}
mat2pat <- function(m){
    vec <- cbind(m, "/") %>% t %>% as.vector 
    paste0(vec[-length(vec)], collapse = "")
}
flip_h <- function(m){
    m[,ncol(m):1] %>% mat2pat
}
flip_v <- function(m){
    m[nrow(m):1,] %>% mat2pat
}
rot_90 <- function(m){
    t(m[nrow(m):1,]) %>% mat2pat
}
rot_180 <- function(m){
    m[nrow(m):1,ncol(m):1] %>% mat2pat
}
rot_270 <- function(m){
    t(m)[ncol(m):1,] %>% mat2pat
}
enhancements <- function(x, all = T){
    m <- pat2mat(x[1])
    if(all){
    tibble(match = c(mat2pat(m), flip_h(m), flip_v(m), 
                     rot_90(m), rot_180(m), rot_270(m)),
           enhance = x[2]) %>% unique
    }else{
        tibble(match = x[1], enhance = x[2])
    }
}
enhancement_tbl <- function(input, all = T){
    l <- input %>% gsub("#", 1, .) %>% gsub("\\.", 0, .) %>% 
    strsplit(., "\n") %>% unlist %>% strsplit(., " => ") %>% 
        map_dfr(enhancements, all)
}
get_enhancement <- function(px, tbl){
    tbl %>% filter(match %in% (px %>% mat2pat %>% enhancements(all = T) %>% pull(match))) %>% 
        pull(enhance) %>% unique
}
get_rci <- function(m, n){
    rg <- (row(m)-1) %/% n + 1
    cg <- (col(m)-1) %/% n + 1
    (rg-1)*max(cg) + cg
}
matsplitter<-function(m, div) {
    rci <-  get_rci(m, div)
    n <- prod(dim(m))/div/div
    cv <- unlist(lapply(1:n, function(x) m[rci==x]))
    dim(cv)<-c(div,div,n)
    cv
} 
pix_l2mat <- function(l, npx, exp){
    nsize <- npx * exp
    m <- matrix(0, ncol = nsize, nrow = nsize)
    rci <- get_rci(m, exp)
    for(i in 1:length(l)){
        m[rci == i] <- l[[i]]
    }
    m
}
enhance_px <- function(px, tbl){
    size <- px %>% dim %>% unique
    if(size %% 2 == 0){
        div <- 2
        exp <- 3}else{
            div <- 3
            exp <- 4}
    npx <- size/div
    apply(matsplitter(px, div), 3, FUN = get_enhancement, tbl = tbl) %>% 
        lapply(pat2mat) %>% pix_l2mat(npx, exp)
}
iter_enhancement <- function(iter, input){
    tbl <- enhancement_tbl(input, all = T)
    px <- "010/001/111" %>% pat2mat
    for(i in 1:iter){
        t0 <- Sys.time()
        px <- enhance_px(px, tbl)
        cat(i, "-- t", Sys.time() - t0, "\n")
    }
    px
}

Test

#expect_equal(,)

deploy

iter_enhancement(5, input) %>% as.numeric %>% sum
1 -- t 0.02047706 
2 -- t 0.09022021 
3 -- t 0.1110499 
4 -- t 0.1148739 
5 -- t 0.4064772 
[1] 186

Success!

via GIPHY



—- Part 2 —-

Brief

Let’s go

Test

#expect_equal(,)

deploy

NEEDS REVISTING FOR SPEED UP!

I’m going to try and perform the enhancement without building the full matrix, but rather, keep it in the compact ..#/#.# notation

iter_enhancement(18, input) %>% as.numeric %>% sum
1 -- t 0.01234889 
2 -- t 0.04629803 
3 -- t 0.117589 
4 -- t 0.1194429 
5 -- t 0.421066 
6 -- t 0.8993812 
7 -- t 0.890754 
8 -- t 3.669505 
9 -- t 7.640756 
10 -- t 7.66293 
11 -- t 31.49764 
12 -- t 1.192982 
13 -- t 1.243426 
14 -- t 5.323464 
15 -- t 14.00838 
16 -- t 17.59456 
17 -- t 1.65651 
18 -- t 6.610538 
[1] 3018423

Success!



template based on the workflowr standalone template

LS0tCnRpdGxlOiAiLS0tIERheSAyMTogRnJhY3RhbCBBcnQgLS0tIgphdXRob3I6ICJhbm5ha3J5c3RhbGxpIgpkYXRlOiAyMDE3LTEyLTIxCm91dHB1dDogaHRtbF9ub3RlYm9vawplZGl0b3Jfb3B0aW9uczogCiAgY2h1bmtfb3V0cHV0X3R5cGU6IGlubGluZQotLS0KCmBgYHtyIGtuaXRyLW9wdHMtY2h1bmssIGluY2x1ZGU9RkFMU0V9CiMgVXBkYXRlIGtuaXRyIGNodW5rIG9wdGlvbnMKIyBodHRwczovL3lpaHVpLm5hbWUva25pdHIvb3B0aW9ucy8jY2h1bmstb3B0aW9ucwprbml0cjo6b3B0c19jaHVuayRzZXQoCiAgY29tbWVudCA9IE5BLAogIGZpZy5hbGlnbiA9ICJjZW50ZXIiLAogIHRpZHkgPSBGQUxTRSwKICBmaWcucGF0aCA9IHBhc3RlMCgiZmlndXJlLyIsIGtuaXRyOjpjdXJyZW50X2lucHV0KCksICIvIikKKQpgYGAKCmBgYHtyIGxhc3QtdXBkYXRlZCwgZWNobz1GQUxTRSwgcmVzdWx0cz0nYXNpcyd9CiMgSW5zZXJ0IHRoZSBkYXRlIHRoZSBmaWxlIHdhcyBsYXN0IHVwZGF0ZWQKY2F0KHNwcmludGYoIioqTGFzdCB1cGRhdGVkOioqICVzIiwgU3lzLkRhdGUoKSkpCmBgYAoKYGBge3IgY29kZS12ZXJzaW9uLCBlY2hvPUZBTFNFLCByZXN1bHRzPSdhc2lzJ30KIyBJbnNlcnQgdGhlIGNvZGUgdmVyc2lvbiAoR2l0IGNvbW1pdCBTSEExKSBpZiBHaXQgcmVwb3NpdG9yeSBleGlzdHMgYW5kIFIKIyBwYWNrYWdlIGdpdDJyIGlzIGluc3RhbGxlZAppZihyZXF1aXJlTmFtZXNwYWNlKCJnaXQyciIsIHF1aWV0bHkgPSBUUlVFKSkgewogIGlmKGdpdDJyOjppbl9yZXBvc2l0b3J5KCkpIHsKICAgIGNvZGVfdmVyc2lvbiA8LSBzdWJzdHIoZ2l0MnI6OmNvbW1pdHMoKVtbMV1dQHNoYSwgMSwgNykKICB9IGVsc2UgewogICAgY29kZV92ZXJzaW9uIDwtICJVbmF2YWlsYWJsZS4gSW5pdGlhbGl6ZSBHaXQgcmVwb3NpdG9yeSB0byBlbmFibGUuIgogIH0KfSBlbHNlIHsKICBjb2RlX3ZlcnNpb24gPC0gIlVuYXZhaWxhYmxlLiBJbnN0YWxsIGdpdDJyIHBhY2thZ2UgdG8gZW5hYmxlLiIKfQpjYXQoc3ByaW50ZigiKipDb2RlIHZlcnNpb246KiogJXMiLCBjb2RlX3ZlcnNpb24pKQpybShjb2RlX3ZlcnNpb24pCmBgYAoKCj4gWyoqKlNlZSBtb3JlIHB1enpsZXMqKipdKGh0dHA6Ly9hbm5ha3J5c3RhbGxpLm1lL2FkdmVudF9vZl9jb2RlLykKClsqKkFkdmVudCBvZiBDb2RlKipdKGh0dHBzOi8vYWR2ZW50b2Zjb2RlLmNvbS8yMDE3LykKCgojIyBTZXNzaW9uIGluZm9ybWF0aW9uCgo8IS0tIEluc2VydCB0aGUgc2Vzc2lvbiBpbmZvcm1hdGlvbiBpbnRvIHRoZSBkb2N1bWVudCAtLT4KYGBge3Igc2Vzc2lvbi1pbmZvfQpzZXNzaW9uSW5mbygpCmBgYAoKCiMjIEJyaWVmCgo8IS0tIEluc2VydCBQYXJ0IDEgb2YgdGhlIHB1enpsZSBicmllZiBoZXJlIC0tPgoKWW91IGZpbmQgYSBwcm9ncmFtIHRyeWluZyB0byBnZW5lcmF0ZSBzb21lIGFydC4gSXQgdXNlcyBhIHN0cmFuZ2UgcHJvY2VzcyB0aGF0IGludm9sdmVzIHJlcGVhdGVkbHkgZW5oYW5jaW5nIHRoZSBkZXRhaWwgb2YgYW4gaW1hZ2UgdGhyb3VnaCBhIHNldCBvZiBydWxlcy4KClRoZSBpbWFnZSBjb25zaXN0cyBvZiBhIHR3by1kaW1lbnNpb25hbCBzcXVhcmUgZ3JpZCBvZiBwaXhlbHMgdGhhdCBhcmUgZWl0aGVyIG9uICgjKSBvciBvZmYgKC4pLiBUaGUgcHJvZ3JhbSBhbHdheXMgYmVnaW5zIHdpdGggdGhpcyBwYXR0ZXJuOgpgYGAKLiMuCi4uIwojIyMKYGBgCgpCZWNhdXNlIHRoZSBwYXR0ZXJuIGlzIGJvdGggMyBwaXhlbHMgd2lkZSBhbmQgMyBwaXhlbHMgdGFsbCwgaXQgaXMgc2FpZCB0byBoYXZlIGEgc2l6ZSBvZiAzLgoKVGhlbiwgdGhlIHByb2dyYW0gcmVwZWF0cyB0aGUgZm9sbG93aW5nIHByb2Nlc3M6CgpJZiB0aGUgc2l6ZSBpcyBldmVubHkgZGl2aXNpYmxlIGJ5IDIsIGJyZWFrIHRoZSBwaXhlbHMgdXAgaW50byAyeDIgc3F1YXJlcywgYW5kIGNvbnZlcnQgZWFjaCAyeDIgc3F1YXJlIGludG8gYSAzeDMgc3F1YXJlIGJ5IGZvbGxvd2luZyB0aGUgY29ycmVzcG9uZGluZyBlbmhhbmNlbWVudCBydWxlLgpPdGhlcndpc2UsIHRoZSBzaXplIGlzIGV2ZW5seSBkaXZpc2libGUgYnkgMzsgYnJlYWsgdGhlIHBpeGVscyB1cCBpbnRvIDN4MyBzcXVhcmVzLCBhbmQgY29udmVydCBlYWNoIDN4MyBzcXVhcmUgaW50byBhIDR4NCBzcXVhcmUgYnkgZm9sbG93aW5nIHRoZSBjb3JyZXNwb25kaW5nIGVuaGFuY2VtZW50IHJ1bGUuCkJlY2F1c2UgZWFjaCBzcXVhcmUgb2YgcGl4ZWxzIGlzIHJlcGxhY2VkIGJ5IGEgbGFyZ2VyIG9uZSwgdGhlIGltYWdlIGdhaW5zIHBpeGVscyBhbmQgc28gaXRzIHNpemUgaW5jcmVhc2VzLgoKVGhlIGFydGlzdCdzIGJvb2sgb2YgZW5oYW5jZW1lbnQgcnVsZXMgaXMgbmVhcmJ5ICh5b3VyIHB1enpsZSBpbnB1dCk7IGhvd2V2ZXIsIGl0IHNlZW1zIHRvIGJlIG1pc3NpbmcgcnVsZXMuIFRoZSBhcnRpc3QgZXhwbGFpbnMgdGhhdCBzb21ldGltZXMsIG9uZSBtdXN0IHJvdGF0ZSBvciBmbGlwIHRoZSBpbnB1dCBwYXR0ZXJuIHRvIGZpbmQgYSBtYXRjaC4gKE5ldmVyIHJvdGF0ZSBvciBmbGlwIHRoZSBvdXRwdXQgcGF0dGVybiwgdGhvdWdoLikgRWFjaCBwYXR0ZXJuIGlzIHdyaXR0ZW4gY29uY2lzZWx5OiByb3dzIGFyZSBsaXN0ZWQgYXMgc2luZ2xlIHVuaXRzLCBvcmRlcmVkIHRvcC1kb3duLCBhbmQgc2VwYXJhdGVkIGJ5IHNsYXNoZXMuIEZvciBleGFtcGxlLCB0aGUgZm9sbG93aW5nIHJ1bGVzIGNvcnJlc3BvbmQgdG8gdGhlIGFkamFjZW50IHBhdHRlcm5zOgpgYGAKLi4vLiMgID0gIC4uCiAgICAgICAgICAuIwoKICAgICAgICAgICAgICAgIC4jLgouIy4vLi4jLyMjIyAgPSAgLi4jCiAgICAgICAgICAgICAgICAjIyMKCiAgICAgICAgICAgICAgICAgICAgICAgICMuLiMKIy4uIy8uLi4uLyMuLiMvLiMjLiAgPSAgLi4uLgogICAgICAgICAgICAgICAgICAgICAgICAjLi4jCiAgICAgICAgICAgICAgICAgICAgICAgIC4jIy4KYGBgCgpXaGVuIHNlYXJjaGluZyBmb3IgYSBydWxlIHRvIHVzZSwgcm90YXRlIGFuZCBmbGlwIHRoZSBwYXR0ZXJuIGFzIG5lY2Vzc2FyeS4gRm9yIGV4YW1wbGUsIGFsbCBvZiB0aGUgZm9sbG93aW5nIHBhdHRlcm5zIG1hdGNoIHRoZSBzYW1lIHJ1bGU6CgpgYGAKLiMuICAgLiMuICAgIy4uICAgIyMjCi4uIyAgICMuLiAgICMuIyAgIC4uIwojIyMgICAjIyMgICAjIy4gICAuIy4KYGBgCgpTdXBwb3NlIHRoZSBib29rIGNvbnRhaW5lZCB0aGUgZm9sbG93aW5nIHR3byBydWxlczoKCmBgYAouLi8uIyA9PiAjIy4vIy4uLy4uLgouIy4vLi4jLyMjIyA9PiAjLi4jLy4uLi4vLi4uLi8jLi4jCmBgYApBcyBiZWZvcmUsIHRoZSBwcm9ncmFtIGJlZ2lucyB3aXRoIHRoaXMgcGF0dGVybjoKYGBgCi4jLgouLiMKIyMjCmBgYAoKVGhlIHNpemUgb2YgdGhlIGdyaWQgKDMpIGlzIG5vdCBkaXZpc2libGUgYnkgMiwgYnV0IGl0IGlzIGRpdmlzaWJsZSBieSAzLiBJdCBkaXZpZGVzIGV2ZW5seSBpbnRvIGEgc2luZ2xlIHNxdWFyZTsgdGhlIHNxdWFyZSBtYXRjaGVzIHRoZSBzZWNvbmQgcnVsZSwgd2hpY2ggcHJvZHVjZXM6CgpgYGAKIy4uIwouLi4uCi4uLi4KIy4uIwpgYGAKClRoZSBzaXplIG9mIHRoaXMgZW5oYW5jZWQgZ3JpZCAoNCkgaXMgZXZlbmx5IGRpdmlzaWJsZSBieSAyLCBzbyB0aGF0IHJ1bGUgaXMgdXNlZC4gSXQgZGl2aWRlcyBldmVubHkgaW50byBmb3VyIHNxdWFyZXM6CgpgYGAKIy58LiMKLi58Li4KLS0rLS0KLi58Li4KIy58LiMKYGBgCgpFYWNoIG9mIHRoZXNlIHNxdWFyZXMgbWF0Y2hlcyB0aGUgc2FtZSBydWxlICguLi8uIyA9PiAjIy4vIy4uLy4uLiksIHRocmVlIG9mIHdoaWNoIHJlcXVpcmUgc29tZSBmbGlwcGluZyBhbmQgcm90YXRpb24gdG8gbGluZSB1cCB3aXRoIHRoZSBydWxlLiBUaGUgb3V0cHV0IGZvciB0aGUgcnVsZSBpcyB0aGUgc2FtZSBpbiBhbGwgZm91ciBjYXNlczoKYGBgCiMjLnwjIy4KIy4ufCMuLgouLi58Li4uCi0tLSstLS0KIyMufCMjLgojLi58Iy4uCi4uLnwuLi4KYGBgCgpGaW5hbGx5LCB0aGUgc3F1YXJlcyBhcmUgam9pbmVkIGludG8gYSBuZXcgZ3JpZDoKCmBgYAojIy4jIy4KIy4uIy4uCi4uLi4uLgojIy4jIy4KIy4uIy4uCi4uLi4uLgpgYGAKClRodXMsIGFmdGVyIDIgaXRlcmF0aW9ucywgdGhlIGdyaWQgY29udGFpbnMgMTIgcGl4ZWxzIHRoYXQgYXJlIG9uLgoKSG93IG1hbnkgcGl4ZWxzIHN0YXkgb24gYWZ0ZXIgNSBpdGVyYXRpb25zPwoKCgojIExldCdzIGdvCgojIyMgUGFja2FnZXMgJiBmdW5jdGlvbnMKYGBge3IsIG1lc3NhZ2UgPSBGfQpsaWJyYXJ5KHRpZHl2ZXJzZSkKbGlicmFyeSh0ZXN0dGhhdCkKbGlicmFyeShhb2NvZGVSKQpgYGAKCgojIyBJbnB1dAoKPCEtLSBTdXBwbHkgZGF5LiBjb29raWVfcGF0aCBkZWZhdWx0cyB0byBwYXRoIGluIG15IHByb2plY3QgLS0+CmBgYHtyfQppbnB1dCA8LSBhb2NfZ2V0X2lucHV0KGRheSA9IDIxLCBjb29raWVfcGF0aCA9IHBhc3RlMChycHJvanJvb3Q6OmZpbmRfcnN0dWRpb19yb290X2ZpbGUoKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICIvc2VjcmV0cy9zZXNzaW9uX2Nvb2tpZS50eHQiKSkgCmBgYAoKIyMgRnVuY3Rpb25zCmBgYHtyfQpwYXQybWF0IDwtIGZ1bmN0aW9uKHBhdHRlcm4pewogICAgcGF0dGVybiAlPiUgc3Ryc3BsaXQoIi8iKSAlPiUgdW5saXN0ICU+JSBzdHJzcGxpdChudW1lcmljKCkpICAlPiUgZG8uY2FsbCgicmJpbmQiLCAuKQp9CgptYXQycGF0IDwtIGZ1bmN0aW9uKG0pewogICAgdmVjIDwtIGNiaW5kKG0sICIvIikgJT4lIHQgJT4lIGFzLnZlY3RvciAKICAgIHBhc3RlMCh2ZWNbLWxlbmd0aCh2ZWMpXSwgY29sbGFwc2UgPSAiIikKfQoKZmxpcF9oIDwtIGZ1bmN0aW9uKG0pewogICAgbVssbmNvbChtKToxXSAlPiUgbWF0MnBhdAp9CmZsaXBfdiA8LSBmdW5jdGlvbihtKXsKICAgIG1bbnJvdyhtKToxLF0gJT4lIG1hdDJwYXQKfQoKcm90XzkwIDwtIGZ1bmN0aW9uKG0pewogICAgdChtW25yb3cobSk6MSxdKSAlPiUgbWF0MnBhdAp9Cgpyb3RfMTgwIDwtIGZ1bmN0aW9uKG0pewogICAgbVtucm93KG0pOjEsbmNvbChtKToxXSAlPiUgbWF0MnBhdAp9Cgpyb3RfMjcwIDwtIGZ1bmN0aW9uKG0pewogICAgdChtKVtuY29sKG0pOjEsXSAlPiUgbWF0MnBhdAp9CgplbmhhbmNlbWVudHMgPC0gZnVuY3Rpb24oeCwgYWxsID0gVCl7CiAgICBtIDwtIHBhdDJtYXQoeFsxXSkKICAgIGlmKGFsbCl7CiAgICB0aWJibGUobWF0Y2ggPSBjKG1hdDJwYXQobSksIGZsaXBfaChtKSwgZmxpcF92KG0pLCAKICAgICAgICAgICAgICAgICAgICAgcm90XzkwKG0pLCByb3RfMTgwKG0pLCByb3RfMjcwKG0pKSwKICAgICAgICAgICBlbmhhbmNlID0geFsyXSkgJT4lIHVuaXF1ZQogICAgfWVsc2V7CiAgICAgICAgdGliYmxlKG1hdGNoID0geFsxXSwgZW5oYW5jZSA9IHhbMl0pCiAgICB9Cn0KCmVuaGFuY2VtZW50X3RibCA8LSBmdW5jdGlvbihpbnB1dCwgYWxsID0gVCl7CiAgICBsIDwtIGlucHV0ICU+JSBnc3ViKCIjIiwgMSwgLikgJT4lIGdzdWIoIlxcLiIsIDAsIC4pICU+JSAKICAgIHN0cnNwbGl0KC4sICJcbiIpICU+JSB1bmxpc3QgJT4lIHN0cnNwbGl0KC4sICIgPT4gIikgJT4lIAogICAgICAgIG1hcF9kZnIoZW5oYW5jZW1lbnRzLCBhbGwpCn0KCmdldF9lbmhhbmNlbWVudCA8LSBmdW5jdGlvbihweCwgdGJsKXsKICAgIHRibCAlPiUgZmlsdGVyKG1hdGNoICVpbiUgKHB4ICU+JSBtYXQycGF0ICU+JSBlbmhhbmNlbWVudHMoYWxsID0gVCkgJT4lIHB1bGwobWF0Y2gpKSkgJT4lIAogICAgICAgIHB1bGwoZW5oYW5jZSkgJT4lIHVuaXF1ZQp9CgpnZXRfcmNpIDwtIGZ1bmN0aW9uKG0sIG4pewogICAgcmcgPC0gKHJvdyhtKS0xKSAlLyUgbiArIDEKICAgIGNnIDwtIChjb2wobSktMSkgJS8lIG4gKyAxCiAgICAocmctMSkqbWF4KGNnKSArIGNnCn0KCm1hdHNwbGl0dGVyPC1mdW5jdGlvbihtLCBkaXYpIHsKICAgIHJjaSA8LSAgZ2V0X3JjaShtLCBkaXYpCiAgICBuIDwtIHByb2QoZGltKG0pKS9kaXYvZGl2CiAgICBjdiA8LSB1bmxpc3QobGFwcGx5KDE6biwgZnVuY3Rpb24oeCkgbVtyY2k9PXhdKSkKICAgIGRpbShjdik8LWMoZGl2LGRpdixuKQogICAgY3YKfSAKCnBpeF9sMm1hdCA8LSBmdW5jdGlvbihsLCBucHgsIGV4cCl7CiAgICBuc2l6ZSA8LSBucHggKiBleHAKICAgIG0gPC0gbWF0cml4KDAsIG5jb2wgPSBuc2l6ZSwgbnJvdyA9IG5zaXplKQogICAgcmNpIDwtIGdldF9yY2kobSwgZXhwKQogICAgZm9yKGkgaW4gMTpsZW5ndGgobCkpewogICAgICAgIG1bcmNpID09IGldIDwtIGxbW2ldXQogICAgfQogICAgbQp9CgplbmhhbmNlX3B4IDwtIGZ1bmN0aW9uKHB4LCB0YmwpewogICAgc2l6ZSA8LSBweCAlPiUgZGltICU+JSB1bmlxdWUKICAgIGlmKHNpemUgJSUgMiA9PSAwKXsKICAgICAgICBkaXYgPC0gMgogICAgICAgIGV4cCA8LSAzfWVsc2V7CiAgICAgICAgICAgIGRpdiA8LSAzCiAgICAgICAgICAgIGV4cCA8LSA0fQogICAgbnB4IDwtIHNpemUvZGl2CiAgICBhcHBseShtYXRzcGxpdHRlcihweCwgZGl2KSwgMywgRlVOID0gZ2V0X2VuaGFuY2VtZW50LCB0YmwgPSB0YmwpICU+JSAKICAgICAgICBsYXBwbHkocGF0Mm1hdCkgJT4lIHBpeF9sMm1hdChucHgsIGV4cCkKfQoKaXRlcl9lbmhhbmNlbWVudCA8LSBmdW5jdGlvbihpdGVyLCBpbnB1dCl7CiAgICB0YmwgPC0gZW5oYW5jZW1lbnRfdGJsKGlucHV0LCBhbGwgPSBUKQogICAgcHggPC0gIjAxMC8wMDEvMTExIiAlPiUgcGF0Mm1hdAogICAgZm9yKGkgaW4gMTppdGVyKXsKICAgICAgICB0MCA8LSBTeXMudGltZSgpCiAgICAgICAgcHggPC0gZW5oYW5jZV9weChweCwgdGJsKQogICAgICAgIGNhdChpLCAiLS0gdCIsIFN5cy50aW1lKCkgLSB0MCwgIlxuIikKICAgIH0KICAgIHB4Cn0KYGBgCgojIyBUZXN0CmBgYHtyfQojZXhwZWN0X2VxdWFsKCwpCmBgYAoKIyMgZGVwbG95CgpgYGB7cn0KaXRlcl9lbmhhbmNlbWVudCg1LCBpbnB1dCkgJT4lIGFzLm51bWVyaWMgJT4lIHN1bQpgYGAKCgojIyBTdWNjZXNzIQoKPGlmcmFtZSBzcmM9Imh0dHBzOi8vZ2lwaHkuY29tL2VtYmVkLzEyMXMyNEI3TG8zV0NzIiB3aWR0aD0iNDgwIiBoZWlnaHQ9IjMyMiIgZnJhbWVCb3JkZXI9IjAiIGNsYXNzPSJnaXBoeS1lbWJlZCIgYWxsb3dGdWxsU2NyZWVuPjwvaWZyYW1lPjxwPjxhIGhyZWY9Imh0dHBzOi8vZ2lwaHkuY29tL2dpZnMvMTIxczI0QjdMbzNXQ3MiPnZpYSBHSVBIWTwvYT48L3A+Cgo8YnI+CgoqKioKCiMgLS0tLSBQYXJ0IDIgLS0tLQoKCiMjIEJyaWVmCjwhLS0gSW5zZXJ0IFBhcnQgMiBvZiB0aGUgcHV6emxlIGJyaWVmIGhlcmUgLS0+CgoKIyBMZXQncyBnbwoKIyMgVGVzdApgYGB7cn0KI2V4cGVjdF9lcXVhbCgsKQpgYGAKCiMjIGRlcGxveQoKIyMjIE5FRURTIFJFVklTVElORyBGT1IgU1BFRUQgVVAhCgpJJ20gZ29pbmcgdG8gdHJ5IGFuZCBwZXJmb3JtIHRoZSBlbmhhbmNlbWVudCB3aXRob3V0IGJ1aWxkaW5nIHRoZSBmdWxsIG1hdHJpeCwgYnV0IHJhdGhlciwga2VlcCBpdCBpbiB0aGUgY29tcGFjdCBgLi4jLyMuI2Agbm90YXRpb24KYGBge3J9Cml0ZXJfZW5oYW5jZW1lbnQoMTgsIGlucHV0KSAlPiUgYXMubnVtZXJpYyAlPiUgc3VtCmBgYAoKIyMgU3VjY2VzcyEKCiFbXSguLi9zY3JlZW5zaG90cy9EYXkxXzIucG5nKQoKPGJyPgoKKioqCgp0ZW1wbGF0ZSBiYXNlZCBvbiB0aGUgW3dvcmtmbG93cl0oaHR0cHM6Ly9naXRodWIuY29tL2pkYmxpc2NoYWsvd29ya2Zsb3dyKSBzdGFuZGFsb25lIHRlbXBsYXRlCg==