Advent of Code: 2020 Day 07
Tags: adventofcode, python, networkx
Published: 2020-12-07 21:12:33

⚠️ **SPOILER ALERT** ⚠️
This is a post with my solutions and learning from the puzzle. Don't continue reading if you haven't tried the puzzle on your own yet.

If you want to do the puzzle, visit [adventofcode.com/2020/day/7](https://adventofcode.com/2020/day/7).

My programming language of choice is `python` and all examples below are in python.

## TOC

- [Key learning](#key-learning)
- [Puzzle](#puzzle)
- [Part 1](#part-1)
  - [Solution breadth first](#breadth-first)
  - [Solution depth first](#depth-first)
- [Part 2](#part-2)
  - [Solution part 2](#solution-2)
- [Alternative: Regex](#regex)
- [Alternative: Networkx](#networkx)
- [Python tips](#python-tools)


## Key learning <a name="key-learning"></a>

* Depth first search
* Possibly on part 1: Breadth first search

This puzzle can be viewed as a "graph" problem with nodes and edges. A simple way for beginners to start is utilizing a queue or recursive function.

## Puzzle <a name="puzzle"></a>

The puzzle describes relationship between bags in different colors. A bag in one color can contain a certain amount of bags in other colors.

Example input:
```
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.
```


## Part 1 <a name="part-1"></a>

The puzzle is to find all bags that can directly or indirectly contain a `shiny gold bag`.  This can be viewed as a graph where bags are nodes and their relationships are edges.

An visualisation with example data:
```
           -> green bag -> grey bag
          /                       \
blue bag -                         -> shiny gold bag
          \                       /
            -> purple bag       /
                               /
white bag -------------------
```

Our goal is to traverse from `shiny gold` to the left and counting all nodes it finds. In this visualisation the answer is: `white bag, blue, green, grey`

### Parsing input

A big part of the problem is deciding on data structure and how to parse the input into that structure.

For part 1 I aimed for this data-structure:
```
bags = {
  "light red": "1 bright white bag, 2 muted yellow bags.",
  "dark orange": "3 bright white bags, 4 muted yellow bags.",
  "bright white": "1 shiny gold bag.",
  "muted yellow":  "2 shiny gold bags, 9 faded blue bags.",
  ...
}
```

To keep track of which bags that contain a `shiny gold` bag I used a `set` to avoid duplicates. Below is the code to parse in the data. This approach does the simple parsing for bare minimum for part 1:

```python
# Extract a list of lines from file
lines = [x.strip() for x in open('07.input', 'r').readlines()]

bags = {}
for l in lines:
    bag, contains = l.split('contain')
    bag = bag.replace(' bags','')
    bags[bag] = contains
```

### Solution: Breadth first <a name="breadth-first"></a>

Some bags will directly contain `shiny gold`. Those bags can in turn be contained in other bags, which will indirectly contain `shiny gold`.

This solution uses a work queue to traverse the "graph". Once we find a bag that can contain `shiny gold` we add it to the queue to check if it can be contained by another bag. We keep on doing so until the work queue is empty. For every bag we find we store it in the `answer`-set

This is a so called [breadth first search](https://en.wikipedia.org/wiki/Breadth-first_search). In this case I use a `queue`.


```python
answer = set()                      # Bags containing 'shiny gold'
q = ['shiny gold']                  # Work queue for traversing bags
while len(q) != 0:
    current = q.pop(0)
    for bag in bags:
        if bag in answer:             # Skip if already counted.
            continue
        if current in bags[bag]:      # If bag contains current-bag,
            q.append(bag)             # add to queue and answer
            answer.add(bag)
print "Answer part 1: %d" % len(answer)
```

### Solution: Depth first <a name="depth-first"></a>

Another solution is the [depth first search](https://en.wikipedia.org/wiki/Depth-first_search). Both algorithms do fine in this puzzle and input-size. But in coming advent-of-code-puzzles, it is possible that only one will be sufficient enough. Therefore we practice both now.

This example is a `depth first` where I use a `recursive function`:

```python
bags = {}
for l in lines:
    bag, contains = l.split('contain')
    bag = bag.replace(' bags','')
    bags[bag] = contains

def deep_search(bag, bags):
    contains = []
    for b in bags:
        if bag in bags[b]:
            # Add b to our list
            contains.append(b)
            # Add all children to b in our list
            contains.extend(deep_search(b, bags))

    # Remove duplicates
    return set(contains)

print "Answer: ", len(deep_search('shiny gold', bags))
```

## Part 2 <a name="part-2"></a>

### Parsing input

For part 2 I aimed for this data-structure:
```
bags = {
  "light red": { "bright white": 1, "muted yellow": 2 },
  "dark orange": { "bright white": 3, "muted yellow": 4 },
  "bright white": { "shiny gold": 1 },
  "muted yellow": { "shiny gold": 2, "faded blue": 9 },
  ...
}
```

In this way I can call `bags['muted yellow']['shiny gold']` to find out how many `shiny gold`  bags `muted yellow` contain.

This is a ugly "simple" way of solving it. Further down is an regex example which is cleaner.

```python
bags = {}
q = []
for l in lines:
    # Clean line from unnecessary words.
    l = l.replace('bags', '').replace('bag', '').replace('.','')

    bag, contains = l.split('contain')
    bag = bag.strip()

    if 'no other' in contains: # If bag doesn't contain any bag
        bags[bag] = {}
        continue

    contains = contains.split(',')
    contain_dict = {}
    for c in [c.strip() for c in contains]:
        amount = c[:2]
        color = c[2:]
        contain_dict[color] = int(amount)
    bags[bag] = contain_dict
```

### Solution  <a name="solution-2"></a>

A good data structure enables us to do a clean solution. Here is an example with 
a recursive function to count all bags:
```python
def recursive_count(bag, bags):
    count = 1  # Count the bag itself

    contained_bags = bags[bag]
    for c in contained_bags:
        multiplier = contained_bags[c]
        count += multiplier * recursive_count(c, bags)
    return count

# Minus one to not count the shiny gold bag itself
result = recursive_count('shiny gold', bags) - 1
print "Result part 2: %d " % result
```

## Alternative: With regex  <a name="regex"></a>

A lot easier way to parse the data is using regex. Here is an example:

```python
import re
from collections import defaultdict

bags = defaultdict(dict)
for l in lines:
    bag = re.match(r'(.*) bags contain', l).groups()[0]
    for count, b in re.findall(r'(\d+) (\w+ \w+) bag', l):
        bags[bag][b] = int(count)

def part1():
    answer = set()
    def search(color):
        for b in bags:
            if color in bags[b]:
                answer.add(b)
                search(b)
    search('shiny gold')
    return len(answer)

def part2():
    def search(bag):
        count = 1
        for s in bags[bag]:
            multiplier = bags[bag][s]
            count += multiplier * search(s)
        return count
    return search('shiny gold' ) - 1  # Rm one for shiny gold itself
```

## Alternative: Network X  <a name="networkx"></a>

[NetworkX](https://networkx.org/) is a good library for handling graphs. Haven't used it myself so much, but it appears quite often in the solutions megathread once there is a graph-problem. 

There is a lot of documentation, but by reading solutions on the megathread you'll learn what common features to use.

Make sure you understand the above example with regex first before reading this. Here is an example solution with networkx:

```python
import re
from collections import defaultdict
import networkx as nx

# Parse data
bags = defaultdict(dict)
for l in lines:
    bag = re.match(r'(.*) bags contain', l).groups()[0]
    for count, b in re.findall(r'(\d+) (\w+ \w+) bag', l):
        bags[bag][b] = { 'weight': int(count)}

# Create a graph in networkx
G = nx.DiGraph(bags)

def part1():
    # Reverse edges
    RG = G.reverse()
    # Get predecessors
    predecessors = nx.dfs_predecessors(RG, 'shiny gold')
    # Count predecessors
    return len(predecessors)
print(part1())

def part2():
    def search(node):
        count = 1
        # Iterate neighbors for node
        for n in G.neighbors(node):
            # Multiply weight with recursive search
            count += G[node][n]['weight'] * search(n)
        return count
    return search('shiny gold') - 1
print(part2())
```

Some benefit in using networkx is that it gives us more powerful tools than just traversing the graph. If we would like to find the shortest path, then this one-liner would help:

```python
print(nx.shortest_path(G, source='bright red', target='shiny gold'))
```

Links:
- [networkx.org/documentation/networkx-2.3/reference/classes/digraph.html#](https://networkx.org/documentation/networkx-2.3/reference/classes/digraph.html#)
- [networkx.org/documentation/networkx-2.3/reference/algorithms/generated/networkx.algorithms.shortest_paths.generic.shortest_path.html](https://networkx.org/documentation/networkx-2.3/reference/algorithms/generated/networkx.algorithms.shortest_paths.generic.shortest_path.html#networkx.algorithms.shortest_paths.generic.shortest_path

## More python tools   <a name="python-tools"></a>

These are tools worth having in back of your head while doing advent of code.

[defaultdict](https://docs.python.org/3/library/collections.html#collections.defaultdict): Useful when you don't want to think about initiating all values first.

[deque](https://docs.python.org/3/library/collections.html#collections.deque): Useful when you want to pop left and right from a queue.

[heapq](https://realpython.com/python-heapq-module/): Amazing for tool or solving problems that involve extremes such as largest, smallest, optimal, etc.

## Thanks for reading!

I hope these solutions were helpful for you.

Complete code can be found at: [github.com/cNille/AdventOfCode/blob/master/2020/07.py](https://github.com/cNille/AdventOfCode/blob/master/2020/07.py)