Last updated: 2017-12-08

Code version: 657bc69

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: /Library/Frameworks/R.framework/Versions/3.4/Resources/lib/libRblas.0.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  backports_1.1.1 magrittr_1.5    rprojroot_1.2  
 [5] tools_3.4.2     htmltools_0.3.6 yaml_2.1.15     Rcpp_0.12.14   
 [9] stringi_1.1.6   rmarkdown_1.8   knitr_1.17      git2r_0.19.0   
[13] stringr_1.2.0   digest_0.6.12   evaluate_0.10.1

Brief

Wandering further through the circuits of the computer, you come upon a tower of programs that have gotten themselves into a bit of trouble. A recursive algorithm has gotten out of hand, and now they’re balanced precariously in a large tower.

One program at the bottom supports the entire tower. It’s holding a large disc, and on the disc are balanced several more sub-towers. At the bottom of these sub-towers, standing on the bottom disc, are other programs, each holding their own disc, and so on. At the very tops of these sub-sub-sub-…-towers, many programs stand simply keeping the disc below them balanced but with no disc of their own.

You offer to help, but first you need to understand the structure of these towers. You ask each program to yell out their name, their weight, and (if they’re holding a disc) the names of the programs immediately above them balancing on that disc. You write this information down (your puzzle input). Unfortunately, in their panic, they don’t do this in an orderly fashion; by the time you’re done, you’re not sure which program gave which information.

For example, if your list is the following:

pbga (66)
xhth (57)
ebii (61)
havc (66)
ktlj (57)
fwft (72) -> ktlj, cntj, xhth
qoyq (66)
padx (45) -> pbga, havc, qoyq
tknk (41) -> ugml, padx, fwft
jptl (61)
ugml (68) -> gyxo, ebii, jptl
gyxo (61)
cntj (57)

…then you would be able to recreate the structure of the towers that looks like this:

                gyxo
              /     
         ugml - ebii
       /      \     
      |         jptl
      |        
      |         pbga
     /        /
tknk --- padx - havc
     \        \
      |         qoyq
      |             
      |         ktlj
       \      /     
         fwft - cntj
              \     
                xhth

In this example, tknk is at the bottom of the tower (the bottom program), and is holding up ugml, padx, and fwft. Those programs are, in turn, holding up other programs; in this example, none of those programs are holding up any other programs, and are all the tops of their own towers. (The actual tower balancing in front of you is much larger.)

Before you’re ready to help them, you need to make sure your information is correct. What is the name of the bottom program?

Let’s go

Packages & functions

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

Input

input <- aoc_get_input(day = 7, cookie_path = paste0(rprojroot::find_rstudio_root_file(),
                                                 "/secrets/session_cookie.txt")) %>% strsplit("[[\\]]|[^[:print:]]") %>% unlist 
input %>% head()
[1] "keztg (7)"                                      
[2] "uwbtawx (9)"                                    
[3] "mgyhaax (46)"                                   
[4] "fuvokrr (14) -> pnjbsm, glrua"                  
[5] "cymmj (257) -> phyzvno, pmfprs, ozgprze, bgjngh"
[6] "goilxo (80)"

Functions

find_base <- function(input){
  edges <- input %>% grep("->", ., value = T) 
  base_node <- gsub(" \\(.*$", "", edges)
  first_node <- gsub("^.*-> ", "", edges) %>% strsplit(", ") %>% unlist
  base_node[which(!(base_node %in% first_node))]
}

Test

#expect_equal(,)

deploy

find_base(input)
[1] "veboyvy"

Success!


—- Part 2 —-

Brief

The programs explain the situation: they can’t get down. Rather, they could get down, if they weren’t expending all of their energy trying to keep the tower balanced. Apparently, one program has the wrong weight, and until it’s fixed, they’re stuck here.

For any program holding a disc, each program standing on that disc forms a sub-tower. Each of those sub-towers are supposed to be the same weight, or the disc itself isn’t balanced. The weight of a tower is the sum of the weights of the programs in that tower.

In the example above, this means that for ugml’s disc to be balanced, gyxo, ebii, and jptl must all have the same weight, and they do: 61.

However, for tknk to be balanced, each of the programs standing on its disc and all programs above it must each match. This means that the following sums must all be the same:

ugml + (gyxo + ebii + jptl) = 68 + (61 + 61 + 61) = 251
padx + (pbga + havc + qoyq) = 45 + (66 + 66 + 66) = 243
fwft + (ktlj + cntj + xhth) = 72 + (57 + 57 + 57) = 243

As you can see, tknk’s disc is unbalanced: ugml’s stack is heavier than the other two. Even though the nodes above ugml are balanced, ugml itself is too heavy: it needs to be 8 units lighter for its stack to weigh 243 and keep the towers balanced. If this change were made, its weight would be 60.

Given that exactly one program is the wrong weight, what would its weight need to be to balance the entire tower?

Functions

