Advent of Code: Day #07 - Handy Haversacks

7th of December 2020 |

4 - 5 minutes

Introduction

Todays challenge was all about working with trees and recursion.

For task one we we're given a list of bags and the amount and colour of bags that can fit in side them. I.e a Red bag could hold 2 green and a purple. We're tasked with finding out how many top level bags can eventually fit a shiny gold bag.

Reading in the data

I read the data into a python dictionary where the key is the bags colour and the value is an array of arrays in the form [[number, colour]]. I used a regex to replace the words bag and bags.

Python Copy

def read_data(path):
    bag_map = {}
    with open(path, "r") as file:
        for line in file.readlines():
            outer, inners = line.split(" bags contain")
            inner_array = inners.strip(" .\n").split(",")
            inner_array = [sub("(bags|bag)+", "", s).strip().split(" ", 1) for s in inner_array]
            bag_map[outer] = inner_array
    return bag_map

The Solution

I decided to take a recursive approach to this issue. I made a function that goes through a bag and all of its sub-bags and returns true if any can hold a shiny gold bag. I then took the sum of all the booleans for each bag.

Python Copy

def can_hold_gold(bags, inner_bags):
    names = [i[1] for i in inner_bags]
    # End condition
    if "shiny gold" in names:
        return True
    # Make sure we're not at the bottom
    elif not (len(names) == 1 and names[0] == "other"):
        total = False
        while not total:
            for _, name in inner_bags:
                # Add to the total a bool value and break
                # if we get a bag that can hold gold
                total += can_hold_gold(bags, bags[name])
            break
        return total
    return False


def task_one(bags):
    return sum([bool(can_hold_gold(bags, bags[i])) for i in bags])

Task Two

The Solution

For task two we are asked to calculate how many bags fit inside our shiny golden bag. I wrote another recursive function that counts how many sub-bags a bag has and ran it with shiny-gold as the input.

Python Copy


def count_sub_bags(bags, prev, inner_bags):
    names = [i[1] for i in inner_bags]
    # If we're still going
    if len(names) != 1 or names[0] != "other":
        total = 0
        for c, n in inner_bags:
            # How many of this bag there are
            count = [int(b[0]) for b in bags[prev] if n == b[1]][0]
            # If this bag holds a end bag or not
            more_bags = not (len(bags[n]) == 1 and bags[n][0][1] == "other")
            # Add to the total number of bags (Multiplying count by more_bags because
            # we only do this if we're not at the bottom)
            total += int(count) * more_bags + int(c) * count_sub_bags(bags, n, bags[n])
        return total
    else:
        return 1


def task_two(bags):
    return count_sub_bags(bags, "shiny gold", bags["shiny gold"])