Advent of Code 2023 - Day 15: Lens Library

Question

Part 1:

The task involves initializing the Lava Production Facility using an initialization sequence. The sequence consists of steps, each requiring the application of the Holiday ASCII String Helper algorithm (HASH). The HASH algorithm involves turning a string into a single number in the range 0 to 255. The sum of the results of running the HASH algorithm on each step in the initialization sequence is the solution.

The HASH algorithm is a way to turn any string 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.

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.

#!/usr/bin/env python3

from pathlib import Path
from typing import Iterable

import typer


def hash_line(line: str) -> int:
    current = 0

    for c in line:
        current = (current + ord(c)) * 17 % 256
    return current


def hash(line: str) -> int:
    return sum(hash_line(pattern) for pattern in line.strip().split(","))


def total_sum(lines: Iterable[str]) -> int:
    return sum(map(hash, lines))


def main(initialization_sequence: Path) -> None:
    """Solves Part 1 of Day 15 Advent of Code.                                   
    See: https://adventofcode.com/2023/day/15""" 
    with open(initialization_sequence) as f:
        print(total_sum(f))


if __name__ == "__main__":
    typer.run(main)

Part 2:

In Part Two, the task extends to configuring lenses in a series of 256 boxes. The initialization sequence specifies operations for inserting or removing lenses from specific boxes. Each lens operation includes a label, an operation character (= or -), and, if applicable, the focal length of the lens. The focusing power of a lens is calculated based on its position in the box, box number, and focal length. The goal is to follow the entire initialization sequence, perform the specified lens operations, and determine the total focusing power of the resulting lens configuration.

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, 2 for 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.

#!/usr/bin/env python3

from pathlib import Path
from typing import Iterable

import typer

TOTAL_BOXES = 256


def hash_csv(line: str) -> int:
    current = 0

    for c in line:
        current = (current + ord(c)) * 17 % 256
    return current


def remove_slot(csv: str, boxes: list[list[list[str | int]]]) -> None:
    # label-
    label, *_ = csv.split("-")
    box_idx = hash_csv(label)

    # Loop over a copy to avoid modifying the list whilst iterating over it.
    for slot in boxes[box_idx][:]:
        if label == slot[0]:
            boxes[box_idx].remove(slot)
            break


def add_slot(csv: str, boxes: list[list[list[str | int]]]) -> None:
    # label=focal_length
    label, focal_len = csv.split("=")
    box_idx = hash_csv(label)

    # If the label already exists, update it. Else, append it to the end.
    for slot in boxes[box_idx]:
        if label == slot[0]:
            slot[1] = int(focal_len)
            return

    boxes[box_idx].append([label, int(focal_len)])


def build_boxes(line: str, boxes: list[list[list[str | int]]]) -> None:
    for csv in line.strip().split(","):
        add_slot(csv, boxes) if "=" in csv else remove_slot(csv, boxes)


def calculate_focusing_pow(boxes: list[list[tuple[str, int]]]) -> int:
    total = 0
    for box_idx, box in enumerate(boxes, 1):
        total += sum(
            box_idx * slot_idx * slot[1] for slot_idx, slot in enumerate(box, 1)
        )
    return total


def line_focusing_pow(line: str) -> int:
    boxes = [[] for i in range(TOTAL_BOXES)]
    build_boxes(line, boxes)
    return calculate_focusing_pow(boxes)


def total_focusing_pow(lines: Iterable[str]) -> int:
    return sum(map(line_focusing_pow, lines))


def main(initialization_sequence: Path) -> None:
    """Solves Part 2 of Day 15 Advent of Code.                                   
    See: https://adventofcode.com/2023/day/15""" 
    with open(initialization_sequence) as f:
        print(total_focusing_pow(f))


if __name__ == "__main__":
    typer.run(main)

Review Request:

General coding comments, style, etc. What are some possible simplifications? What would you do differently?

I don't have time currently to provide an actual answer but for now I will say that you should not create a function that mirrors a built-in function, such as hash. If you call any other function that relies on the hash function, you will have a broken program on your hands. — Booboo
– Booboo, Commented Jan 1, 2024 at 22:54

Booboo · Accepted Answer · 2024-01-02 16:24:59Z

Part 1

Your code produces the correct answers, so well done! Consequently, I will be commenting mostly on style and choice of names for variables and functions.

