Advent of Code 2018 Day 3: No Matter How You Slice It
Tags: aoc2018, python, puzzle, challenge
Published: 2019-04-21 14:08:07

---
title: "Advent of Code 2018 Day 3: No Matter How You Slice It"
tags: ["aoc2018", "python", "puzzle", "challenge"]
published: true
categories: ["Advent of Code 2018"]
description: Apparently elves aren't great at teamwork.
---

> This post originally appeared on [steadbytes.com](https://steadbytes.com/blog/advent-of-code-2018/03/)

> Complete solution can be found on [GitHub](https://github.com/SteadBytes/advent-of-code-2018/blob/2c9fe3ab312bdd15b23e1657edd98d3bd1fef8e5/03/solution.py)

## Part One

Given a [puzzle input](https://github.com/SteadBytes/advent-of-code-2018/blob/2c9fe3ab312bdd15b23e1657edd98d3bd1fef8e5/03/input.txt) of **claims**, we are asked to find the **number of square inches of fabric within two or more claims**.

1. Parse the input into a sequence of fabric claims
2. For each square inch of fabric, find the number of claims containing it
3. Count the total number of square inches of fabric where the claim count is greater than one

### Parsing Input

Each line of input represents a claim in the following format:

```
#<ID> @ <left>,<top>: <width>x<height>
```

For example, `#123 @ 3,2: 5x4` corresponds to a rectangle with ID `123`, `3` from the left edge, `2` inches from the top edge, `5` inches wide and `4` inches tall.

1. Split the input on newlines
2. For each line, extract the claim data:
   - ID
   - Distance from the left edge
   - Distance from the top edge
   - Width
   - Height

Extracting claim data can be achieved using a [regular expression](https://en.wikipedia.org/wiki/Regular_expression):

```python
import re

claim_re = re.compile(
    r"#(?P<_id>[0-9]+) @ "
    r"(?P<left>[0-9]+),(?P<top>[0-9]+): "
    r"(?P<width>[0-9]+)x(?P<height>[0-9]+)"
)

m = claim_re.match("#123 @ 3,2: 5x4")
# retrieve all cptured values
m.groups() # -> ('123', '3', '2', '5', '4')
# retreieve a specific captured value
m.groups('_id') # -> '123'
```

- Python [named capture groups](https://www.regular-expressions.info/named.html) are used to make the extracted pieces of data clearer.
- [Interactive demo and explanation of this regex](https://regex101.com/r/MKLnmx/1)

The extracted values from the regular expression are strings, however for this puzzle they represent integers. Furthermore, once the values are extracted the regular expression match object is no longer needed and the claim could be represented by it's own object. Since this is Python, a `dict` will do the trick!

Given a claim from the puzzle input:

1. Match each value using the `claim_re` regular expression
2. Create a `dict` where the keys are the names of the groups, and the values are the extracted strings parsed to integers:

```python
def parse_claim(claim_string):
    m = claim_re.match(claim_string)
    return {k: int(v) for k, v in m.groupdict().items()}

parse_claim("#123 @ 3,2: 5x4")
# {'_id': 123, 'left': 3, 'top': 2, 'width': 5, 'height': 4}
```

### Representing The Fabric

For this puzzle, the fabric can be thought of as grid where each coordinate represents a square inch of fabric and contains an integer denoting the number of claims upon it. Given the single claim from in the previous example:

```
00000000000
00000000000
00011111000
00011111000
00011111000
00011111000
00000000000
00000000000
00000000000
```

For each claim:

1. Find the 'physical' area (coordinates in the grid) it will cover
2. Increment the corresponding claim counts in the fabric

Finding the area represented by a claim can be achieved using the positions (left, top) and the dimensions (width, height) extracted from the puzzle input:

```python
def claim_area(claim):
    return (
        (i, j)
        for i in range(claim["left"], claim["left"] + claim["width"])
        for j in range(claim["top"], claim["top"] + claim["height"])
    )
```

This function takes a claim `dict` produced by the previous `parse_claim` function and returns a [generator](https://wiki.python.org/moin/Generators) which yields pairs of `(x, y)` coordinates in the fabric grid which are conatined within the claim.

The most intuitive way to represent the fabric grid is using a 2D array structure:

```python
fabric = []
for y in range(height_of_fabric):
    row = []
    for x in range(width_of_fabric):
        row.append(0)
    fabric.append(row)

# to update the fabric counters for a claim
for x, y in claim_area("#123 @ 3,2: 5x4"):
    fabric[y][x] += 1
```

However, we don't actually need the information represented by the structure of the entire fabric - only the number of claims present for each square inch. Furthermore, we don't actually know the exact size of the fabric to use as the limits for the array structure. The question only gives a lower bound:

> The whole piece of fabric they're working on is a very large square - at least `1000` inches on each side.

To avoid the unecessary overhead of building and iterating over a large 2D array, we can use a dictionary where the keys are the coordinates and the values are the number of claims upon that position:

```python
fabric =  {}

# to add a claim
for coord in claim_area("#123 @ 3,2: 5x4"):
    if coord in fabric:
        fabric[coord] += 1
    else:
        fabric[coord] = 1

fabric[(3, 2)] # -> 1
```

With this improvement, we are no longer storing values for positions in the fabric with no claims. Counting values in a dictionary like this is a common operation and as such, Python includes a built in `Counter` data structure in the [collections](https://docs.python.org/3/library/collections.html#collections.Counter) module. Given a list `claims` containg every single claim parsed from the puzzle input, the entire fabric can be represented as such:

```Python
fabric = Counter(coord for claim in claims for coord in claim_area(claim))

fabric[(3, 2)] # -> number of claims at position (3, 2)
```

### Finding The Overlapping Claims

Armed with our `fabric` finding the number of square inches within two or more claims requires counting the total number of values in the `fabric` that are greater than 1:

```python
def part_1(fabric):
    return sum([1 for claim_count in fabric.values() if claim_count > 1])
```

For my puzzle input, the result is **115348**.

## Part 2

Next, we are told that there is a **single** claim which has no overlap with any other and are asked to find the **ID** of said claim.

This claim will have a counter value of `1` for each of the coordinates contained within it in the `fabric`.

1. Iterate over every claim
2. Retrieve the counter values from the `fabric` of every coordinate within the claim
3. If every value is equal to `1`, return the ID of the claim

```python
def part_2(claims, fabric):
    for claim in claims:
        # all returns True if and only if each value is True
        if all(fabric[coord] == 1 for coord in claim_area(claim)):
            return claim["_id"]
```

For my puzzle input, the result is **ID 188**.

### Resources

- [Regular Expression Named Capture Groups](https://www.regular-expressions.info/named.html)
- [regex101](https://regex101.com/)
- [collections.Counter](https://docs.python.org/3/library/collections.html#collections.Counter)