Advent of Code 2018 - Day 3

Useful Links

Concepts and Packages Demonstrated

Problem Intro

The Elves are arguing over how to cut the prototype fabric for Santa’s suit. They have a large square piece of fabric, at least 1000x1000 inches. Each Elf has made a claim for a rectangular area of this fabric. The problem is that many of these claims overlap.

The input is a list of claims, looking like this:

#1 @ 1,3: 4x4
#2 @ 3,1: 4x4
#3 @ 5,5: 2x2

Each line describes a claim with:

An ID (e.g., #1)
Coordinates of the top-left corner (inches from left, inches from top)
Dimensions (width x height)

Part 1

How many square inches of fabric are within two or more claims?

To solve this, we need to:

Parse the input claims into a usable format.
Model the fabric grid.
Mark each claim on the grid.
Count the number of grid cells that have been marked more than once.

Parsing the Claims

We can use Python’s re module to extract the numbers from each line. We’ll define a simple Dataclass to store the claim details.

@dataclass
class Claim:
    claim_id: int
    x: int
    y: int
    width: int
    height: int

matcher = re.compile(r"#(\d+) @ (\d+),(\d+): (\d+)x(\d+)")

def process_data(data):
    """ 
    Process the data into a list of claims
    Input is a list of claim strings. Each string is in the format #1 @ 1,3: 4x4, which represents a rectangle on a fabric.
    Output is a list of claims.
    """
    claims = []
    for claim in data:
        # Extract groups, map them to ints, and unpack into the Claim constructor
        claims.append(Claim(*map(int, matcher.match(claim).groups())))
    return claims

Modeling the Fabric

A 2D grid is a perfect use case for NumPy. We can create a 1000x1000 array of zeros. For each claim, we can use NumPy’s powerful slicing to increment the values in the corresponding rectangular region.

If a cell has a value of 0, it’s unclaimed.
If a cell has a value of 1, it’s claimed by exactly one Elf.
If a cell has a value > 1, it’s part of an overlap.

Finally, to get the answer for Part 1, we just count how many cells have a value greater than 1. NumPy makes this easy with boolean indexing.

The expression (array > 1) creates a boolean mask (an array of the same shape where each element is True if the condition is met, and False otherwise).

When we call .sum() on this boolean array, NumPy treats True as 1 and False as 0. Thus, summing the mask effectively counts the number of True values, which gives us the total number of overlapping square inches.

def part1(data):
    """
    Return sum of squares where array > 1 (claimed by 2+ Elves)
    """
    array = np.zeros((1000, 1000), dtype=int)
    claims = process_data(data)
    for claim in claims:
        array[claim.x:claim.x+claim.width, claim.y:claim.y+claim.height] += 1
    
    return (array > 1).sum()  # Count squares where array > 1 (claimed by 2+ Elves)

Part 2

What is the ID of the only claim that doesn’t overlap?

We are told that there is exactly one claim that has no overlaps. We can re-use the grid construction logic from Part 1.

We simply iterate through our list of claims again. For each claim, we look at the corresponding slice of the grid. If every cell in that slice has a value of exactly 1, then that claim overlaps with nothing else (because if it did, some cells would be > 1).

We use the .all() method here. This method returns True if and only if all elements in the array (or slice) evaluate to True. So, (slice == 1).all() checks if every single cell in that specific claim’s region has a value of 1.

def part2(data):
    """
    Return ID of claim that does not overlap
    """
    array = np.zeros((1000, 1000), dtype=int)
    claims = process_data(data)

    # First increment array for each claim
    for claim in claims:
        array[claim.x:claim.x+claim.width, claim.y:claim.y+claim.height] += 1
    
    # Then go through the claims again and check if all squares in the claim are claimed by only one Elf
    for claim in claims:
        if (array[claim.x:claim.x+claim.width, claim.y:claim.y+claim.height] == 1).all():
            return claim.claim_id

    raise AssertionError("No non-overlapping claim found")

This approach is efficient because checking a slice in NumPy is very fast.

Results

The output looks like this:

Part 1 soln=123456
Part 2 soln=456

‹