Advent of Code 2022: Day 3

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

For this puzzle, we're given the items in a number of elves' rucksacks as input. Each line of input represents a rucksack, and each character on a line is an item.

vJrwpWtwJgWrhcsFMMfFFhFp
jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL
PmmdzqPrVvPwwTWBwg
wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn
ttgJtRGJQctTZtZT
CrZsJsPPZsGzwwsLwLmpwMDw

Each item has an associated priority, a–z have priorities 1–26 and A–Z have 27–56. That sounds like it'll be useful; so let's make a lookup table for it.

Conveniently, the ascii_letters constant in the string module has these letters in our desired order already.

>>> from string import ascii_letters
>>> ascii_letters
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

So we can enumerate that into an lookup table using a simple a dictionary comprehension.

from solver import Solver
from string import ascii_letters


class RucksackReorg(Solver):
    item_priorities = {
        item: priority
        for priority, item
        in enumerate(ascii_letters, start=1)
    }

Which will look something like:

>>> RucksackReorg.item_priorities
{
    "a": 1,
    "b": 2,
    ...
    "z": 26,
    "A": 27,
    "B": 28,
    ...
    "Z": 52,
}

Wonderful.

Part One

Each rucksack has two compartments of equal size. The first half of the items are in one compartment, and the second half are in the other. One item type will present in both compartments. The desired output is the sum of the priorities of these shared items across all rucksacks.

At a high level, our solution will determine which item is shared between the two compartments for every rucksack, convert them to priorities, and sum the priorities. But let's make an observation first.

We but first we can observe that the mapping from items to priorities is a bijection—which is to say that it's one-to-one and onto. Being one-to-one, distinct elements of the input (items) map to distinct elements of the output (priorities). Because distinct items will produce distinct priorities, we can convert the items to priorities up front and work with them directly in the solution. Let's do that in our parse function to produce a list of rucksacks which are lists of priorities.

class RucksackReorg(Solver):
    ...

    rucksacks: list[list[int]]

    def parse_input(self) -> None:
        self.rucksacks = [
            [self.item_priorities[item] for item in line]
            for line in self.input_lines
        ]

Starting from the end result and working backwards, it'd be nice if we could define our solution as a simple map-reduce. Let's map rucksacks to shared priorities and reduce the result to a sum.

class RucksackReorg(Solver):
    ...

    def solve_part_one(self) -> int:
        return sum(
            map(
                self.compartment_shared_priority,
                self.rucksacks
            )
        )

To convert a rucksack to the shared priority of its compartments, we'll split the rucksack into halves, and return the priority that they share.

We could manually split the rucksack using list slicing, but the more-itertools package provides a chunked function. So instead we can just chunk the rucksack into two compartments of half size.

from more_itertools import chunked
from solver import Solver
from string import ascii_letters


class RucksackReorg(Solver):
    ...

    def compartment_shared_priority(
        self, rucksack: list[int]
    ) -> int:
        compartment_size = len(rucksack) // 2
        return self.shared_priority(
            chunked(rucksack, compartment_size)
        )

Now we can determine the shared priority for the two compartments. Python's set built-in has syntactic sugar for intersection. So we can use that to find the shared priority. With the power of Future Vision™, I know it will be useful to determine the shared priority among multiple collections of items. So rather than hard-code it to two, let's support an N-collection intersection.

We'll start with the universal set (all item priorities), and iteratively intersect all of the collections of priorities. According to the puzzle description, there should only be one shared item between any two compartments; so our set of shared priorities should only have one element. However if we sum the set, we can support any number of shared elements with no extra work.

class RucksackReorg(Solver):
    ...

    def shared_priority(
        self, priority_collections: list[list[int]]
    ) -> int:
        shared_priorities = set(self.item_priorities.values())

        for priorities in priority_collections:
            shared_priorities &= set(priorities)

        return sum(shared_priorities)

And with that our solution for part one is complete. Testing it with the sample input produces the correct answer 157.

Part Two

Rather than summing the priorities for items shared between each rucksack's compartments, in part two we need to sum the priorities for items shared between every group of 3 elves' rucksacks. Because of the aforementioned Future Vision™, this is trivially easy to do with the tools we've already got.

class RucksackReorg(Solver):
    ...

    def solve_part_two(self) -> int:
        return sum(
            map(
                self.shared_priority,
                chunked(self.rucksacks, 3)
            )
        )

Testing it with the sample input produces the correct answer 70.

You can try this solution in your browser with Pyodide.