Categories

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.)

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

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

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.