Categories
Programming What I’m Up To

My solution to Advent of Code 2020’s Day 7 challenge, in Python

Welcome to another installment in my Advent of Code 2020 series, where I present my solutions to this year’s Advent of Code challenges!

In this installment, I share my Python solution to Day 7 of Advent of Code, titled Handy Haversacks.

The Day 7 challenge, part one

The challenge

Here’s the text from part one of the challenge:

You land at the regional airport in time for your next flight. In fact, it looks like you’ll even have time to grab some food: all flights are currently delayed due to issues in luggage processing.

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!

For example, consider the following rules:

These rules specify the required contents for 9 bag types. In this example, every faded blue bag is empty, every vibrant plum bag contains 11 bags (5 faded blue and 6 dotted black), and so on.

You have a shiny gold bag. If you wanted to carry it in at least one other bag, how many different bag colors would be valid for the outermost bag? (In other words: how many colors can, eventually, contain at least one shiny gold bag?)

In the above rules, the following options would be available to you:

  • bright white bag, which can hold your shiny gold bag directly.
  • muted yellow bag, which can hold your shiny gold bag directly, plus some other bags.
  • dark orange bag, which can hold bright white and muted yellow bags, either of which could then hold your shiny gold bag.
  • light red bag, which can hold bright white and muted yellow bags, either of which could then hold your shiny gold bag.

So, in this example, the number of bag colors that can eventually contain at least one shiny gold bag is 4.

How many bag colors can eventually contain at least one shiny gold bag? (The list of rules is quite long; make sure you get all of it.)

Spoiler alert!

Please be warned: If you want to try solving the challenge on your own and without any help, stop reading now! The remainder of this post will be all about my solution to both parts of the Day 7 challenge.

Importing the data

Every Advent of Code participant gets their own set of data. I copied my data and went through my usual process of bringing it into a Jupyter Notebook running a Python kernel.

This involves pasting it into a triple-quoted string and then using Python’s splitlines() method to break it up into a list of strings. The result is main_raw_input:

Creating the data structure

I feel that I can never stress this enough: A key part of coming up with solutions to Advent of Code challenges is to come up with good structures for the input data.

Here’s my function that takes the initial, somewhat-massaged input data, currently living in main_raw_input, and turns it into a data structure that I could do some problem-solving with:

The create_data_structure() function creates a table that makes it easy to look up a given bag and see what bags it contains.

It takes each line in the input, which follows this general form:

[adjective and color] bags contain [one or more of
([number][adjective and color]bag(s)).

It first makes use of this regular expression…

…to separate the line into two parts:

  • The containing bag, which is captured by the (\w+ \w+) group, and
  • The contained bag(s), which are captured by the (.*) group.

The contained bag(s) are further parsed using this regular expression…

…to create a list of tuples of the form:

Here’s how I used create_data_structure() to create the data structure:

Here’s a sample of the what the structure looked like for my data:

With the data structure built, it was now possible to write a function to determine how many shiny gold bags a given bag would contain:

It’s the return of our friend:

This function checks the contents of the given bag. If there are bags in the given bag, it checks the contents of those bags and counts the shiny gold ones. If there are bags in those bags, it checks the contents of those bags and counts the shiny gold ones. And so on…

Now that I had the shiny_gold_bag_count() function, I could write another function — bags_containing_at_least_one_shiny_gold_bag() — that would apply the shiny_gold_bag_count() function to all the bags in the collection, giving me the answer to the part one:

In my case, the count was 326.

The Day 7 challenge, part two

Creative Commons photo by “Sunnya343”. Tap to view the source.

The challenge

Here’s the text of part two:

It’s getting pretty expensive to fly these days – not because of ticket prices, but because of the ridiculous number of bags you need to buy!

Consider again your shiny gold bag and the rules from the above example:

  • faded blue bags contain 0 other bags.
  • dotted black bags contain 0 other bags.
  • vibrant plum bags contain 11 other bags: 5 faded blue bags and 6 dotted black bags.
  • dark olive bags contain 7 other bags: 3 faded blue bags and 4 dotted black bags.

So, a single shiny gold bag must contain 1 dark olive bag (and the 7 bags within it) plus 2 vibrant plum bags (and the 11 bags within each of those): 1 + 1*7 + 2 + 2*11 = 32 bags!

Of course, the actual rules have a small chance of going several levels deeper than this example; be sure to count all of the bags, even if the nesting becomes topologically impractical!

Here’s another example:

In this example, a single shiny gold bag must contain 126 other bags.

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

My solution was the following function:

Once again, my solution was a recursive one. This function checks the contents of the given bag. If there are bags in the given bag, it counts them and then checks their contents. If there are bags in those bags, it counts them and checks their contents. And so on…

Getting the solution was a matter of calling the function:

And for my data, the answer was 5635.

Solutions for previous days in Advent of Code 2020

Leave a Reply

Your email address will not be published. Required fields are marked *