Advent of Code 2020 (Day - 7 Handy Haversacks)

To solve this challenge visit https://adventofcode.com/2020/day/7

You can find my solutions for other problems at :
https://github.com/Rage-ops/Advent-of-code-2020

---

Puzzle Part - 1

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:

light red bags contain 1 bright white bag, 2 muted yellow bags.
dark orange bags contain 3 bright white bags, 4 muted yellow bags.
bright white bags contain 1 shiny gold bag.
muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.
shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.
dark olive bags contain 3 faded blue bags, 4 dotted black bags.
vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.
faded blue bags contain no other bags.
dotted black bags contain no other bags.

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:

A bright white bag, which can hold your shiny gold bag directly.
A muted yellow bag, which can hold your shiny gold bag directly, plus some other bags.
A dark orange bag, which can hold bright white and muted yellow bags, either of which could then hold your shiny gold bag.
A 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.)

Parsing Input File

My intuition was to first construct a directed graph satisfying all dependencies of the bags (i.e., outer bag have an edge going towards all the inner bags).

import re


adj = {}
visited = {}
with open("Problem-7/Day 7: Handy Haversacks.txt") as file:
    for line in file:
        # Every line in the input was in the format outerbags contain x innerbags, y innerbags, so on..
        # So we can split every line into two parts using the word "contain " as separator. 
        # As split funtion returns a list, we now have outerbag name as first element and it's dependencies as second element. Unpacked them into two variables as shown below.
        outer_bag, innerbags = line.split("contain ")
        # Now the outer_bag variable has outerbagname with suffix bags in it. We can just slice the string to remove the suffix
        # Similarly, innerbags will now has a string in the format x innerbags, y innerbags, so on..
        # We can extract the count and the innerbag name using regex and grouping as shown below
        innerbags = re.findall(r"(\d{1,}) ([a-z ]+) bag|bags", innerbags)
        # visited list is useful when we are exploring the graph to avoid cycles. Initially we should mark every bag as not visited
        visited[outer_bag[:-6]] = False
        if outer_bag[:-6] not in adj:
            adj[outer_bag[:-6]] = {}
        # Adding edges from outer bag to each inner bag
        for count, bag in innerbags:
            if count and bag:
                if bag not in adj:
                    adj[bag] = {}
                adj[outer_bag[:-6]][bag] = int(count)
# Now we have our adjacency list ready for our directed graph

Solution for Part 1

The question was to find how many different bag colors would be valid for the outermost bag if we wanted to carry a shiny gold bag?.

• We can now find the solution by counting number of vertices(bags) from which we can reach shiny gold bag vertex. - We can solve it by exploring the graph completely or just by exploring only vertices that has an edge going towards the shiny gold bag vertex. (i.e., Simply find the strongly connected components which has shiny gold bag vertex in it)

def part_one(adj, visited, bag_name):
# dfs of a graph
    def dfs(adj, visited, start, count):
        for edge in adj[start].keys():
            if not visited[edge]:
                visited[edge] = True
                count = dfs(adj, visited, edge, count + 1)
        return count


    # reverse the graph 
    adj_reverse = {}
    for outer, inner in adj.items():
        if outer not in adj_reverse:
            adj_reverse[outer] = {}
        for key, count in inner.items():
            if key in adj_reverse:
                adj_reverse[key][outer] = count
            else:
                adj_reverse[key] = {outer: count}
    # Now as the graph is reversed, we can find the vertices that previously had a directed edge towards the shiny gold bag now in new adjacency list at shiny gold vertex.
    # Simply exploring and counting the number of vertices explored from shiny gold bag vertex will be the result
    return dfs(adj_reverse, visited, bag_name, 0)

---

Puzzle Part - 2

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:

shiny gold bags contain 2 dark red bags.
dark red bags contain 2 dark orange bags.
dark orange bags contain 2 dark yellow bags.
dark yellow bags contain 2 dark green bags.
dark green bags contain 2 dark blue bags.
dark blue bags contain 2 dark violet bags.
dark violet bags contain no other bags.

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?

Solution for Part 2

Searching the graph using dfs and keeping the count of bags at each level recursively will give the result.

def part_two(adj, start, count):
    if not adj[start]:
        return 0
    temp = 0
    for edge, c in adj[start].items():
        temp += c + c * part_two(adj, edge, count)
    count += temp
    return count

---

Complete Solution with Part 1 and Part 2 in Python

# Advent of Code 2020 Day 7
import re


adj = {}
visited = {}
with open("Problem-7/Day 7: Handy Haversacks.txt") as file:
    for line in file:
        # Every line in the input was in the format outerbags contain x innerbags, y innerbags, so on..
        # So we can split every line into two parts using the word "contain " as separator.
        # As split funtion returns a list, we now have outerbag name as first element and it's dependencies as second element. Unpacked them into two variables as shown below.
        outer_bag, innerbags = line.split("contain ")
        # Now the outer_bag variable has outerbagname with suffix bags in it. We can just slice the string to remove the suffix
        # Similarly, innerbags will now has a string in the format x innerbags, y innerbags, so on..
        # We can extract the count and the innerbag name using regex and grouping as shown below
        innerbags = re.findall(r"(\d{1,}) ([a-z ]+) bag|bags", innerbags)
        # visited list is useful when we are exploring the graph to avoid cycles. Initially we should mark every bag as not visited
        visited[outer_bag[:-6]] = False
        if outer_bag[:-6] not in adj:
            adj[outer_bag[:-6]] = {}
        # Adding edges from outer bag to each inner bag
        for count, bag in innerbags:
            if count and bag:
                if bag not in adj:
                    adj[bag] = {}
                adj[outer_bag[:-6]][bag] = int(count)
# Now we have our adjacency list ready for our directed graph


def part_one(adj, visited, bag_name):
    # dfs of a graph
    def dfs(adj, visited, start, count):
        for edge in adj[start].keys():
            if not visited[edge]:
                visited[edge] = True
                count = dfs(adj, visited, edge, count + 1)
        return count

    # reverse the graph
    adj_reverse = {}
    for outer, inner in adj.items():
        if outer not in adj_reverse:
            adj_reverse[outer] = {}
        for key, count in inner.items():
            if key in adj_reverse:
                adj_reverse[key][outer] = count
            else:
                adj_reverse[key] = {outer: count}
    # Now as the graph is reversed, we can find the vertices that previously had a directed edge towards the shiny gold bag now in new adjacency list at shiny gold vertex.
    # Simply exploring and counting the number of vertices explored from shiny gold bag vertex will be the result
    return dfs(adj_reverse, visited, bag_name, 0)


def part_two(adj, start, count):
    if not adj[start]:
        return 0
    temp = 0
    for edge, c in adj[start].items():
        temp += c + c * part_two(adj, edge, count)
    count += temp
    return count


print("Part 1: Total number of bag colors that contain at least one shiny gold bag :",
      part_one(adj, visited, "shiny gold"))
print("Part 2: Shiny gold bag contains total {} number of bags".format(
    part_two(adj, "shiny gold", 0)))