Advent of Code 2022 - Day 3

Day 3: Rucksack Reorganization

Useful Links

‹›

Concepts and Packages Demonstrated

defaultdict enumerate sets Comprehension

Problem Intro
Part 1
Part 2
Results

Problem Intro

This problem is about looking at the items in rucksacks, and looking for common items.

The input data looks something like this:

vJrwpWtwJgWrhcsFMMfFFhFp
jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL
PmmdzqPrVvPwwTWBwg
wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn
ttgJtRGJQctTZtZT
CrZsJsPPZsGzwwsLwLmpwMDw

Each line each represents a rucksack full of items.
Each letter represents an item. (And A is a different item to a.)
The first half of the line is rucksack compartment 1. The second half is compartment 2.
We’re told letterz a-z are given priorities 1-26. Letterz A-Z are priorities 27-52.

Part 1

Find the item type that appears in both compartments of each rucksack. What is the sum of the priorities of those item types?

First, let’s build a dictionary that maps all the item characters to their corresponding priority values:

    item_to_priority = {} # a:1, b:2... Y:51, Z:52
    for i, ordinal in enumerate(range(ord('a'), ord('z')+1), start=1):
        item_to_priority[chr(ordinal)] = i
    for i, ordinal in enumerate(range(ord('A'), ord('Z')+1), start=27):
        item_to_priority[chr(ordinal)] = i

This works by:

Iterating over each letter of the alphanet, starting with a and A, respectively. Here we use ord() to turn an character into its ordinal, i.e. its int representation.
With each iteration, maintain a count which is actually the priority. We can do this easily using enumerate.
Convert the current ordinal back to its character, and add to the dict, using the character is the key and the priority as the value.

    priorities = []
    for rucksack in data:
        compartment_1 = set(rucksack[0:len(rucksack)//2])
        compartment_2 = set(rucksack[len(rucksack)//2:])
        common = compartment_1 & compartment_2 # intersection
        for item in common:
            priorities.append(item_to_priority[item])
    
    print(f"Part 1: Sum of priorities = {sum(priorities)}")

What this does:

Split the rucksack into two compartments using slicing.
Turn each compartment to a set to remove duplicates.
Use the set intersection method to return the items that are common to both compartments.
Convert the common items to their priorities, using the dictionary we built earlier.
Sun the priority values.

Easy!

Part 2

Find the item type that corresponds to the badges of each three-Elf group. What is the sum of the priorities of those item types?

We’re told that each successive group of three input lines represents an elf group. We need to find items that are common to all three rucksacks in each group. Then we add up the priorities of these items, as before.

First, I’ll create dictionary, where the key is the group number, and the value is list of the three rucksacks that make up that group. I’m building the dictionary using defaultdict:

    # Goal is # {1: ['vJrw...', 'jqHR...', 'Pmmd...'], 2: [...], ...} etc
    groups = defaultdict(list) 
    group_num = 1
    for line_num, rucksack in enumerate(data):
        if line_num > 0 and line_num % GRP_SZ == 0:
            group_num += 1
        
        groups[group_num] += [rucksack]

Note that we once again use enumerate() to get the current line number. And when each line number is a multiple of GRP_SZ (which is 3), we increment the group number.

Finally, we’re ready to iterate over each group, and find the items that are common in each group:

    priorities = []
    for rucksacks in groups.values():
        rucksack_sets = [set(sack) for sack in rucksacks]
        common = set.intersection(*rucksack_sets)
        for item in common:
            priorities.append(item_to_priority[item])        
        
    print(f"Part 2: Sum of priorities = {sum(priorities)}")

Recall that each group is a dictionary. Recall that each dictionary value is a list of three rucksacks. I convert each rucksack to a set, using list comprehension. Then we use the cool set.intersection() method, which allows us intersect (i.e. find the commonality of) any number of sets using the splat * operator. This gives us the items that are common to all three rucksacks.

Finally, we can convert these items to priorities, as before.

Results

The final code looks like this:

from collections import defaultdict
from pathlib import Path
import time

SCRIPT_DIR = Path(__file__).parent
INPUT_FILE = Path(SCRIPT_DIR, "input/input.txt")

GRP_SZ = 3

def main():
    with open(INPUT_FILE, mode="rt") as f:
        data = f.read().splitlines()
        
    item_to_priority = {} # a:1, b:2... Y:51, Z:52
    for i, ordinal in enumerate(range(ord('a'), ord('z')+1), start=1):
        item_to_priority[chr(ordinal)] = i
    for i, ordinal in enumerate(range(ord('A'), ord('Z')+1), start=27):
        item_to_priority[chr(ordinal)] = i
    
    priorities = []
    for rucksack in data:
        compartment_1 = set(rucksack[0:len(rucksack)//2])
        compartment_2 = set(rucksack[len(rucksack)//2:])
        common = compartment_1 & compartment_2 # intersection
        for item in common:
            priorities.append(item_to_priority[item])
    
    print(f"Part 1: Sum of priorities = {sum(priorities)}")
    
    # Goal is # {1: ['vJrw...', 'jqHR...', 'Pmmd...'], 2: [...], ...} etc
    groups = defaultdict(list) 
    group_num = 1
    for line_num, rucksack in enumerate(data):
        if line_num > 0 and line_num % GRP_SZ == 0:
            group_num += 1
        
        groups[group_num] += [rucksack]
    
    priorities = []
    for rucksacks in groups.values():
        rucksack_sets = [set(sack) for sack in rucksacks]
        common = set.intersection(*rucksack_sets)
        for item in common:
            priorities.append(item_to_priority[item])        
        
    print(f"Part 2: Sum of priorities = {sum(priorities)}")
    
if __name__ == "__main__":
    t1 = time.perf_counter()
    main()
    t2 = time.perf_counter()
    print(f"Execution time: {t2 - t1:0.4f} seconds")

The output looks like this:

Part 1: Sum of priorities = 8240
Part 2: Sum of priorities = 2587
Execution time: 0.0015 seconds

‹›

Learning Python with Advent of Code Walkthroughs