Day 7 threw me for a loop. Basically what you have is a remake of the Matryoshka Dolls where you have a doll inside of a doll, only in this case it was bags within bags. We’re provided with a list of rules telling us which bags are within which bag. Ultimately we want to find how many bags can contain a “Shiny Gold Bag” within it.
The first part of the challenge was just parsing the rules. The rules came in a line separated file that looked like
shiny purple bags contain 2 pale blue bags, 1 wavy fuchsia bag, 5 pale salmon bags.
Fortunately the lines follow a set format that consists of
<verb> <color> bags? contain (# <verb> <color> bags?(.|,)){1:}
Basically what I did was space separated the line and pulled in the first two elements (shiny purple) and used that as the key to a dict that held all of the rules. The value for that dict was another dict that held the internal bag’s description as the key and the number of bags as the value. For example:
{"shiny purple": {"pale blue": 2, "wavy fuchsia": 1, "pale salmon": 5}}
So now that we have all of the rules parsed, its a matter of figuring out what is inside what. I built a function (get_inside_bags) that receives a bag color and keeps going through each bag inside it until it either finds a shiny gold bag or runs out. In order for this to work, it had to be a recursive function where it keeps calling itself as it goes through each internal bag. I HATE recursive functions because I have a really hard time wrapping my head around what the hell they are actually doing. Fortunately, this function was fairly straightforward and came together without too much stress.
def get_inside_bags(rules, current_bag):
gold_bag_found = False
inside_bags = rules[current_bag].keys()
if 'shiny_gold' in inside_bags:
gold_bag_found = True
else:
for bag in inside_bags:
if get_inside_bags(rules, bag):
gold_bag_found = True
break
return gold_bag_found
So what does the get_inside_bags function do? You see it’s passed two values, rules and current_bag. Rules is the dict that contains all of the rules that were parsed at the start of the script. I realize that you don’t need to pass it into the function because it’s globally available, but it’s just something I’ve always done and I guess will continue to do. Current_bag is the name (i.e. pale blue) of the current bag we’re examining.
Once in the function, we assign the variable inside_bags the list of keys attached to the current_bag (all of the bags that are inside that bag). If we happen to get lucky and find a “shiny gold” bag, then we found what we’re looking for and return true. If not though, we go through each bag that is now present in inside_bags and cycle through them. Each time we cycle through, we recursively call get_inside_bags again, this time feeding it a new bag to look at. This continues until we finally reach a bag that doesn’t contain any bags within it, or we find a “shiny gold” bag.
Part 2 was basically the same but we started with a Shiny Gold bag as the outside bag, and then had to figure out what was in it. I basically used the same function and just modified it to keep track of how many bags it was dealing with as it moved through.
def get_inside_bags(rules, current_bag):
additional_bags = 0
inside_bags = rules[current_bag].keys()
for bag in inside_bags:
additional_bags += int(rules[current_bag][bag])
additional_bags += int(rules[current_bag][bag]) * get_inside_bags(rules, bag)
return additional_bags
for bag in rules['shiny_gold'].keys():
total_bags += int(rules['shiny_gold'][bag])
total_bags += int(rules['shiny_gold'][bag]) * get_inside_bags(rules, bag)
Starting at line 9 (in the main program) we go straight into the rules just as it pertains to “shiny gold” bag, and find out what is inside that bag. Since we’re tracking how many bags total are inside the “shiny gold” bag, we start by recording the number of each bags directly inside. Then we pass that bag into our updated get_inside_bags function.
Now the function is essentially do the same thing that the original for statement did, looking at the bags within that bag, and passing it back to itself until we get the number of bags.
My final solution can be found here.