[Day 15] Lens Library // Advent of Code 2023 (Python)

Lens Library (via DALL-E 3)

Advent of Code
The newly-focused parabolic reflector dish is sending all of the collected light to a point on the side of yet another…adventofcode.com

---

Part One

The newly-focused parabolic reflector dish is sending all of the collected light to a point on the side of yet another mountain — the largest mountain on Lava Island. As you approach the mountain, you find that the light is being collected by the wall of a large facility embedded in the mountainside.

You find a door under a large sign that says “Lava Production Facility” and next to a smaller sign that says “Danger — Personal Protective Equipment required beyond this point”.

As you step inside, you are immediately greeted by a somewhat panicked reindeer wearing goggles and a loose-fitting hard hat. The reindeer leads you to a shelf of goggles and hard hats (you quickly find some that fit) and then further into the facility. At one point, you pass a button with a faint snout mark and the label “PUSH FOR HELP”. No wonder you were loaded into that trebuchet so quickly!

You pass through a final set of doors surrounded with even more warning signs and into what must be the room that collects all of the light from outside. As you admire the large assortment of lenses available to further focus the light, the reindeer brings you a book titled “Initialization Manual”.

“Hello!”, the book cheerfully begins, apparently unaware of the concerned reindeer reading over your shoulder. “This procedure will let you bring the Lava Production Facility online — all without burning or melting anything unintended!”

“Before you begin, please be prepared to use the Holiday ASCII String Helper algorithm (appendix 1A).” You turn to appendix 1A. The reindeer leans closer with interest.

