— Day 21: Fractal Art —

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