day3

AoC Day3: Rucksack Reorganization

Each rucksack has two compartments. Items of a type should go into exactly one. Packing elf failed for exactly one item per rucksack.

Input: items now in each rucksack, 52 types a-zA-Z. First half in compartment 1, second in 2.

Read on.

Example:

Suppose we have the following list of 6 pack contents:

example = """
vJrwpWtwJgWrhcsFMMfFFhFp
jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL
PmmdzqPrVvPwwTWBwg
wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn
ttgJtRGJQctTZtZT
CrZsJsPPZsGzwwsLwLmpwMDw
"""

packs_ex = example.split()

We can get their lengths:

lengths = [len(x) for x in packs_ex]
lengths

[24, 32, 18, 30, 16, 24]

Each pack is evenly divided into two comparments:

Code

def get_compartments(packs: list[str] # List of pack contents like ['vJrwpWtw', ...]
                    ) -> list[tuple]: # Split each pack like ('vJrw', 'pWtw')
    """Split each pack down the middle."""
    lengths = [len(x) for x in packs]
    return [(pack[:lengths[i]//2], pack[lengths[i]//2:]) 
                for i, pack in enumerate(packs)]

get_compartments(packs_ex)

[('vJrwpWtwJgWr', 'hcsFMMfFFhFp'),
 ('jqHRNqRjqzjGDLGL', 'rsFMfFZSrLrFZsSL'),
 ('PmmdzqPrV', 'vPwwTWBwg'),
 ('wMqvLMZHhHMvwLH', 'jbvcjnnSBnvTQFn'),
 ('ttgJtRGJ', 'QctTZtZT'),
 ('CrZsJsPPZsGz', 'wwsLwLmpwMDw')]

source

get_compartments

 get_compartments (packs:list[str])

Split each pack down the middle.

	Type	Details
packs	list	List of pack contents like [‘vJrwpWtw’, …]
Returns	list	Split each pack like (‘vJrw’, ‘pWtw’)

Note each pack has precisely one item that is in both compartments:

Code

def get_shared(compartments: list[tuple] # ('vJrw','pWtw')
              ) -> list[str]: # Single char like 'w' here.
    """Find the shared item in each pack: same in both compartments."""
    return [set(left).intersection(right).pop()
            for left, right in compartments]

shared = get_shared(get_compartments(packs_ex))
shared

['p', 'L', 'P', 'v', 't', 's']

source

get_shared

 get_shared (compartments:list[tuple])

Find the shared item in each pack: same in both compartments.

	Type	Details
compartments	list	(‘vJrw’,‘pWtw’)
Returns	list	Single char like ‘w’ here.

And each item has a priority:

   a..z -> 1..26
   A..Z -> 27..52

Code

BASE_LOWER = ord("a") - 1    # 1..26
BASE_UPPER = ord("A") - 27   # 27..52

def priority(char: str # Single char like 'w'
            ) -> int: # Priority 1..52
    """Return priority 1..52 of item in pack."""
    if char.lower() == char:
        return ord(char) - BASE_LOWER
    return ord(char) - BASE_UPPER

source

priority

 priority (char:str)

Return priority 1..52 of item in pack.

	Type	Details
char	str	Single char like ‘w’
Returns	int	Priority 1..52

Test that

assert [priority(x) for x in shared] == [16, 38, 42, 22, 20, 19]

Part 1

Get the data

Decode both moves to R, P, S. Keep as a two-letter string like “RP”.

with open("../data/day3_input.txt") as f:
    packs1 = [x.strip() for x in f.readlines()]
packs1[:5]

['CjhshBJCSrTTsLwqwqwb',
 'GtmnFHlDfcpHbLZjtTTRLWwb',
 'fDfNHHjVFNvvrvVBJJdS',
 'PPWvWQjPhrPQwlMWJJdMDGbJTdCJ',
 'rsqsStgNNggBNBZHSrJGdJdCFRRZCFbGbTdJ']

Run

priorities = [priority(x) for x in
    get_shared(get_compartments(packs1))]
sum(priorities)

Part 2

Elves are divided into “badged” groups of 3.

The “badge” is the only item type carried by all 3.

So in group B, all 3 elves have an item of type B. (Ok.) And at most two have any other item type. (Wait, what?)

Every set of 3 lines in your list is a badge group. In the example, the first 3 lines are group r and the second is Z.

We need to generalize get_shared(). Let’s try functools.reduce and define get_badge with that.

Find badge for a group

Code

from typing import Collection
from functools import reduce

def intersect(left: Collection, # Items in first group
              right: Collection # Items in second group
             ) -> str: # Items common to both 
    """Find set intersection btw two args."""
    return set(left).intersection(right)

def get_badge(group: list[str] # List of item names
             ) -> str: # The single item common to all
    """Find common item. Assumes there is precisely 1."""
    return reduce(intersect, group).pop()

source

get_badge

 get_badge (group:list[str])

Find common item. Assumes there is precisely 1.

	Type	Details
group	list	List of item names
Returns	str	The single item common to all

source

intersect

 intersect (left:Collection, right:Collection)

Find set intersection btw two args.

	Type	Details
left	Collection	Items in first group
right	Collection	Items in second group
Returns	str	Items common to both

assert get_badge(packs_ex[:3]) == "r"
assert get_badge(packs_ex[3:6]) == "Z"

Find groups from packlist

Code

def get_groups(packs: list[str] # List of all packs
              ) -> list[list]:  # Divided into lists of 3
    """Split packlist into groups of 3"""
    return [[packs[i], packs[i+1], packs[i+2]]
            for i in range(0, len(packs), 3)]

source

get_groups

 get_groups (packs:list[str])

Split packlist into groups of 3

	Type	Details
packs	list	List of all packs
Returns	list	Divided into lists of 3

get_groups(packs_ex)

[['vJrwpWtwJgWrhcsFMMfFFhFp',
  'jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL',
  'PmmdzqPrVvPwwTWBwg'],
 ['wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn',
  'ttgJtRGJQctTZtZT',
  'CrZsJsPPZsGzwwsLwLmpwMDw']]

assert [get_badge(group)
        for group in get_groups(packs_ex)] == ['r','Z']

Run

badges = [get_badge(group) 
          for group in get_groups(packs1)]
sum([priority(x) for x in badges])