The HASH algorithm is a way to turn any [string](https://en.wikipedia.org/wiki/String_(computer_science%29) of characters into a single number in the range 0 to 255. To run the HASH algorithm on a string, start with a current value of 0. Then, for each character in the string starting from the beginning:

Determine the ASCII code for the current character of the string.

Increase the current value by the ASCII code you just determined.

Set the current value to itself multiplied by 17.

Set the current value to the remainder of dividing itself by 256.

After following these steps for each character in the string in order, the current value is the output of the HASH algorithm.

So, to find the result of running the HASH algorithm on the string HASH:

The current value starts at 0.

The first character is H; its ASCII code is 72.

The current value increases to 72.

The current value is multiplied by 17 to become 1224.

The current value becomes 200 (the remainder of 1224 divided by 256).

The next character is A; its ASCII code is 65.

The current value increases to 265.

The current value is multiplied by 17 to become 4505.

The current value becomes 153 (the remainder of 4505 divided by 256).

The next character is S; its ASCII code is 83.

The current value increases to 236.

The current value is multiplied by 17 to become 4012.

The current value becomes 172 (the remainder of 4012 divided by 256).

The next character is H; its ASCII code is 72.

The current value increases to 244.

The current value is multiplied by 17 to become 4148.

The current value becomes 52 (the remainder of 4148 divided by 256).

So, the result of running the HASH algorithm on the string HASH is 52.

The initialization sequence (your puzzle input) is a comma-separated list of steps to start the Lava Production Facility. Ignore newline characterswhen parsing the initialization sequence. To verify that your HASH algorithm is working, the book offers the sum of the result of running the HASH algorithm on each step in the initialization sequence.

For example:

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

This initialization sequence specifies 11 individual steps; the result of running the HASH algorithm on each of the steps is as follows:

rn=1 becomes 30.

cm- becomes 253.

qp=3 becomes 97.

cm=2 becomes 47.

qp- becomes 14.

pc=4 becomes 180.

ot=9 becomes 9.

ab=5 becomes 197.

pc- becomes 48.

pc=6 becomes 214.

ot=7 becomes 231.

In this example, the sum of these results is 1320. Unfortunately, the reindeer has stolen the page containing the expected verification number and is currently running around the facility with it excitedly.

Run the HASH algorithm on each step in the initialization sequence. What is the sum of the results? (The initialization sequence is one long line; be careful when copy-pasting it.)

---

Intereisting problem! It seems like we need to implement a new hashing algorithm — Holiday ASCII String Helper Algorithm!

Well, this algo will turn any string of characters into a single number in the range 0 to 255 by starting with a current value of 0. Then, for each character in the string starting from the beginning:

• Determine the ASCII code for the current character of the string.
• Increase the current value by the ASCII code you just determined.
• Set the current value to itself multiplied by 17.
• Set the current value to the remainder of dividing itself by 256.

Looks pretty straight forward! Let’s write some code? We will start with the base case first:

The code seems pretty simple to implement for now:

Let’s test our base case?

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_15/lens_library.py"
✅ test_process_sequence Passed

[Done] exited with code=0 in 0.067 seconds

Lets run this for our puzzle input while ensuring all of the sequence is just a 1 line string so we need to ignore new newline characters while parsing:

Let’s run this? This seems just suspiciously easy! 😅

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_15/lens_library.py"
❗️ Part One: XXXXX

[Done] exited with code=0 in 0.067 seconds

We have an answer, let’s try it on the puzzle page and…

✅

Boom! Easy. Let’s go to part 2, here’s our code till now, can’t be anymore efficient!

# Day 15: Lens Library

def holiday_helper(step):
    current_value = 0
    for ch in step:
        ascii_code = ord(ch)
        current_value += ascii_code
        current_value *= 17
        current_value %= 256

    return current_value

def process_sequence(sequence):
    sum = 0
    for step in sequence.split(","):
        sum += holiday_helper(step)

    return sum

def part_one():
    with open("day_15/input.txt") as f:
        sequence = f.read().strip()
    
    sum = process_sequence(sequence)
    print(f"❗️ Part One: {sum}")

def test_process_sequence():
    sequence = "rn=1,cm-,qp=3,cm=2,qp-,pc=4,ot=9,ab=5,pc-,pc=6,ot=7"
    sum = process_sequence(sequence)
    assert sum == 1320, f"Expected 1320, but got {sum}"
    print("✅ test_process_sequence Passed")

if __name__ == "__main__":
    test_process_sequence()
    part_one()

---

Part Two

You convince the reindeer to bring you the page; the page confirms that your HASH algorithm is working.

The book goes on to describe a series of 256 boxes numbered 0 through 255. The boxes are arranged in a line starting from the point where light enters the facility. The boxes have holes that allow light to pass from one box to the next all the way down the line.

+-----+ +-----+ +-----+
Light | Box | | Box | … | Box |
----------------------------------------->
| 0 | | 1 | … | 255 |
+-----+ +-----+ +-----+

Inside each box, there are several lens slots that will keep a lens correctly positioned to focus light passing through the box. The side of each box has a panel that opens to allow you to insert or remove lenses as necessary.

Along the wall running parallel to the boxes is a large library containing lenses organized by focal length ranging from 1 through 9. The reindeer also brings you a small handheld label printer.

The book goes on to explain how to perform each step in the initialization sequence, a process it calls the Holiday ASCII String Helper Manual Arrangement Procedure, or HASHMAP for short.

Each step begins with a sequence of letters that indicate the label of the lens on which the step operates. The result of running the HASH algorithm on the label indicates the correct box for that step.

The label will be immediately followed by a character that indicates the operation to perform: either an equals sign (=) or a dash (-).

If the operation character is a dash (-), go to the relevant box and remove the lens with the given label if it is present in the box. Then, move any remaining lenses as far forward in the box as they can go without changing their order, filling any space made by removing the indicated lens. (If no lens in that box has the given label, nothing happens.)

If the operation character is an equals sign (=), it will be followed by a number indicating the focal length of the lens that needs to go into the relevant box; be sure to use the label maker to mark the lens with the label given in the beginning of the step so you can find it later. There are two possible situations:

If there is already a lens in the box with the same label, replace the old lens with the new lens: remove the old lens and put the new lens in its place, not moving any other lenses in the box.

If there is not already a lens in the box with the same label, add the lens to the box immediately behind any lenses already in the box. Don’t move any of the other lenses when you do this. If there aren’t any lenses in the box, the new lens goes all the way to the front of the box.

Here is the contents of every box after each step in the example initialization sequence above:

After “rn=1”:
Box 0: [rn 1]

After “cm-”:
Box 0: [rn 1]

After “qp=3”:
Box 0: [rn 1]
Box 1: [qp 3]

After “cm=2”:
Box 0: [rn 1] [cm 2]
Box 1: [qp 3]

After “qp-”:
Box 0: [rn 1] [cm 2]

After “pc=4”:
Box 0: [rn 1] [cm 2]
Box 3: [pc 4]

After “ot=9”:
Box 0: [rn 1] [cm 2]
Box 3: [pc 4] [ot 9]

After “ab=5”:
Box 0: [rn 1] [cm 2]
Box 3: [pc 4] [ot 9] [ab 5]

After “pc-”:
Box 0: [rn 1] [cm 2]
Box 3: [ot 9] [ab 5]

After “pc=6”:
Box 0: [rn 1] [cm 2]
Box 3: [ot 9] [ab 5] [pc 6]

After “ot=7”:
Box 0: [rn 1] [cm 2]
Box 3: [ot 7] [ab 5] [pc 6]

All 256 boxes are always present; only the boxes that contain any lenses are shown here. Within each box, lenses are listed from front to back; each lens is shown as its label and focal length in square brackets.

To confirm that all of the lenses are installed correctly, add up the focusing power of all of the lenses. The focusing power of a single lens is the result of multiplying together:

One plus the box number of the lens in question.

The slot number of the lens within the box: 1 for the first lens, 2for the second lens, and so on.

The focal length of the lens.

At the end of the above example, the focusing power of each lens is as follows:

rn: 1 (box 0) * 1 (first slot) * 1 (focal length) = 1

cm: 1 (box 0) * 2 (second slot) * 2 (focal length) = 4

ot: 4 (box 3) * 1 (first slot) * 7 (focal length) = 28

ab: 4 (box 3) * 2 (second slot) * 5 (focal length) = 40

pc: 4 (box 3) * 3 (third slot) * 6 (focal length) = 72

So, the above example ends up with a total focusing power of 145.

With the help of an over-enthusiastic reindeer in a hard hat, follow the initialization sequence. What is the focusing power of the resulting lens configuration?

---

You convince the reindeer to bring you the page; the page confirms that your HASH algorithm is working.

Well, duh! Here we go, this puzzle is going to get super complex now…

So, the setup is something like this:

And we have a label printer!

Initialization sequence(or Holiday ASCII String Helper Manual Arrangement Procedure or H.A.S.H.M.A.P.) goes on something like this:

1. Each step begins with a sequence of letters that indicate the label of the lens on which the step operates.
   -> The result of running the HASH algorithm on the label indicates the correct box for that step.
2. The label will be immediately followed by a character that indicates the operation to perform: either an equals sign (=) or a dash (-).
3. If the operation character is a dash (-):
   * go to the relevant box and remove the lens with the given label if it is present in the box.
   * move any remaining lenses as far forward in the box as they can go without changing their order, filling any space made by removing the indicated lens.
4. If the operation character is an equals sign (=):
   * it will be followed by a number indicating the focal length of the lens that needs to go into the relevant box
   * be sure to use the label maker to mark the lens with the label given in the beginning of the step so you can find it later.

There are two possible situations:

• If there is already a lens in the box with the same label, replace the old lens with the new lens: remove the old lens and put the new lens in its place, not moving any other lenses in the box.

• If there is not already a lens in the box with the same label, add the lens to the box immediately behind any lenses already in the box. Don’t move any of the other lenses when you do this. If there aren’t any lenses in the box, the new lens goes all the way to the front of the box.

This is a mouthfull, let’s do it one by one!

First, we need a new parsing logic for each step of the sequence:

This should take care of the “Operation” nuance

Let’s setup some classes for Box and Lens so we can have object embedding for cleaner code:

Now, let’s implement some of the box operations for — and = !

Now, let’s implement our H.A.S.H.M.A.P function that will utilise our Box methods to do the processing:

I have added some logging for my own sanity!

Let’s run the test case with the help of our debugger, our final state of BOXES should look like this:

After "ot=7":
Box 0: [rn 1] [cm 2]
Box 3: [ot 7] [ab 5] [pc 6]

Indeed, it is! 🙌

Post this, all we need to do is, implement a sum function to give us our answer, i.e: focusing power of the resulting lens configuration

Let’s test our new base test case as given in the part 2:

And…

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_15/lens_library.py"
Lens: rn | ADDED | in box: 0
Lens: cm | NOT FOUND | in box: 0
Lens: qp | ADDED | in box: 1
Lens: cm | ADDED | in box: 0
Lens: qp | REMOVED | in box: 1
Lens: pc | ADDED | in box: 3
Lens: ot | ADDED | in box: 3
Lens: ab | ADDED | in box: 3
Lens: pc | REMOVED | in box: 3
Lens: pc | ADDED | in box: 3
Lens: ot | UPDATED | in box: 3
✅ test_hashmap Passed

[Done] exited with code=0 in 0.05 seconds

Beautiful! Let’s now run this for our puzzle input?

💡Remember to not run test_hashmap() before part_two() as it will modify the state of our global BOXES. 😅

I will fix that post verification!

Let’s remove the logging and just execute the part_two() :

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_15/lens_library.py"
❗️❗️ Focusing power of the resulting lens configuration: XXXXXX

[Done] exited with code=0 in 0.073 seconds

We got an answer in just sweet 0.073 seconds, let’s input this in our answer box…..and…. 💥

First try! 😎

Here’s our final optimized pythonic code with production level quality with inline comments!

Since I was able to do this one quickly, spent some time writing quality code! You will enjoy reading this!

# Day 15: Lens Library

from enum import Enum

class Operation(Enum):
    DASH = "-"
    EQUALS = "="

# Represents a step in the initialization sequence, parsing its components
class Step:
    def __init__(self, step):
        # Check if the step involves removing a lens (indicated by a dash)
        if Operation.DASH.value in step:
            self.label, _ = step.split(Operation.DASH.value)
            self.operation = Operation.DASH
            self.focal_length = None

        # Check if the step involves adding or updating a lens (indicated by an equals sign)
        elif Operation.EQUALS.value in step:
            self.label, focal_length = step.split(Operation.EQUALS.value)
            self.operation = Operation.EQUALS
            self.focal_length = int(focal_length)

        else:
            raise ValueError(f"Invalid step: {step}")

# Represents a lens with a label and focal length
class Lens:
    def __init__(self, label, focal_length):
        self.label = label
        self.focal_length = focal_length

    def __repr__(self):
        return f"[{self.label} {self.focal_length}]"

# Represents a box that can hold multiple lenses
class Box:
    def __init__(self, id):
        self.id = id
        self.lenses = []

    def find_lens(self, label):
        for lens in self.lenses:
            if lens.label == label:
                return lens
        return None

    def remove_lens(self, label):
        lens = self.find_lens(label)
        if lens:
            self.lenses.remove(lens)

    def add_or_update_lens(self, lens):
        existing_lens = self.find_lens(lens.label)
        if existing_lens:
            existing_lens.focal_length = lens.focal_length
        else:
            self.lenses.append(lens)

    def calc_focusing_power(self):
        return sum(
            (self.id + 1) * (idx + 1) * lens.focal_length
            for idx, lens in enumerate(self.lenses)
        )

# Represents the entire Lava Production Facility with its boxes
class LavaProductionFacility:
    def __init__(self):
        self.boxes = [Box(id) for id in range(256)]

    # H.A.S.H.M.A.P. = Holiday ASCII String Helper Manual Arrangement Procedure
    def holiday_ascii_string_helper_manual_arrangement_procedure(self, sequence_steps):
        for step in sequence_steps:
            step_obj = Step(step)
            box_id = self.holiday_ascii_string_helper(step_obj.label)
            box = self.boxes[box_id]

            if step_obj.operation == Operation.DASH:
                box.remove_lens(step_obj.label)
            elif step_obj.operation == Operation.EQUALS:
                lens = Lens(step_obj.label, step_obj.focal_length)
                box.add_or_update_lens(lens)

    def sum_focusing_power(self):
        return sum(box.calc_focusing_power() for box in self.boxes)

    @staticmethod
    # H.A.S.H. = Holiday ASCII String Helper
    def holiday_ascii_string_helper(step):
        current_value = 0
        for ch in step:
            current_value = (current_value + ord(ch)) * 17 % 256
        return current_value

    def get_sequence_hash(self, sequence):
        return sum(
            self.holiday_ascii_string_helper(step) for step in sequence.split(",")
        )

def part_one():
    with open("day_15/input.txt") as f:
        sequence = f.read().strip()

    facility = LavaProductionFacility()
    sum_hash = facility.get_sequence_hash(sequence)
    print(f"❗️ Part One: {sum_hash}")

def part_two():
    with open("day_15/input.txt") as f:
        sequence = f.read().strip()

    facility = LavaProductionFacility()
    facility.holiday_ascii_string_helper_manual_arrangement_procedure(
        sequence.split(",")
    )
    sum_focusing_power = facility.sum_focusing_power()
    print(
        f"❗️❗️ Focusing power of the resulting lens configuration: {sum_focusing_power}"
    )

def test_hashmap():
    sequence = "rn=1,cm-,qp=3,cm=2,qp-,pc=4,ot=9,ab=5,pc-,pc=6,ot=7"
    facility = LavaProductionFacility()
    facility.holiday_ascii_string_helper_manual_arrangement_procedure(
        sequence.split(",")
    )
    sum_focusing_power = facility.sum_focusing_power()
    assert sum_focusing_power == 145, f"Expected 145, but got {sum_focusing_power}"
    print("✅ test_hashmap Passed")

def test_get_sequence_hash():
    sequence = "rn=1,cm-,qp=3,cm=2,qp-,pc=4,ot=9,ab=5,pc-,pc=6,ot=7"
    facility = LavaProductionFacility()
    sum_hash = facility.get_sequence_hash(sequence)
    assert sum_hash == 1320, f"Expected 1320, but got {sum_hash}"
    print("✅ test_process_sequence Passed")

if __name__ == "__main__":
    test_get_sequence_hash()
    part_one()

    test_hashmap()
    part_two()

---

p.s: I am deliberating not adding answers here so you can actually spend some time trying to understand how we solved the problem!

Feel free to checkout code on my Github repo and try to set it up and run on your machine 👇

GitHub - jatinkrmalik/advent-of-code-2023: Well, here’s my attempt to solve all 25 problems of…
Well, here’s my attempt to solve all 25 problems of Advent of Code 2023 with Python! 🎄 - GitHub …github.com