day4

Day 4: Camp Cleanup

The list of camp cleanup assignments has unfortunate overlaps. For example:

2-4,6-8   First elf has sections 2,3,4; Second has 6,7,8.
2-3,4-5   First has 2,3; Second has 4,6
5-7,7-9   First has 5,6,7; Second has 7,8,9.

Actual numbers may be higher.

Some assignments fully contain the other.

Find them.

Example:

Consider this list of assignments.

example = """
2-4,6-8
2-3,4-5
5-7,7-9
2-8,3-7
6-6,4-6
2-6,4-8
""".strip().split()

We could do this by comparing min & max. Or we could generate sets from ranges and check intersection is as large as the smaller range. But the second could struggle with very large ranges.

Code

def get_assignments(data: list[str] # List of assignment pairs "2-4,6-8"
                    ) -> list[list[int]]: # List of [min,max,min,max]
    """Split each assignment by commas and dashes."""
    _ = (row.replace("-",",").split(",") for row in data)
    return [[int(x) for x in row] for row in _]

---

source

get_assignments

 get_assignments (data:list[str])

Split each assignment by commas and dashes.

	Type	Details
data	list	List of assignment pairs “2-4,6-8”
Returns	list	List of [min,max,min,max]

assignments = get_assignments(example)
assignments

[[2, 4, 6, 8],
 [2, 3, 4, 5],
 [5, 7, 7, 9],
 [2, 8, 3, 7],
 [6, 6, 4, 6],
 [2, 6, 4, 8]]

Code

def right_contains_left(row: list[int] # [min,max,min,max]
                       )-> bool: # Right pair contains left
    return (row[2] <= row[0]) and (row[3] >= row[1])

def left_contains_right(row: list[int] # [min,max,min,max]
                       )-> bool: # Left pair contains right
    return (row[0] <= row[2]) and (row[1] >= row[3])

def contains(row: list[int] # [min,max,min,max]
            )-> bool: # One pair contains the other
    return right_contains_left(row) or left_contains_right(row)

---

source

contains

 contains (row:list[int])

	Type	Details
row	list	[min,max,min,max]
Returns	bool	One pair contains the other

---

source

left_contains_right

 left_contains_right (row:list[int])

	Type	Details
row	list	[min,max,min,max]
Returns	bool	Left pair contains right

---

source

right_contains_left

 right_contains_left (row:list[int])

	Type	Details
row	list	[min,max,min,max]
Returns	bool	Right pair contains left

Test that

assert [contains(row) for row in assignments] == [False, False, False, True, True, False]

Part 1

Get the data

with open("data/day4_input.txt") as f:
    data = [x.strip() for x in f.readlines()]
data[:3]

['14-28,13-28', '72-81,82-91', '4-4,6-95']

Run

assignments = get_assignments(data)
contains = [contains(row) for row in assignments]
f"{sum(contains):,} assignment pairs fully overlap"

'305 assignment pairs fully overlap'

Part 2

OK, how many overlap at all?

Tempting to reuse day2.intersect but in case the ranges are billions long, let’s just do some min/max checking again. For some reason it’s easier for me to reason about disjoint first and then define overlap as not disjoint.

Code

def disjoint(row: list[int] # [min,max,min,max]
            )-> bool:       # The ranges are disjoint
    # min1 > max2 or max1 < min2
    return (row[0] > row[3]) or (row[1] < row[2])

def overlap(row: list[int] # [min,max,min,max]
            )-> bool:       # The ranges overlap
    return not disjoint(row)

---

source

overlap

 overlap (row:list[int])

	Type	Details
row	list	[min,max,min,max]
Returns	bool	The ranges overlap

---

source

disjoint

 disjoint (row:list[int])

	Type	Details
row	list	[min,max,min,max]
Returns	bool	The ranges are disjoint

Run

overlaps = [overlap(x) for x in get_assignments(data)]
f"{sum(overlaps):,} assignments overlap at all."

'811 assignments overlap at all.'