Advent of Code 2020 Day 7
Try the simulator!
Task: Solve for X where...
X = the number of bag types (a.k.a. colors) that can contain at least one shiny gold bag
Example input
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.
It represents:
- A different bag color per line
- The required contents of each colored bag
Part 1
- Considering an effective data structure for the rules
- Considering the speed of a possible algorithm
- Extracting the important information from each line
- Building a dictionary from each list of captured matches
- Considering an inside-out algorithm
- Writing the working inside-out algorithm
- Building a simulator to step through each containing set of bags
Considering an effective data structure for the rules
How about a dictionary, hash table or object?
'light red': ['bright white', 'muted yellow'],
'dark orange': ['bright white', 'muted yellow'],
'bright white': ['shiny gold'],
'muted yellow': ['shiny gold', 'faded blue'],
'shiny gold': ['dark olive', 'vibrant plum'],
'dark olive': ['faded blue', 'dotted black'],
'vibrant plum': ['faded blue', 'dotted black'],
'faded blue': [],
'dotted black': []
If we followed each bag to it's deepest node, by recursively checking each color's contained bags for entries that are not in our originating bag's list:
'light red': ['bright white', 'shiny gold', 'dark olive', 'faded blue', 'dotted black', 'vibrant plum', 'muted yellow'],
'dark orange': ['bright white', 'shiny gold', 'dark olive', 'faded blue', 'dotted black', 'vibrant plum', 'muted yellow'],
'bright white': ['shiny gold', 'dark olive', 'faded blue', 'dotted black', 'vibrant plum'],
'muted yellow': ['shiny gold', 'dark olive', 'dotted black', 'vibrant plum', 'faded blue'],
'shiny gold': ['dark olive', 'faded blue', 'dotted black', 'vibrant plum'],
'dark olive': ['faded blue', 'dotted black'],
'vibrant plum': ['faded blue', 'dotted black'],
'faded blue': [],
'dotted black': []
Then, checking each key's list for shiny gold
:
'light red'
'dark orange'
'bright white'
'muted yellow'
4 colors, which matches the answer given in the instructions!
However, my puzzle input is several hundred lines long.
So this exact approach may take a while.
Considering the speed of a possible algorithm
[Must-do] Parse the list to generate the dictionary
[Yikes!] For each bag, expand its containment list to account for unique new entries from the contents of each bag's containment list
[Look-ups seem fast] For each bag, check if `shiny gold` is in each containment list
[No problem] Return the length of the filtered list
Extracting the important information from each line
It appears this may require the use of a regular expression:
Variations:
light red bags contain 1 bright white bag, 2 muted yellow bags.
bright white bags contain 1 shiny gold bag.
dotted black bags contain no other bags.
Initial thoughts on the formula:
Quasi-english/regex
/word word bags contain [no other bags|(number word word bags?,? ?)+./g
Let's try this using Regexr.com
Flash forward to later that day...
- I didn't get the above regular expression to work when matching the entire puzzle input string
- It was too greedy - it matched too long of a substring for the second part
- But I did get a regular expression to work when limited in scope to each line
Here's the Regex I used to capture 2+ groups per line:
/(\w+\s\w+)\sbags?/g
Capture group:
- 1 or more letters
- Followed by a space
- 1 or more letters
Other important characters
- Followed by a space
- Then the letters 'bag'
- Then, optionally, the letter 's'
For a line like this:
light red bags contain 1 bright white bag, 2 muted yellow bags.
It matches:
light red bags
bright white bag
muted yellow bags
And captures:
light red
bright white
muted yellow
Building a dictionary from each list of captured matches
Create a dictionary, rules, that starts empty
For each list item - which contains two or more elements: 1. the containing bag, 2. either 'no other' or the first of one or more contained bags, 3. additionally contained bags
Create a key in rules with the label of the first element
Set as its value an empty list
As long as the second element is not 'no other'
Add each subsequent element to the initially empty list associated with the newly created key
By now, using the example input, I have this as the first created key-value pair:
'light red': [ 'bright white', 'muted yellow' ]
And in the case where I started with this:
faded blue bags contain no other bags.
I now have:
'faded blue': []
Considering an inside-out algorithm
While walking my dog, I discovered a far more seemingly expedited way to solve this puzzle.
Recalling what I'm solving for:
- I need a count of all bag types that eventually contain
shiny gold
bags
Perhaps I start with this single-element list:
['shiny gold']
Then I check each key's associated list for the inclusion of that value.
That would give me a list of all bags that directly contain shiny gold
bags (a.k.a. parent bags).
Using the example input, that list will be:
['bright white', 'muted yellow']
Then I check each key's associated list for the inclusion of either value.
That would give me a list of all bags that are grandparents
of shiny gold
bags.
Using the example input again, that list will be:
['light red', 'dark orange']
Then I check each key's associated list for the inclusion of either value.
That would give me a list of all bags that are great-grandparents
of shiny gold
bags.
Using the example input again, that list will be:
[]
Since that list is empty, I stop because it is now clear that no bags can contain either of the great-grandparent
bags.
By now, I counted 4 bags that could eventually contain shiny gold
bags.
That's the correct answer!
Writing the working inside-out algorithm
Build the dictionary as described earlier
Create a unique set of values, containers, starting with one element: 'shiny gold'
Create another unique set of values, visited, starting empty
Do as long as containers is not empty
Create a unique set of values, next, starting empty
For each key-value pair in rules
If the array associated with the current key contains any of the elements in containers
Add the key to container, unless it already exists
Add the key to visited, unless it already exists
Replace the contents of containers with the unique elements in next
Return the number of unique elements in visited
Something I overlooked when first writing the algorithm above was that without the second unique list visited
, the algorithm was double-counting containers.
It felt great to see this algorithm run near-instantly.
Building a simulator to step through each containing set of bags
- This took almost no time at all
- It taught me that joining an array with one string element works differently than joining an array with two or more string elements: with one, it joins each character in the string; with two or more, it joins each string...as desired
- It's fun and insightful to see how the search list changes and the visited list grows
Part 2
- Updating my regular expression
- Updating my rules data structure
- Writing a working algorithm faster than I expected
- Repurposing the output for the simulator
Updating my regular expression
My Regex from Part 1 looked like this:
/(\w+\s\w+)\sbags?/g
For a line like this:
light red bags contain 1 bright white bag, 2 muted yellow bags.
It captured:
light red
bright white
muted yellow
I need to capture this now:
? light red
1 bright white
2 muted yellow
My Regex for Part 2 prepends an optional digit and space, capturing the digit:
// Part 1:
/(\w+\s\w+)\sbags?/g
// Part 2:
/(\d)?\s?(\w+\s\w+)\sbags?/g
For a line like this:
light red bags contain 1 bright white bag, 2 muted yellow bags.
It captures:
(nothing, light red)
(1, bright white)
(2, muted yellow)
Updating my rules data structure
In Part 1, my rules dictionary featured keys for each bag type and values were lists filled with each bag type contained in that bag.
light red bags contain 1 bright white bag, 2 muted yellow bags.
'light red': ['bright white', 'muted yellow']
In Part 2, my rules dictionary features keys for each bag type and values are dictionaries with keys for each contained bag type and values that are the required number of that bag type
light red bags contain 1 bright white bag, 2 muted yellow bags.
'light red': { 'bright white': 1, 'muted yellow': 2 }
Writing a working algorithm faster than I expected
My algorithm uses recursion
and a reducer
to generate the correct total number of required bags.
Sub-routine - Count Bags In (bag):
Expect one parameter, a string
If the object associated with the key in rules that matches bag is empty (meaning it contains 'no other bags')
Return 0
Else
Generate a list of entries derived from the object where each item in the list contains the bag type in location 1 and the bag quantity in location 2
For each item in the derived list
Accumulate a number - starting at 0
Increment the number by this amount:
The sum of the count associated with the current bag plus
And the product of the same count and the result of calling this sub-routine on the current bag's key (a.k.a. 2-word type)
Return the resulting number from calling the sub-routine with 'shiny gold'
Repurposing the output for the simulator
- I wasn't sure how to simulate my recursive algorithm
- Instead, I decided to generate the string of my accumulated equation and display that upon button click
The resulting equation for the example input looks like this:
(1 + 1 * (3 + 3 * 0) + (4 + 4 * 0)) + (2 + 2 * (5 + 5 * 0) + (6 + 6 * 0))
And for the second example, which is:
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.
Looks like this:
(2 + 2 * (2 + 2 * (2 + 2 * (2 + 2 * (2 + 2 * (2 + 2 * 0))))))
Celebrating my accomplishments throughout this puzzle
- To be honest, I read this puzzle's instructions about a year ago, shortly after discovering Advent of Code
- At that time, I felt intimated by this puzzle
- I didn't even try to solve Part 1
This time around, for Part 1:
- I carefully read through the instructions
- I wrote a
regular expression
instead of a complex chain ofsplit()
statements to extract the portions of the input string I needed to parse - I used the
Set
data type in JavaScript to leverage lists with only unique values, instead of writing complex code to check for duplicates in an array - I used a
for..in
with aternary
operation to make my code more elegant and concise - I considered one algorithmic approach that seemed like it would take forever to terminate
- I allowed myself time to consider other algorithmic approaches
- I discovered an alternative method that wound up being easy to write and quick to terminate in a correct answer
- And thus, I solved Part 1!
For Part 2:
- I studied the example and its equation closely to extract the winning formula
- I expanded on my
regular expression
- I used
recursion
- I used
Object.entries()
to convert key-value pairs into lists of two items - I used
reduce
to more elegantly and concisely generate the correct answer in one compact statement - I fully wrote the main sub-routine in my algorithm before running it once...only to discover it worked as expected!
- And thus, I solved Part 2!
What I achieved here feels incredible:
- I've learned a lot from completing these puzzles
- I'm proving that I can use intuition to create performant solutions
- I'm demonstrating a better understanding of advanced computer science skills, like regular expressions, recursion and functional programming
Top comments (1)
How much does a handy haversack cost?
Black magic revenge spell