Advent of Code - 2022

This is a solution to Day 4 of Advent of Code 2022.

Day 4 - Camp Cleanup

Space needs to be cleared before the last supplies can be unloaded from the ships, and so several Elves have been assigned the job of cleaning up sections of the camp. Every section has a unique ID number, and each Elf is assigned a range of section IDs.

However, as some of the Elves compare their section assignments with each other, they've noticed that many of the assignments overlap. To try to quickly find overlaps and reduce duplicated effort, the Elves pair up and make a big list of the section assignments for each pair (your puzzle input).

For example, consider the following list of section assignment pairs:
2-4,6-8
2-3,4-5
5-7,7-9
2-8,3-7
6-6,4-6
2-6,4-8
For the first few pairs, this list means:

Within the first pair of Elves, the first Elf was assigned sections 2-4 (sections 2, 3, and 4), while the second Elf was assigned sections 6-8 (sections 6, 7, 8).

The Elves in the second pair were each assigned two sections.

The Elves in the third pair were each assigned three sections: one got sections 5, 6, and 7, while the other also got 7, plus 8 and 9.

This example list uses single-digit section IDs to make it easier to draw; your actual list might contain larger numbers. Visually, these pairs of section assignments look like this:
.234.....  2-4
.....678.  6-8

.23......  2-3
...45....  4-5

....567..  5-7
......789  7-9

.2345678.  2-8
..34567..  3-7

.....6...  6-6
...456...  4-6

.23456...  2-6
...45678.  4-8
Some of the pairs have noticed that one of their assignments fully contains the other. For example, 2-8 fully contains 3-7, and 6-6 is fully contained by 4-6. In pairs where one assignment fully contains the other, one Elf in the pair would be exclusively cleaning sections their partner will already be cleaning, so these seem like the most in need of reconsideration. In this example, there are 2 such pairs.

Read input

When ever I see ranges in the description, I want to import one of my favorite data structures in Python: namedtuples. They are a subset of tuples that are compatible with any code that operates on tuples but provides a few extra goodies, namely named attributes and debug printing.

Our ranges here have two values: start point and end point.

from utils import read_input
    from collections import namedtuple
    
    Range = namedtuple('Range', ['start', 'end'])
    
    def transformer(line):
        first, second = line.split(',')
        x0, x1 = [int(x) for x in first.split('-')]
        y0, y1 = [int(x) for x in second.split('-')]
        return (Range(x0, x1), Range(y0, y1))
    
    data = read_input(4, transformer)

To find whether two ranges are such that one range fully contains another range, we need to check if the start/end values of one are within the boundaries of the start/end values of the other.

def fully_contained(x, y):
    """
    >>> fully_contained(Range(1, 5), Range(2, 3))
    True
    >>> fully_contained(Range(6, 6), Range(4, 6))
    True
    >>> fully_contained(Range(1, 2), Range(2, 3))
    False
    """
    if x.start <= y.start and x.end >= y.end:
        return True
    if y.start <= x.start and y.end >= x.end:
        return True
    return False

In how many assignment pairs does one range fully contain the other?

We can calculate the sum directly from a list or generator of booleans and it will count True as 1 and False as 0.

By using the spread operator (*) with our tuples, we don't need to touch the individual attributes nor indices. *pair is the same as pair[0], pair[1] or pair.start, pair.end.

solution_1 = sum(fully_contained(*pair) for pair in data)
    print(f'Part 1: {solution_1}')
    assert solution_1 == 500

Part 2

It seems like there is still quite a bit of duplicate work planned. Instead, the Elves would like to know the number of pairs that overlap at all.

In the above example, the first two pairs (2-4,6-8 and 2-3,4-5) don't overlap, while the remaining four pairs (5-7,7-9, 2-8,3-7, 6-6,4-6, and 2-6,4-8) do overlap:

5-7,7-9 overlaps in a single section, 7.

2-8,3-7 overlaps all of the sections 3 through 7.

6-6,4-6 overlaps in a single section, 6.

2-6,4-8 overlaps in sections 4, 5, and 6.

So, in this example, the number of overlapping assignment pairs is 4.

For the second part, we need to check a bit more. Now it's enough that either start or end value of one is within the boundaries of the start/end range of the other.

def overlap(x, y):
    """
    >>> overlap(Range(1, 5), Range(2, 3))
    True
    >>> overlap(Range(6, 6), Range(4, 6))
    True
    >>> overlap(Range(1, 2), Range(2, 3))
    True
    >>> overlap(Range(1, 2), Range(4, 5))
    False
    """
    return (
        y.start <= x.start <= y.end or 
        y.start <= x.end <= y.end or
        x.start <= y.start <= x.end or 
        x.start <= y.end <= x.end)

In how many assignment pairs do the ranges overlap?

solution_2 = sum(1 for pair in data if overlap(*pair))
    print(f'Part 2: {solution_2}')
    assert solution_2 == 815

Appendix A - Quick solution

When I was originally solving this day's puzzles, I was in a hurry to catch a train and just wanted to get a quick answer to a) check that my solution worked and b) to get the star into the system as I wasn't sure if I'd have internet on the train.

For part 2, instead of thinking hard on what if conditions I'd need, I decided to turn the ranges into sets and checking for common items.

def set_overlap(x, y):
    """
    >>> set_overlap(Range(1, 5), Range(2, 3))
    True
    >>> set_overlap(Range(6, 6), Range(4, 6))
    True
    >>> set_overlap(Range(1, 2), Range(2, 3))
    True
    >>> set_overlap(Range(1, 2), Range(4, 5))
    False
    """
    return len(set(range(x.start, x.end+1)) & set(range(y.start, y.end+1))) > 0

This works but for ranges where the difference between start and end is huge, it will create very large sets when all we really need are two numbers for each range. Also, since the range function does not include the end argument (ie. range(1, 5) is (1, 2, 3, 4), I couldn't do a more beautiful looking

return len(set(range(*x)) & set(range(*y)))