Advent of Code Day 15 — Lens Library

The header art was used with the permission of the artist, YellowZorro. You can find more of their AoC-themed art here!

All the light you collected yesterday has to go somewhere, and that somewhere is here — a light focusing facility with a thousand different lenses… and a reindeer who perhaps works there? They are very happy to see a human, as while they know what needs to be done, they can’t actually do it.

That, of course, is where you come in.

Part 1

The input is a vast number of comma-separated values, looking like this:

rn=1,cm-,qp=3,cm=2,qp-,pc=4,ot=9,ab=5,pc-,pc=6,ot=7

The actual puzzle input is much, much more. The puzzle gives instructions on how to form a hash of a string. A hash is simply a way of turning a string into a number. More than one string can generate the same hash, especially in the case of this one, that only has 256 values.

def deer_hash(s: str) -> int:
    return reduce(lambda h, c: ((h + ord(c)) * 17) % 256, s, 0)

def part1():
    print ("Part 1:", sum(deer_hash(x) for x in read_data().split(',')))

deer_hash applies the hashing algorithm to each character in turn, using reduce, a function that takes a list, applies a lambda (AKA anonymous function, et al) to each element, and returns a single value.

part1 sums the hashes of the input data.

Part 2

It turns out that the input data are actually instructions. Tokens of the form (<label>=<number>) are instructions to put the lens of focal length <number> in the box numbered deer_hash(<label>) and the lens would be labeled with that label as well. The order of the lenses is important, so there is to be no shuffling. Tokens of the form (<label>-) are instructions to remove the labeled lens from the deer_hash’d box.

At the end, calculate the power of each lens, which the product of its box number + 1, its position in the box +1, and its focal length, and sum those up for every lens in every box.

What the puzzle describes is an “ordered hash”. Python’s native dictionary object implements this, so I just made a list of dictionaries, and parsed the commands to add and remove things as necessary.

def part2():
    boxes = [{} for i in range(256)]
    for x in read_data().split(','):
        # use re to find the label, contiguous letters at the start of the string
        label = re.match(r'^[a-z]+', x).group(0)
        box = boxes[deer_hash(label)]
        if '=' in x: box[label] = int(x.split('=')[1])
        else: box.pop(label, None)
    # sum the product of the box number + 1, the position in the box + 1 
    # and the lens for each lens in each box
    print ("Part 2:", sum((k+1)*(i+1)*v 
                          for k, v in enumerate(boxes) 
                          for i, v in enumerate(v.values())))

The code works as I mentioned. We make the boxes, each with a dictionary inside. For each command, we extract the label (the letters at the beginning of the command), figure out which box we’re working with, and if this is an insert/replace command, doing the needful. Otherwise it is a remove command, and we remove it. Then we score it and done.

A short puzzle for today!