— Day 14: Disk Defragmentation —

Last updated: 2017-12-16

Code version: aa59a2a

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] BMS_0.3.4          PKI_0.1-5.1        base64enc_0.1-3    sodium_1.1         magrittr_1.5      
 [6] ggplot2_2.2.1.9000 withr_2.1.0.9000   jsonlite_1.5       igraph_1.1.2       rlist_0.4.6.1     
[11] bindrcpp_0.2       aocodeR_0.1.1      testthat_1.0.2     forcats_0.2.0      stringr_1.2.0     
[16] dplyr_0.7.4        purrr_0.2.4        readr_1.1.1        tidyr_0.7.2        tibble_1.3.4      
[21] tidyverse_1.2.1   

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

Brief

Suddenly, a scheduled job activates the system’s disk defragmenter. Were the situation different, you might sit and watch it for a while, but today, you just don’t have that kind of time. It’s soaking up valuable system resources that are needed elsewhere, and so the only option is to help it finish its task as soon as possible.

The disk in question consists of a 128x128 grid; each square of the grid is either free or used. On this disk, the state of the grid is tracked by the bits in a sequence of knot hashes.

A total of 128 knot hashes are calculated, each corresponding to a single row in the grid

• each hash contains 128 bits which correspond to individual grid squares.
  • Each bit of a hash indicates whether that square is free (0) or used (1).

---

Recreate hash from inputs

The hash inputs are

• a key string (your puzzle input),
• a dash
• a number from 0 to 127 corresponding to the row.

1. Calculate knot hash for each row (to 32-bit hex)

For example, if your key string were flqrgnkx, then the first row would be given by the bits of the knot hash of flqrgnkx-0, the second row from the bits of the knot hash of flqrgnkx-1, and so on until the last row, flqrgnkx-127.

• The output of a knot hash is traditionally represented by 32 hexadecimal digits; each of these digits correspond to 4 bits, for a total of 4 * 32 = 128 bits.

1. Convert to bits (32 Hex to binary)

To convert to bits, turn each hexadecimal digit to its equivalent binary value, high-bit first: 0 becomes 0000, 1 becomes 0001, e becomes 1110, f becomes 1111, and so on;

a hash that begins with a0c2017... in hexadecimal would begin with 10100000110000100000000101110000... in binary.

00001010000011000010000000010111

Continuing this process, the first 8 rows and columns for key flqrgnkx appear as follows, using # to denote used squares, and . to denote free ones:

##.#.#..-->
.#.#.#.#   
....#.#.   
#.#.##.#   
.##.#...   
##..#..#   
.#...#..   
##.#.##.-->
|      |   
V      V   

In this example, 8108 squares are used across the entire 128x128 grid.

Given your actual key string, how many squares are used?

Let’s go

Packages & functions

library(tidyverse)
library(testthat)
library(aocodeR)
library(sodium)
library(BMS)

Input

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

[1] "ugkiagan"

Functions

knot <- function(l.input = input, v = 0:255, 
                 skip = 0, cp = 1, cycles = 1, hex = F) {
    
    if(hex){l.input <- l.input %>% hex.l} else{
        l.input <- l.input %>% strsplit(",") %>% unlist %>% as.numeric
    }
    # intitialise algorithm
    lv <- length(v)
    
    for(i in rep(1:length(l.input), cycles)){
        l <- l.input[i] 
        # twist
        tc<- cp:(cp - 1 + l) %% lv %>% recode(`0` = lv)
        v[tc] <- v[rev(tc)]
        
        # move cp
        cp <- (cp + l + skip) %% lv 
        if (cp == 0){cp <- lv} #fix %% 0s
        
        # update params
        skip <- skip + 1
        i <- i + 1
    }
    v
}
hex.l <- function(input= "1,2,3") {
   c(utf8ToInt(input) , c(17, 31, 73, 47, 23))
}
hash <- function(input, ...) {
    input %>% 
        knot(v = 0:255, cycles = 64, hex = T) %>% 
        split(., ceiling(seq_along(.)/16)) %>% 
        map_int(~reduce(.x, bitwXor)) %>%
        as.hexmode %>%
        paste(collapse = "")
}
key2sum <- function(x) {
    x %>% hash %>% paste(collapse = "") %>% BMS::hex2bin() %>% sum
}
sq_used <- function(key_string) {
    key_string %>% paste(0:127, sep = "-") %>% map(key2sum) %>% unlist %>% sum
}

Test

There was an error in the example and example output needed the last 0000s trimming

expect_equal(BMS::hex2bin("a0c2017 ") %>% paste(collapse = ""), "1010000011000010000000010111")
#expect_equal(sq_used("flqrgnkx"), 8186)

deploy

sq_used(input)

[1] 8292

Success!

via GIPHY

---

—- Part 2 —-

Now, all the defragmenter needs to know is the number of regions. A region is a group of used squares that are all adjacent, not including diagonals. Every used square is in exactly one region: lone used squares form their own isolated regions, while several adjacent squares all count as a single region.

In the example above, the following nine regions are visible, each marked with a distinct digit:

11.2.3..–> .1.2.3.4
….5.6.
7.8.55.9
.88.5…
88..5..8
.8…8..
88.8.88.–> | |
V V
Of particular interest is the region marked 8; while it does not appear contiguous in this small view, all of the squares marked 8 are connected when considering the whole 128x128 grid. In total, in this example, 1242 regions are present.

How many regions are present given your key string?

Brief

Let’s go

#m <- matrix(c(1, 0, 1, 1, 1, 1, 1,0, 1, 1, 0, 1), ncol = 4, byrow = T)
key2bin <- function(x) {
    x %>% hash %>% paste(collapse = "") %>% BMS::hex2bin()
}
key2mat <- function(key_string) {
    key_string %>% paste(0:128, sep = "-") %>% map(key2bin) %>% do.call("rbind", .)
}
group_matrix <- function(m) {
    mg <- m   
    mg[,] <- 0
    xs <- rep(1:nrow(m), each = ncol(m)) 
    ys <- rep(1:ncol(m), times = nrow(m))
    #length(xs)
    for(i in 1:161){
        loc <- c(xs[i], ys[i])   
        g0 <- max(mg) + 1
        if(m[loc[1], loc[2]] == 0){
            next
        }
        x <- loc[1] -1
        y <- loc[2] -1
        gx <- if(x == 0){0}else{mg[x, loc[2]]}
        gy <- if(y == 0){0}else{mg[loc[1], y]}
        if(gx == 0 & gy == 0){
            mg[loc[1], loc[2]] <- g0
        }else{
            min_g <- min(c(gx,gy) %>% magrittr::extract(. > 0))
            m_i <- m   
            m_i[,] <- F
            if(gx != 0){
                m_i <- m_i | (mg == gx)
            }
            if(gy != 0){
                m_i <- m_i | (mg == gy)
            }
            m_i[loc[1], loc[2]] <- T
            mg[m_i] <- min_g
        }
        
    }
    mg
}
no_groups <- function(mg) {
    mg %>% as.vector %>% unique %>% magrittr::extract(. > 0) %>% length
}

Test

m %>% group_matrix %>% no_groups

[1] 1242

deploy

input %>% key2mat %>% group_matrix %>% no_groups

[1] 1069

Success!

via GIPHY

---

template based on the workflowr standalone template