Advent of Code 2022: Day 4

If you haven't already, take a look at the prep work we did on day 0, and view the puzzle description on AoC.

Today, we're given pairs of cleaning assignments for elves. They're represented as integer ranges, two per line of puzzle input. Let's start out by parsing them into range built-ins.

2-4,6-8
2-3,4-5
5-7,7-9
2-8,3-7
6-6,4-6
2-6,4-8

If you're like me, you might think of ranges as just iterators used to feed for loops. But they're much more than that. They fully implement the Sequence interface, and as such, support len, slicing, indexing, and other features we normally think of with lists and tuples. But in our case we're just using them as a convenient, performant container for our start and stop integer values.

Speaking of integers, one thing we'll see more of as we progress through Advent of Code is the need to parse integers out of a line of input that contains other stuff we don't care about. So let's factor that out of our parsing so we can reuse it in the future. We'll just use regular expressions from the re module to substitute all of the non-digit characters with spaces, split the result into integer strings, and map the integer strings to native integers. Then we can use that to unpack the range start and stop values on each line.

import re
from solver import Solver


def parse_integers(line: str) -> list[int]:
    integer_strs = re.sub(r"[^\d]", " ", line)
    return list(map(int, integer_strs.split()))


class CampCleanup(Solver):
    assignment_pairs: list[tuple[range, range]]

    def parse_input(self) -> None:
        self.assignment_pairs = []

        for line in self.input_lines:
            (
                first_start, first_stop,
                second_start, second_stop
            ) = parse_integers(line)

            self.assignment_pairs.append(
                (
                    range(first_start, first_stop),
                    range(second_start, second_stop)
                )
            )

Part One

With our input parsed into assignment range pairs, we're ready to solve part one. The desired output is the number of range pairs where one range fully overlaps the other.

Let's start by defining "fully overlaps" for two ranges. This occurs when the start and stop values for one range are both outside or include the other's.

Which we can write easily enough as a boolean expression.

def fully_overlaps(first: range, second: range) -> bool:
    return (
        (first.start <= second.start and second.stop <= first.stop)
        or
        (second.start <= first.start and first.stop <= second.stop)
    )

Using that, we can define our solution. And making the observation that a Python bool is just a subclass of int restricted to the values 0 and 1, we can directly sum the number of assignment pairs that fully overlap.

class CampCleanup(Solver):
    ...

    def solve_part_one(self) -> int:
        return sum(
            fully_overlaps(*assignment_pair)
            for assignment_pair in self.assignment_pairs
        )

That solves part one. Testing it with the sample input produces the correct answer 2.

Part Two

Very similar to part one is the desired output of part two–find the number of assignment pairs that overlap at all.

Determining if two ranges overlap is a classic programming puzzle with a very compact solution, but I can never remember it off the top of my head. Let's work backwards again, because it's easier to define two ranges that don't overlap.

Two ranges are disjoint if the start of either range is greater than the stop of the other.

def disjoint(first: range, second: range) -> bool:
    return first.start > second.stop or second.start > first.stop

So the solution we're looking for is the negation of this, which we can do with no additional operation using De Morgan's law—the most useful thing you can learn in discrete mathematics.^{[citation needed]}

It allows us to negate our disjoint boolean expression "for free" (computationally-speaking) to create our overlaps boolean expression.

def overlaps(first: range, second: range) -> bool:
    return first.start <= second.stop and second.start <= first.stop

With that we can define our solution to part two.

class CampCleanup(Solver):
    ...

    def solve_part_two(self) -> int:
        return sum(
            overlaps(*assignment_pair)
            for assignment_pair in self.assignment_pairs
        )

And that solves part two. Testing it with the sample input produces the correct answer 4.

You can try this solution in your browser with Pyodide.