Advent of Code 2018 Day 3: No Matter How You Slice It

This post originally appeared on steadbytes.com

Complete solution can be found on GitHub

Part One

Given a puzzle input 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:

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 are used to make the extracted pieces of data clearer.
• Interactive demo and explanation of this regex

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:

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:

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 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:

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:

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 module. Given a list claims containg every single claim parsed from the puzzle input, the entire fabric can be represented as such:

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:

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

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
• regex101
• collections.Counter