By Eric Burden | December 8, 2020
In the spirit of the holidays (and programming), I’ll be posting my solutions to the Advent of Code 2020 puzzles here, at least one day after they’re posted (no spoilers!). I’ll be implementing the solutions in R because, well, that’s what I like! What I won’t be doing is posting any of the actual answers, just the reasoning behind them.
Also, as a general convention, whenever the puzzle has downloadable input, I’m
saving it in a file named input.txt.
Day 7 - Handy Haversacks
Find the problem description HERE.
Part One - It’s Bags all the Way Down
This one is a lot! First, we are led to believe that the only thing anyone is packing in their luggage for these flights is more, smaller luggage. Second of all, this puzzle was a head-scratcher! Partly because of the puzzle, and partly from wrestling with lists to get them in the format I wanted when ingesting the bag-stuffing rules. I seemed to keep ending up with lists nested either one level too deep or not nested deeply enough. As a result, you may note that most of the code here is dedicated to parsing the input.
library(stringr) # For `str_extract()`, `str_split()`
library(purrr) # For `map()`, `map_lgl()`
test_input <- c(
"light red bags contain 1 bright white bag, 2 muted yellow bags.",
"dark orange bags contain 3 bright white bags, 4 muted yellow bags.",
"bright white bags contain 1 shiny gold bag.",
"muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.",
"shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.",
"dark olive bags contain 3 faded blue bags, 4 dotted black bags.",
"vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.",
"faded blue bags contain no other bags.",
"dotted black bags contain no other bags."
)
real_input <- readLines('input.txt')
# BIG helper function, given a single line from the input file, converts that
# line into a list that can be combined with other lists to give a full
# mapping of the bag-stuffing topology. An example structure will be included
# below this code block.
parse_rule <- function(rule_str) {
rule_name <- str_extract(rule_str, '^[a-z\\s]+bag(?=s\\s)') # Extract the parent bag name
rule_vals <- str_extract_all(rule_str, '\\d[a-z\\s]+bag') # Extract the child bag names and numbers
# This bit converts the character strings from `rule_vals` (ex. 1 bright
# white bag, 2 muted yellow bags) to named lists in the format of
# list('bright white bag' = 1, 'muted yellow bag' = 2)
rule_details <- str_split(unlist(rule_vals), '(?<=\\d)\\s')
rule_details <- map(rule_details, function(x) {
rd <- list(as.numeric(x[1]))
names(rd) <- x[2]
rd
})
# Pure list manipulation, returns a 'rule' in the format of
# list('light red bag' = list('bright white bag' = 1, 'muted yellow bag' = 2))
result <- list(unlist(rule_details, recursive = F))
names(result) <- rule_name
result
}
# Helper function, takes a list of rule strings (lines from the input) and
# leverages `parse_rule()` to return a list of 'rules' in the format described
# above
parse_rules <- function(rule_strs) {
rules <- map(rule_strs, parse_rule)
unlist(rules, recursive = F)
}
# Main function, given a bag type ('light red bag'), a target bag type
# ('shiny gold bag'), and the list of rules, recurses through the list of rules
# and returns TRUE if the `target_type` is anywhere in the descendants of the
# `bag_type`, otherwise FALSE
target_bag_inside <- function(bag_type, target_type, rules) {
if (is.null(rules[bag_type])) { return(FALSE) }
for (child_type in names(rules[[bag_type]])) {
if (child_type == target_type) { return(TRUE) }
if (target_bag_inside(child_type, target_type, rules)) { return(TRUE) }
}
return(FALSE)
}
rules <- parse_rules(real_input) # Parse all the rules from the input
# Maps over the list of bag types (the keys in the `rules` named list) and
# searches each type for a 'shiny gold bag' somewhere down deep inside
target_found <- map_lgl(names(rules), target_bag_inside, 'shiny gold bag', rules)
answer <- sum(target_found) # The number of bag types returning TRUE
I’m leaving in the test_inputs to demonstrate how I go about testing these
scripts as I write them, essentially just running them on the given test input
until I can reliably (and understandably) get the right answer.
As I said, the input parsing was the major struggle here. It’s probably me, but R’s syntax for rearranging lists can be frustrating at times. I eventually ended up with input data in the format of:
List of 9
$ light red bag :List of 2
..$ bright white bag: num 1
..$ muted yellow bag: num 2
$ dark orange bag :List of 2
..$ bright white bag: num 3
..$ muted yellow bag: num 4
$ bright white bag:List of 1
..$ shiny gold bag: num 1
$ muted yellow bag:List of 2
..$ shiny gold bag: num 2
..$ faded blue bag: num 9
$ shiny gold bag :List of 2
..$ dark olive bag : num 1
..$ vibrant plum bag: num 2
$ dark olive bag :List of 2
..$ faded blue bag : num 3
..$ dotted black bag: num 4
$ vibrant plum bag:List of 2
..$ faded blue bag : num 5
..$ dotted black bag: num 6
$ faded blue bag : NULL
$ dotted black bag: NULL
You can see that, for the example, the ‘faded blue bag’ and ‘dotted black bag’
formed our base case, so the recursive function could stop and start pushing
FALSE back up the stack if it hit one of those, or TRUE if it finds a
‘shiny gold bag’
Part Two - Bag of Holding
Now we’re getting to the real question: How many bags are we supposed to have in our ‘shiny gold bag’ anyway. Also, why are ‘shiny gold bag’s even on this list? Are there enough people out there bringing those on planes to have warranted inclusion in the rules list? Probably at least as many as ‘mirrored fuchsia’. The good news is, our input processing code is already written, now it’s just a matter of counting instead of searching.
# We really did need another test input
test_input2 <- c(
"shiny gold bags contain 2 dark red bags.",
"dark red bags contain 2 dark orange bags.",
"dark orange bags contain 2 dark yellow bags.",
"dark yellow bags contain 2 dark green bags.",
"dark green bags contain 2 dark blue bags.",
"dark blue bags contain 2 dark violet bags.",
"dark violet bags contain no other bags."
)
# New main function, given a bag type and the list of rules parsed from the
# input, count the number of bags required inside a bag of type `bag_type`.
bag_contains <- function(bag_type, rules) {
if (is.null(rules[[bag_type]])) { return(0) } # Base case now yields 0
total_bags <- 0
for (child_type in names(rules[[bag_type]])) {
result <- bag_contains(child_type, rules) # Bags this child contains
children <- rules[[bag_type]][[child_type]] # Number of children
# Add the number of bags the childre contain, plus the number of
# child bags (they count, too)
total_bags <- total_bags + (result * children) + children
}
return(total_bags)
}
rules <- parse_rules(real_input)
bags_in_bag <- bag_contains('shiny gold bag', rules) # The answer
Important note, my first stab at this main function succeeded wonderfully on
test_input2, but failed on test_input1 in ways that left me puzzling for
a while. The other major ‘breakthrough’ was adding in the number of children
to the accumulating total, otherwise you severely under-count. A ‘dark blue’
bag with two ‘dark violet’ bags inside it is three bags, after all.
Wrap-Up
Not going to lie, this one was a bit tough, taking me about two-three times as long to solve as Day 6. I spent almost as much time on this one as I did on Day 1, and that’s because I couldn’t be satisfied until I implemented like five different ways to solve Day 1… That said, the feeling of accomplishment was nice. I hope to see more challenges like this in the days ahead. Today also provided a really nice use case for recursion, something I’m appreciating more and more.
If you found a different solution (or spotted a mistake in one of mine), please drop me a line!