As I mentioned in a comment to your post, you should avoid assigning names to variables and (especially) functions that are the same as built-in functions. First, when somebody sees a call to hash they may erroneously assume what that function is doing. Moreover, be redefining a built-in function, the potential for breaking existing code that uses that function exists. I would, therefore, rename function hash to hash_step as follows:

def hash_step(step: str) -> int:
    h = 0
    for c in step:
        h = (h + ord(c)) * 17 % 256

    return h

The input consists of a sequence of comma-delimited "steps" where a single step is, for example, 'gp=3'. This is not a "line", so the function name I have chosen is hash_step and its argument is step because the function computes a hash for a single step. I have also modified loop variable current to h (for "hash") because "current" asks the question "current what?". Using a name such as current_hash would have also been fine. Finally, I don't want any empty lines between the initialization of the hash (i.e. h = 0) and the loop that uses it since the two are closely tied together.

Similarly, function name total_sum asks the question "sum of what?" So I would rename this to total_hash. I see no other changes required. But let me pose another possibility depending on how literally you want to take the program description in implementing your code. The description states:

The initialization sequence (your puzzle input) is a comma-separated list of steps to start the Lava Production Facility. Ignore newline characters when parsing the initialization sequence.

The way I interpret this description is that function total_hash is really the function to be called to solve the problem and it is passed the initialization sequence, which is a comma-separated list of steps, i.e. a string. That this string is coming from an input file is just one possibility. According to this way of thinking the docstring describing what the function does should be moved to the actual function that is doing it! So we then have:

#!/usr/bin/env python3

from pathlib import Path
from typing import Iterable, Union

import typer


def hash_step(step: str) -> int:
    h = 0
    for c in step:
        h = (h + ord(c)) * 17 % 256

    return h


def part1(initialization_sequence: str) -> int:
    """Solves Part 1 of Day 15 Advent of Code.
        See: https://adventofcode.com/2023/day/15

    We are passed a comma-delimited sequence of steps for which
    we must compute the sum of their hashes. The input may contain
    newline characters that are to be ignored."""

    # Ignore any newlines:
    initialization_sequence = initialization_sequence.replace('\n', '')

    return sum(
        hash_step(step)
            for step in initialization_sequence.split(',')
    )



if __name__ == "__main__":
    def main(initialization_sequence_path: Path) -> None:
        with open(initialization_sequence_path) as f:
            print(part1(f.read()))

    typer.run(main)

Part 2

Comments I made about using safer and more descriptive function and variable names apply here.

What Is The Optimal Functional Decomposition?

I don't know if there is an optimal; it's a balance between maintainability and readability, which are not always the same thing. When performing functional decomposition for solving a programming task one has determine how fine-grained the functions should be. If code is used repeatedly it should clearly be a candidate for standing alone in its own function (for maintainability). Other than that, I would perform a functional decomposition so that the resulting code is is the clearest possible even if it means having larger functions. I have included my code version at the end as an example of not creating functions that are too fine-grained. For example, I could have created individual functions for add_slot or remove_slot, but they would have been "one-liners". In the end that would have made it harder to see the forest for all the trees. Would your code gain in readability without loosing maintainability if you combined some of your functions? This is for you to answer.

Efficiency

In function remove_slot you are iterating a copy of the list you are potentially removing an element from. But since you immediately stop iterating the list as soon as an element is removed, there was no need in iterating a copy. You also have:

label, *_ = csv.split("-")

But csv is terminated by the minus sign. Simpler (and better) would be:

label = csv[:-1]

Your boxes variable is a list of lists with each sub-list representing the contents of a box. Consequently, your remove_slot function has to perform a linear search to determine whether a label exists and then when you call remove the list has to be searched again and elements moved. Since Python 3.6 insertion order is maintained in a dictionary. Testing whether a label exists is an O(1) operation if that label is a key of a dictionary and then deleting the key is also an O(1) operation. Finally, when you iterate the keys (labels) and values (lenses) of the dictionary you will be doing so in key-insertion order.

Consider using a regular expression for parsing a "step":

([a-z]+)([=-])([0-9]*)

([a-z]+) - Capture group 1 consists of one or more lower case letters.
([=-]) - Followed by capture group 2 consisting of either '=' or '-'.
([0-9]*) - Followed by optional digits (not present when capture group2 is '-').

