Handy Haversack

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

1. Considering an effective data structure for the rules
2. Considering the speed of a possible algorithm
3. Extracting the important information from each line
4. Building a dictionary from each list of captured matches
5. Considering an inside-out algorithm
6. Writing the working inside-out algorithm
7. 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

Try the simulator for Part 1

Part 2

1. Updating my regular expression
2. Updating my rules data structure
3. Writing a working algorithm faster than I expected
4. 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 of split() 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 a ternary 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

Comments

[BellaReyes]

How much does a handy haversack cost?
Black magic revenge spell