Dazbo's Advent of Code solutions, written in Python

Day 3: Rucksack Reorganization

defaultdictenumeratesetsComprehension

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.

**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*.

Next:

```
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!

**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.

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
```