Advent of Code 2023 Day 15

Day 15: Lens Library

https://adventofcode.com/2023/day/15

You arrive at the facility the mirrors are pointing at.

Inside, some more calibration work is needed.

Today’s input is a bunch of instructions.

An example input looks like this:

input.txt

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

The line with instructions is separated by commas.

Part 1

A hashing algorithm turns every instruction into a number.

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.

The question asks for the sum of all instruction hashes.

Helpers

The hash function!

fn hash(s: &str) -> u32 {
    s.bytes().fold(0, |mut acc, byte| {
        acc += byte as u32;
        acc *= 17;
        acc % 256
    })
}

By using some properties of modular arithmetic, and the fact that a 8 bytes can store 256 decimal numbers (0 to 255).

// https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-addition-and-subtraction
// (A + B) mod C = (A mod C + B mod C) mod C
// https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-multiplication
// (A * B) mod C = (A mod C * B mod C) mod C
// combining those two rules:
// ((A + B) * C) mod D = (((A + B) mod D) * C) mod D
fn hash(s: &str) -> u8 {
    s.bytes()
        .fold(0, |acc, byte| acc.wrapping_add(byte).wrapping_mul(17))
}

Code

day_15.rs

fn hash(s: &str) -> u8 {
    s.bytes()
        .fold(0, |acc, byte| acc.wrapping_add(byte).wrapping_mul(17))
}

pub fn part_1(input: &str) -> u32 {
    input.trim().split(',').map(|s| hash(s) as u32).sum()
}

Part 2

Now the question tells us what each instruction means.

Each instruction starts with a label (the letters).

The labels are for lenses.

There are 2 types of instruction:

An instruction ending in a minus - means “remove the lens with this label from its box”.
An instructing with an equals sign = means “update the box with this lens”

To find the box for a label, apply the hashing function from part1 to it. eg. The rn=1 instruction has a label of rn, hashing that gives 0. So this instruction tells us to update box 0.

There are 256 boxes in total, this maps perfectly to what the hash function from part1 can return!

Now, the specifics of both instructions.

The remove instruction:
- If the label you are searching for is not inside its box, do nothing.
- If the label you are searching for is present, remove it and shift all other lenses forward.
The add instruction:
- If a lens with the label you are searching for is present, update its focal length (the number right of the = in the instruction).
- If a lens with the label you are searching for is not present, add the lens to the end of the box.

The question asks for the total focusing power after all instructions are applied.

The focusing power of a single lens is the result of multiplying together:

One plus the box number of the lens in question. (boxes start at 0!)
The slot number of the lens within the box: 1 for the first lens, 2 for the second lens, and so on. (slots start 1!)
The focal length of the lens.

Helpers

I represented each instruction as an enum.

enum Instruction<'a> {
    Remove(&'a str),
    Add(Lens<'a>),
}

A Lens here:

struct Lens<'a> {
    label: &'a str,
    focal: u8,
}

Again, don’t mind the 'a stuff, those are Rust lifetimes that let me use the labels from the input.

Then I created a way to turn a piece of the input into a real Instruction.

impl<'a> Instruction<'a> {
    fn new(s: &'a str) -> Self {
        if let Some(label) = s.strip_suffix('-') {
            Self::Remove(label)
        } else {
            let (label, focal) = s.split_once('=').unwrap();
            let focal = focal.parse().unwrap();
            let lens = Lens { label, focal };
            Self::Add(lens)
        }
    }
}

I loop over the input, turn each instruction into an Instruction and apply it.

I represented the 256 boxes as an array. Each box can hold several lenses, so each box is represented as a list itself.

For every instruction, I calculate the hash of its label.

Then I apply the instruction according to the rules described in the problem statement.

At the end, I loop through all boxes and calculate the sum of the focusing power. The sum of all those sums is what the question is asking for.

Code

day_15.rs

