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.
- Parse the input into a sequence of fabric claims
- For each square inch of fabric, find the number of claims containing it
- 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.
- Split the input on newlines
- 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:
- Match each value using the
claim_re
regular expression - 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:
- Find the 'physical' area (coordinates in the grid) it will cover
- 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
.
- Iterate over every claim
- Retrieve the counter values from the
fabric
of every coordinate within the claim - 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.
Top comments (0)