So much code :(

# compile node relationships
attach_to_base <- function(input, base_node = find_base(input)){
  edges <- input %>% grep("->", ., value = T) 
  base_nodes <- gsub(" \\(.*$", "", edges)
  gsub("^.*-> ", "", edges) %>% strsplit(", ") %>% setNames(base_nodes)
  }

# get weights for each node
get_weights <- function(input){
    base_names <- input %>% gsub(" \\(.*$", "", .)
 input %>% gsub("[^0-9]", "", .) %>% as.numeric %>% setNames(base_names)
       }

# get node info for a given depth
get_nodes_depth <- function(base, depth, 
                            nodes = nodes, wts = wts){
    nds <- nodes[[base]]
    if(!is.null(nds)){ 
        tibble(base = base, nodes = nds, wts = wts[nds], depth = depth)
    }
}

# iterate across all depths    
get_nodes_tbl <- function(start_node = "veboyvy", wts = wts){
    i = 0
    df <- tibble(base = NA, nodes = start_node,  wts = wts["veboyvy"], depth = i)
    base <- df %>% filter(depth == i) %>% pull(nodes)
    while(length(base) > 0){
        i <- i + 1
        df <- bind_rows(df, base %>% map_dfr(get_nodes_depth, i, nodes, wts))
        base <- df %>% filter(depth == i) %>% pull(nodes)
    }
    df
}

# find unbalanced tower
check_tower_balance <- function(df){
    for(depth.i in max(df$depth):min(df$depth)){    
        sum_df <- df %>% filter(depth == depth.i) %>% group_by(base) %>% 
            summarise(sum_below = sum(wts),
                      depth = depth.i - 1, 
                      unbalanced = length(unique(wts)) != 1) 
        
        if(any(sum_df$unbalanced)){
            return(df %>% filter(depth == depth.i, 
                                 base %in% sum_df$base[sum_df$unbalanced]))
        }else{
            sum_df <- sum_df %>% mutate(nodes = base) %>% select(-unbalanced, -base)
        }
        
        df <- df %>% left_join(sum_df, by = c("nodes", "depth")) %>% 
            mutate(wts = case_when(
                is.na(sum_below) ~ wts,
                TRUE ~ wts + sum_below)) %>% 
            select(base:depth)
    }
}

# get the value neede to balance the tower
get_unbalance <- function(check_out){
    comp <- check_out %>% count(wts) %>% arrange(n) 
    wts[check_out$nodes[check_out$wts == pull(comp, "wts")[1]]] + 
        (comp  %>% pull(wts) %>% diff)
}

Let’s go

Test - abort - going in without testing

#expect_equal(,)

deploy

wts <- get_weights(input)
nodes <- attach_to_base(input)

get_nodes_tbl(start_node = find_base(input), wts = wts) %>% 
    check_tower_balance %>%
    get_unbalance
obxrn 
  749

Here’s what the functions do

get_weights(input) %>% head
  keztg uwbtawx mgyhaax fuvokrr   cymmj  goilxo 
      7       9      46      14     257      80 
attach_to_base(input) %>% head
$fuvokrr
[1] "pnjbsm" "glrua" 

$cymmj
[1] "phyzvno" "pmfprs"  "ozgprze" "bgjngh" 

$cumfrfc
[1] "yjivxcf" "swqkqgz"

$lkdkyk
[1] "oldwss" "nadxwf"

$iqsztjd
[1] "hovelvz" "pndcqot" "naglm"   "oxxlsk" 

$nxdkpuh
[1] "yhcsc"   "ydmeqtl"
df <- get_nodes_tbl(start_node = find_base(input), wts = wts)
df
# A tibble: 1,452 x 4
      base   nodes   wts depth
     <chr>   <chr> <dbl> <dbl>
 1    <NA> veboyvy    61     0
 2 veboyvy qwjmobb 28425     1
 3 veboyvy   fmarl  5688     1
 4 veboyvy  hqxdyv 17568     1
 5 veboyvy fhphiyb 45183     1
 6 veboyvy  cmmqbz 29868     1
 7 veboyvy  kqoigs    53     1
 8 qwjmobb ohusizx  9151     2
 9 qwjmobb   gqoxv  1646     2
10 qwjmobb  xatjlb    40     2
# ... with 1,442 more rows
df %>% check_tower_balance
# A tibble: 6 x 4
    base   nodes   wts depth
   <chr>   <chr> <dbl> <dbl>
1 apktiv   obxrn  1116     3
2 apktiv kqaksir  1109     3
3 apktiv   itjrw  1109     3
4 apktiv supnaxw  1109     3
5 apktiv   wuefg  1109     3
6 apktiv   twtcx  1109     3

FinallY…Success!

What a palava though. This puzzle really did my head in as I kept hitting dead ends trying to work recursively with lists. Had to completely change course after quite some effort and am sure my solution is convoluted and cumbersome but I’m sure glad it’s done. So glad in fact, I’m gonna flash what the calendar is looking like to make myself feel better!


template based on the workflowr standalone template