Day 4: Camp Cleanup

Part 1

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.

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

# Python imports

from pathlib import Path

test = Path("data/day04_test.txt")  # test data
data = Path("data/day04_data.txt")  # puzzle data

def parse_input(fpath: Path) -> list[list[tuple[int, int]]]:
    """Return list of elf cleaning assignments
    
    :param fpath:  path to puzzle input
    
    Each assignment is a list with two tuples. Each tuple is the
    section for a single elf. Each tuple has (start, end) locations
    for that section.
    """
    assignments = []  # hold elf cleaning assignments as lists of tuples of (start, end) pairs
    
    with fpath.open() as ifh:
        for elves, line in enumerate([_.strip() for _ in ifh.readlines()]):
            entry = line.split(",")
            assignment = []
            for section in entry:
                start, end = (int(_) for _ in section.split("-"))
                assignment.append((start, end))
            assignments.append(sorted(assignment))  # earliest-starting assignment first
                
    return assignments
    
def find_contained_assignments(assignments: list[list[tuple[int, int]]]) -> list[list[tuple[int, int]]]:
    """Return elf cleaning assignments where one section is contained in the other
    
    :param assignments:  list of cleaning assignments
    
    Each assignment is a list with two tuples. Each tuple is the
    section for a single elf. Each tuple has (start, end) locations
    for that section.
    """
    contained = []
    for ass in assignments:

        # section 1 doesn't start before section 0 AND section 1 doesn't end after section 0
        if ass[1][0] >= ass[0][0] and ass[1][1] <= ass[0][1]:
            contained.append(ass)
        # ELSE section 1 starts at same point as section 0 AND section 0 doesn't end after section 1
        elif ass[1][0] == ass[0][0] and ass[0][1] <= ass[1][1]:
            contained.append(ass)
            
    return contained

    
def part1(fpath: Path) -> int:
    """Solve the puzzle
    
    :param fpath:  path to puzzle input
    """    
    assignments = parse_input(fpath)  # load puzzle input
    contained = find_contained_assignments(assignments)  # find how many assignments are contained
    
    return len(contained)

part1(test)

2

part1(data)

459

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.

In how many assignment pairs do the ranges overlap?

def find_overlap_assignments(assignments: list[list[tuple[int, int]]]) -> list[list[tuple[int, int]]]:
    """Return elf cleaning assignments where one section overlaps the other
    
    :param assignments:  list of cleaning assignments
    
    Each assignment is a list with two tuples. Each tuple is the
    section for a single elf. Each tuple has (start, end) locations
    for that section.
    """
    overlaps = []
    for ass in assignments:
        
        # section 1 ends within section 0
        if ass[1][1] >= ass[0][0] and ass[1][1] <= ass[0][1]:
            overlaps.append(ass)
        # section 1 starts within section 0
        elif ass[1][0] >= ass[0][0] and ass[1][0] <= ass[0][1]:
            overlaps.append(ass)
            
    return overlaps


def part2(fpath: Path) -> int:
    """Solve the puzzle
    
    :param fpath:  path to puzzle input
    """
    assignments = parse_input(fpath)  # load puzzle input
    overlaps = find_overlap_assignments(assignments)  # find how many assignments overlap
    
    return len(overlaps)

part2(test)

4

part2(data)

779