Advent of Code 2020, Day 7 -- Handy Haversacks

Dec 7th, 2020

5 min read

Advent Of Code

Python solutions to Advent of Code 2020, day 7.

My Advent of Code solutions, done in Python. Refactors and solutions in other languages will be added if/when they're done.

Full code for Day 7 can be found on Github.

You can participate in Advent of Code at adventofcode.com/2020

The Day 7 problem can be found at adventofcode.com/2020/day/7

A very wrong solution

And now the difficulty of Advent of Code has jumped! I actually started writing my solution for part 1 completely wrong, thinking that I just needed to count the number of times that "shiny gold" showed up in my list.

import re

puzzle_input = open("input.txt", "r")
test = puzzle_input.read()

# Super fail!
# I thought I could just find bags that contain shiny gold bags,
# but no, I need to recursively find the bags that contain
# THOSE bags as well!
def fail_shiny_golds(rules):
    pattern = re.compile(r'^[\w\s]+contain\s', flags=re.M)
    remove_containers = re.sub(pattern, '', rules)
    gold_pattern = re.compile(r'shiny gold', flags=re.M)
    shiny_gold = re.findall(gold_pattern, remove_containers)
    return len(shiny_gold)

I don't know why I thought Day 7 would be as easy as that, but I thought I was being very clever.

Solution, part 1

What I needed to do, as explictly stated in the problem, is solve this:

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?

I can still use my same puzzle input, since it doesn't do anything beyond read the file.

I'm going to split the text by line into a list, and then split each line into a tuple. The first part of the tuple will be what comes before the string " contain " (the container bag) and the second will be everything that is contained by the container bag.

Next, I'm adding a recursive function that starts by finding all containers that contain "shiny gold" bags. I'm doing this with regex, because I don't care about the other bags right now, I just want to find that string in the second part of the tuple.

If a container bag contains a "shiny gold", the color of that bag is added to the set of possible bag colors. I'm using a set so that any duplicates are automatically removed. Then, the function is called recursively on that bag color, and finds all bags that can contain that bag.

Once the function has found all possible parent, grandparent, etc. bags, the function returns the length of the all_possibles set, and that's the answer!

You'll see my note about removing the word "bags" from my search results. This is why I'm using a slice of [:-5] on container names. At some points, a container bag can contain "1 bag", which won't match unless we search by just the description and color string.

# Found out about formatted string literals in Python.
# https://docs.python.org/3/tutorial/inputoutput.html#fancier-output-formatting
# Basically turning the list into tuples of "container" and "contains",
# then recursively iterating over it to get the nesting-dolls of bags.
def find_shiny_golds(rules):
    container_list = [tuple(x.split(" contain ")) for x in rules.strip().split("\n")]
    all_possibles = set()

    # Have to remove the words "bag" and "bags" from the search results.
    # In the case of "1 bag" vs "bags", some bags aren't getting caught.
    def find_containers(bag_type):
        for cont in container_list:
            pattern = re.compile(rf"{bag_type}")
            contains = re.search(pattern, cont[1])
            if contains:
                all_possibles.add(cont[0][:-5])
                find_containers(cont[0][:-5])
    find_containers("shiny gold")
    return len(all_possibles)


print(find_shiny_golds(test))

Solution, part 2

This took me a really long time, mostly because I'm not great with trees. Luckily, I found a resource that helped me figure out how to make a basic tree in Python.

First, I decided to create a list of tuples like the first function, but then transform that into a dictionary in the form of {container: child bags}. I figured this might make lookup a little easier for each bag type.

def shiny_golds_contain(rules):
    container_list = [tuple(x.split(" contain ")) for x in rules.strip().split("\n")]
    container_dict = {k: v for k, v in container_list}

Next, I've created my Node class. It takes the bag type and adds children into a list linked to it, and continues until a bag type has "no other bags." I've started off the tree with bag_tree, a single node of "1 shiny gold bag".

    # Look at me making a tree!
    class Node(object):
        def __init__(self, data):
            self.data = data
            self.children = []

        def add_child(self, obj):
            self.children.append(obj)

    bag_tree = Node("1 shiny gold bag")  # Gold bag holds all

After that is the function that recursively searches for child bag types and adds them to the bag_tree as children. Then, those child bags are searched for their child bags, and so on. There's some string manipulation in here as well, where we replace ".", "bags", and "bag" in the string we're using to search, much like in the part 1 function. There's also a slice to remove the number of bags from the search term.

    # Make a tree of all the contents of the shiny gold bag.
    # If a child returns with "no other bags.", that's the end of that branch.
    def find_contains(bag_type, node_parent):
        bag_contains = container_dict[bag_type].split(", ")
        for c in bag_contains:
            if c == "no other bags.":
                break
            node = Node(c)
            node_parent.add_child(node)
            c = c.replace(".", "").replace("bags", "").replace("bag", "")
            find_contains(c[2:] + "bags", node)
    find_contains("shiny gold bags", bag_tree)

I wanted to print out the tree, since I like to visualize things. This also helped me with some debugging. For example, I had a weird [:-1] slice in my find_contains function above that was removing the last element in each bag_contains list. That meant that my final bag tree was way shorter than it should've been. By comparing my printed tree and puzzle input, I was able to see what was going wrong.

    # I felt like printing out the entire data tree with indents,
    # just so I could see what it looks like.
    def print_data_tree(node, indent):
        print(indent + node.data.replace(".", ""))
        indent += "    "
        for c in node.children:
            print_data_tree(c, indent)
    print_data_tree(bag_tree, '    ')

Finally, I'm recursively going through each node and multiplying each number of child bags by the number of parent bags that it exists in. This gives us a total number of each type of bag that will exist within the shiny gold bag.

When it comes to returning the final sum, I'm removing the first bag from the list, since we don't want to count the shiny gold bag!

    total_bags = []

    # Multiply the number of bags with the number of parent bags
    # to get the total number of a bag within the gold bag.
    def add_bags(node, parent_bags):
        child_bags = int(node.data[0]) * parent_bags
        total_bags.append(child_bags)
        for c in node.children:
            add_bags(c, child_bags)
    add_bags(bag_tree, 1)

    # Sum all the bags except for the first node,
    # because that's the main shiny gold bag.
    return sum(total_bags[1:])
    
print(shiny_golds_contain(test))

Overall, this was quite a difficult challenge. I was able to understand pretty quickly what I needed to do to get the answer, but I didn't necessarily know how to go about doing it. Luckily, I've been studying binary trees and other data structures recently, and knew that a tree was the way I wanted to solve this. I thought about using a nested dictionary, but I'm glad I tried something new this time.

mary.codes