Then you can use method re.finditer over the entire input. Commas and newline characters will never be matched.

My Implementation

The following code incorporates my suggestions:

#!/usr/bin/env python3

import re

def hash_label(label: str) -> int:
    box = 0
    for c in label:
        box = (box + ord(c)) * 17 % 256

    return box

def part2(initialization_sequence: str) -> int:
    """Solves Part 2 of Day 15 Advent of Code.
        See: https://adventofcode.com/2023/day/15"""

    boxes = [{} for _ in range(256)]

    rex = re.compile(r'([a-z]+)([=-])([0-9]*)')
    for m in rex.finditer(initialization_sequence):
        label, action, lens = m.groups()
        box = boxes[hash_label(label)]
        if action == '-':
            if label in box:
                del box[label]
        else:
            box[label] = int(lens)

    return sum (
        box_number * slot_number * lens
            for box_number, box in enumerate(boxes, start=1)
                for slot_number, lens in enumerate(box.values(), start=1)
    )


if __name__ == "__main__":
    with open('test.txt') as f:
        print(part2(f.read()))

vnp · Accepted Answer · 2024-01-01 22:45:32Z

1

Part 1 is fairly simple; I trust that it worked correctly, so no comments here.

Part 2 is a bit more tricky. You diligently followed the instructions. In contest programming it usually means that your algorithm is suboptimal. Advent of Code does not specify the constraints, so prepare for the worst.

In your implementation the time complexity of add_slot and remove_slot is linear to a box population, which in turn is linear to the number of queries to that box. It means that the time complexity of build_box is quadratic to the number of queries.

Instead of a list of tuples, consider to model the box as a tuple, made by a dictionary label: position, and a topmost position. Adding a slot increments the topmost position. Only after all queries are served, collapse the dictionary into a list sorted by position. This will give you a linearithmic complexity.

edited Jan 1, 2024 at 22:45

answered Jan 1, 2024 at 21:31

vnp

58.7k4 gold badges55 silver badges144 bronze badges

\$\begingroup\$ If I understand your suggestion you are saying that a box is a dictionary whose key is the label and whose values are tuples, e.g. (lense, position). After all insertion/deletions are made you then sort the tuples by position. But ever since Python 3.6 dictionaries maintain insertion order (or you could use an OrderedDict) and there is no need to include a position or to sort anything. \$\endgroup\$

Booboo
– Booboo

2024-01-02 16:48:54 +00:00
Commented Jan 2, 2024 at 16:48
\$\begingroup\$ @Booboo This is worth considering. As I understand. ``OrderedDict` has a logarithmic time complexity, so there is no real gain. \$\endgroup\$

vnp
– vnp

2024-01-02 17:08:47 +00:00
Commented Jan 2, 2024 at 17:08
\$\begingroup\$ All I know is that since Python 3.6 all dictionaries now maintain insertion order. I question that they would have done this if it increased the time complexity in any substantial way, especially since there is already an OrderDict that could be used for that purpose. Anyway, if you are already using a dictionary to hold the contents of a box (you did not reply either way and it wasn't clear to me from your description because I could not parse "consider to model the box as a tuple, made by a dictionary label: position"), you might as well take advantage of its insertion order. \$\endgroup\$

Booboo
– Booboo

2024-01-02 17:49:34 +00:00
Commented Jan 2, 2024 at 17:49
\$\begingroup\$ I also meant one could use an OrderedDict if one was running < Python 3.6. \$\endgroup\$

Booboo
– Booboo

2024-01-02 17:52:11 +00:00
Commented Jan 2, 2024 at 17:52

Add a comment |

Stack Exchange Network

Advent of Code 2023 - Day 15: Lens Library

Part 1:

Part 2:

Review Request:

2 Answers 2

Part 1

Part 2

What Is The Optimal Functional Decomposition?

Efficiency

My Implementation

You must log in to answer this question.

Hot Network Questions

Advent of Code 2023 - Day 15: Lens Library

Part 1:

Part 2:

Review Request:

2 Answers 2

Part 1

Part 2

What Is The Optimal Functional Decomposition?

Efficiency

My Implementation

You must log in to answer this question.

Related

Hot Network Questions