enum Instruction<'a> {
    Remove(&'a str),
    Add(Lens<'a>),
}

impl<'a> Instruction<'a> {
    fn new(s: &'a str) -> Self {
        if let Some(label) = s.strip_suffix('-') {
            Self::Remove(label)
        } else {
            let (label, focal) = s.split_once('=').unwrap();
            let focal = focal.parse().unwrap();
            let lens = Lens { label, focal };
            Self::Add(lens)
        }
    }
}

struct Lens<'a> {
    label: &'a str,
    focal: u8,
}

fn hash(s: &str) -> u8 {
    s.bytes()
        .fold(0, |acc, byte| acc.wrapping_add(byte).wrapping_mul(17))
}

pub fn part_2(input: &str) -> usize {
    const BOX: Vec<Lens> = Vec::new();
    let mut boxes = [BOX; 256];

    for instr in input.trim_end().split(',').map(Instruction::new) {
        match instr {
            Instruction::Remove(label) => {
                let hash = hash(label);
                boxes[hash as usize].retain(|item| item.label != label);
            }
            Instruction::Add(lens) => {
                let hash = hash(lens.label);
                let lenses = &mut boxes[hash as usize];
                if let Some(old) = lenses.iter_mut().find(|item| lens.label == item.label) {
                    // update focal length of lens with this label
                    old.focal = lens.focal;
                } else {
                    // add lens to end of box
                    lenses.push(lens);
                }
            }
        }
    }

    boxes
        .into_iter()
        .enumerate()
        .map(|(box_idx, lenses)| {
            let box_focusing_power: usize = lenses
                .into_iter()
                .enumerate()
                .map(|(lens_idx, lens)| (box_idx + 1) * (lens_idx + 1) * lens.focal as usize)
                .sum();
            box_focusing_power
        })
        .sum()
}

Final code

day_15.rs

1enum Instruction<'a> {
2    Remove(&'a str),
3    Add(Lens<'a>),
4}
5
6impl<'a> Instruction<'a> {
7    fn new(s: &'a str) -> Self {
8        if let Some(label) = s.strip_suffix('-') {
9            Self::Remove(label)
10        } else {
11            let (label, focal) = s.split_once('=').unwrap();
12            let focal = focal.parse().unwrap();
13            let lens = Lens { label, focal };
14            Self::Add(lens)
15        }
16    }
17}
18struct Lens<'a> {
19    label: &'a str,
20    focal: u8,
21}
22
23fn hash(s: &str) -> u8 {
24    s.bytes()
25        .fold(0, |acc, byte| acc.wrapping_add(byte).wrapping_mul(17))
26}
27
28pub fn part_1(input: &str) -> u32 {
29    input.trim().split(',').map(|s| hash(s) as u32).sum()
30}
31
32pub fn part_2(input: &str) -> usize {
33    const BOX: Vec<Lens> = Vec::new();
34    let mut boxes = [BOX; 256];
35
36    for instr in input.trim_end().split(',').map(Instruction::new) {
37        match instr {
38            Instruction::Remove(label) => {
39                let hash = hash(label);
40                boxes[hash as usize].retain(|item| item.label != label);
41            }
42            Instruction::Add(lens) => {
43                let hash = hash(lens.label);
44                let lenses = &mut boxes[hash as usize];
45                if let Some(old) = lenses.iter_mut().find(|item| lens.label == item.label) {
46                    // update focal length of lens with this label
47                    old.focal = lens.focal;
48                } else {
49                    // add lens to end of box
50                    lenses.push(lens);
51                }
52            }
53        }
54    }
55
56    boxes
57        .into_iter()
58        .enumerate()
59        .map(|(box_idx, lenses)| {
60            let box_focusing_power: usize = lenses
61                .into_iter()
62                .enumerate()
63                .map(|(lens_idx, lens)| (box_idx + 1) * (lens_idx + 1) * lens.focal as usize)
64                .sum();
65            box_focusing_power
66        })
67        .sum()
68}

Date

Last update

By

Tagged

Part of series

Older post

Newer post

Advent of Code 2023 Day 15

Day 15: Lens Library

Part 1

Helpers

Code

Part 2

Helpers

Code

Final code