Advent of Code 2023, Day 15

❄️ Back to Advent of Code 2023 solutions homepage ❄️

# Imports
from aoc23.utils import read_input

input_15 = read_input(15)

Part 1

In part 1 of the day 15 puzzle, we are asked to implement a simple hash function, which maps strings to integers in the range $[0, 255]$. The algorithm looks up the ASCII code each each character (using the built-in ord function in Python), multiplies by $17$ and takes the remainder mod $256$:

def hash_algorithm(string: str) -> int:
    ascii_codes = [ord(char) for char in string]
    current_value = 0
    for code in ascii_codes:
        current_value += code
        current_value = (17*current_value) % 256
    return current_value

assert hash_algorithm('rn=1') == 30
assert hash_algorithm('cm-') == 253
assert hash_algorithm('qp=3') == 97
assert hash_algorithm('cm=2') == 47

On the provided test input, the sum of these hashes for each step should equal $1320$:

test_input = 'rn=1,cm-,qp=3,cm=2,qp-,pc=4,ot=9,ab=5,pc-,pc=6,ot=7'
test_steps = test_input.split(',')
sum([hash_algorithm(step) for step in test_steps])

1320

And the sum for the full list of input strings is:

steps = input_15[0].split(',')
sum([hash_algorithm(step) for step in steps])

521434

So the answer to part 1 is: 521434.

Part 2

There are now 256 boxes, in which there are slots into which lenses can be placed. Each lens has a different focal length, which is an integer in the range $[0, 9]$. Now, the hash shouldn’t be applied to the whole string, but only to the portion before the = or - characters; the original portion of string is the label of the new lens, and the hash tells us which of the boxes to modify the contents of at each step. What needs to be done next depends on which subsequent character is present:

• If the next character is -, then we remove the lens in the chosen box with the matching label (if it exists). All other lenses are shuffled up to remove any gaps
• If the next character is =, then we replace the lens currently in the chosen box with the matching label, if it exists. If there is not a lens with a matching label, add the new lens to the next slot in the box (leaving no gaps).

The dict type in Python is the ideal data structure to use here, as it has the following properties:

• Checking for membership is quick (independent of the size of the dict)
• The keys are kept in the order in which they are added. Therefore, when looping over all keys in the dict, we will obtain them from oldest to newest by default
• The pop method allows keys to be removed from the dict, without interfering with the order of the remaining keys.

Here is the implementation of the lens fitting process:

def place_lenses(steps: list[str]) -> list[dict[str, int]]:
    
    # Each box: {label: focal}
    boxes = [{} for _ in range(256)]
    
    for step in steps:
        if step[-1] == '-':
            # Get label and box index
            label = step[:-1]
            box_idx = hash_algorithm(label)
            
            # Remove lens (if it exists)
            boxes[box_idx].pop(label, None)
            
        elif '=' in step:
            # Get label, focal length and box index
            label, focal = step.split('=')
            box_idx = hash_algorithm(label)
            
            # Replace or add lens
            boxes[box_idx][label] = int(focal)

        else:
            raise ValueError('invalid step!')
    
    return boxes

Let’s check this on the provided test case:

test_boxes = place_lenses(test_steps)

for i, box in enumerate(test_boxes):
    if len(box) != 0:
        print(f'Box {i}: {box}')

Box 0: {'rn': 1, 'cm': 2}
Box 3: {'ot': 7, 'ab': 5, 'pc': 6}

This matches what was expected. Furthermore, the focusing power can be computed from the boxes easily:

def compute_focusing_power(boxes):
    power = 0
    for box_num, box in enumerate(boxes):
        for slot, (label, focal) in enumerate(box.items()):
            power += (box_num + 1)*(slot + 1)*focal
    return power

assert compute_focusing_power(test_boxes) == 145
print('Success!')

Success!

Finally, we can compute the boxes and focusing power on the full set of input steps:

boxes = place_lenses(steps)
compute_focusing_power(boxes)

248279

So the answer to part 2 is: 248279.

❄️ Back to Advent of Code 2023 solutions homepage ❄️