Advent of Code, Day 7

Day 7 of Advent of Code is here! Check out Day 1 for what this is all about. See all of my solutions here.

Did you join my leaderboard? I invite you to join my board, and we can see who can win it ;) It’s not too late, go to “Leaderboard” in the top nav of AoC and enter 1030369-e174b794 to join my board.

Get your leaderboard in Slack! See my other post, written by a friend of mine, on how to get your leaderboard into your Slack channel with a fun lambda function and slash command!

I have also loaded up just the challenge and code from this and my other days on github, you can follow along there too: pretty Git pages or the code in the repo.

Don’t cheat!

I highly encourage you to get through the day’s challenge on your own. I would love to hear how you did! Did you find a better approach than I did? Do tell!

Day 7: Handy Haversacks

Part I

“Due to recent aviation regulations, many rules (your puzzle input) are being enforced about bags and their contents; bags must be color-coded and must contain specific quantities of other color-coded bags. Apparently, nobody responsible for these regulations considered how long they would take to enforce!” ref

The rules for baggage look like this

How many bags can contain a shiny gold bag? Absolute nonsense, but it’s going to be fun!

As always, we need to get all of the data:

var rules = document.getElementsByTagName('pre')[0].innerText.split('\n')

We got our rules, so lets find how many rules have a shiny gold bag

var countSet = new Set()
rules
 .filter(r => r.match(/contain[\sa-z0-9,]*shiny gold/i))
 .forEach(r => {
   var containingBag = r.match(/([a-z\s]*)\sbag[s]?\scontain/i)[1].trim()
   countSet.add(containingBag)
})

We’re going to filter the rules, and I’m using a gold ole regular expression again. This regex is looking for any rule that:

• has the word contain and AFTER that word, has a space \s, and any letter or number, a-z0-9 or comma, or none of these. * indicates zero or more of the previous.
• and the words shiny gold

Once we have all rules with shiny gold, let’s now find the containing bag, the parent bag, the bag my shiny gold bag is in. We use another .match() to get the bag name:

• find any letters a-z and spaces \s with the word bag, or optionally with a s after it, like bags
• find all of this BEFORE the word contain
• a .match() returns an array of values. The first value, index 0, is the entire string it matched. Then the next values are the groups from the match. Note the ( ) in the regex, that groups those values so I can pull them out. At the end, outside of the .match() you’ll see a [1], that’s grabbing the first group, which is the bag name.

Then we add it to countSet which is a Set(), which will ensure uniqueness of the data. We talked about Set in Part I of Day 6.

This is great, but this only gets us parent bags that contain shiny gold, what about the parent bags of the parent bags? That’s right, let’s loop!

var getBag = (childBag) => {
    var bagReg = new RegExp(`contain[\\sa-z0-9,]*${childBag}`,'i')
    rules
        .filter(r => r.match(bagReg))
        .forEach(r => {
            var containingBag = r.match(/([a-z\s]*)\sbag[s]?\scontain/i)[1].trim()
            countSet.add(containingBag)
            getBag(containingBag)
        })
}
 
getBag('shiny gold')
console.log(countSet.size)

We took our previous code and wrapped it in a function called getBag:

• the function takes whatever bag name is sent to it, and creates the same regex
• filters the rules for that regex
• does the same .match() to get the containing bag, adds that to the set, then calls itself to find that bag’s containers
• Once that’s all done, it’ll exit getBag and log the number to the console!

Part II

“How many individual bags are required inside your single shiny gold bag?” ref

The new rule is basically opposite of Part I, how many bags should be in your shiny gold bag? The shiny gold bad is a containing bag, and has bags in it, so how many bags are those, and in those, and in those….

THIS was hard, and mainly because I am developing in the dev console in Chrome. This lacks a lot of features a normal IDE brings, like intellitype, debugging, variable checking, etc. I think future challenges I’ll start to move to writing in VSCode instead of the dev toolbar.

The trick here is thinking recursively. In Part I, we recursed through the data. By calling the same function we were in, we can basically send a subset of data to itself and recurse through parents. Here, we want to recurse the other direction, start at the top level bag, and work our way down, while doing some math.

How does it look:

var countSet = new Set()
 
var tree = []
var getBag = (parentBag, count) => {
    var bagReg = new RegExp(`${parentBag}\\sbag[s]?\\scontain`,'i')
    return rules
        .filter(r => r.match(bagReg))
        .map(r => {
            var childrenBags = r.split('contain')[1].split(',')
            return childrenBags.map(c => {
                var child = c.match(/([0-9]+)\s([a-z\s]*)\sbag/i)
                if(child){
                    tree.push({ count: Number(child[1]), total: (Number(child[1]) * count), bag: child[2], parentBag })
                    getBag(child[2], (Number(child[1]) * count))
                }
            }).flat()
        })
        .flat()
}
 
getBag('shiny gold', 1)
var bagCnt = 0
tree.forEach(t => bagCnt += t.total)
console.log(bagCnt)

You’ll see some similar code from Part I, similar, but not the same.

• For starters, our filter regex is swapped with the subsequent match. Now we’re filtering for the parent bag provided that lives before contain.
  • In doing Day 8, I realized that the ^ can indicate the start of the line, so this expression could be lighter like ^${parentBag}. That will only match where the first characters on the line are the value in parentBag
• For each item that matches, I just split on the word contain and then the second value, the right side of contain, I split on comma. This will get us all the bags this parent bag contains
• For each child bag, I am putting the bag info into my tree array.
  • I am creating little objects here, instead of just storing the data I ultimately need, which is the total. I like to do this for “just in case” use cases, sometimes I realize I need a little more data to finish it off. Also, it helps in debugging to get more info about the data it’s acting weird about.
• Note the total is set to the number from the rule, times the count from the parent. This ensures we get a multiplied total as we go.
  • I made the comment earlier to think recursively, this little tidbit was another spot I mucked up on. Big thanks to Josh, one of my colleagues, for sharing his code and letting me see this ;)
• Then we call getBag, sending the child as the new parent, and this child’s count.
• Finally, outside of getBag, we iterate through the tree array and add up all the totals.

How did it go for you?

Whoo, what a doosey, but a fun challenge for sure! I hope you tried it yourself! How did you find the answer on your own? How did you do it? Anything stump you? I’d love to hear how you did! Please comment below!