Lens Library
Tags: adventofcode, algorithms, javascript, programming
Published: 2024-01-31 00:42:10

## [Advent of Code 2023 Day 15](https://adventofcode.com/2023/day/15)

### Part 1

#### Seems pretty cut and dry
> start with a current value of 0

```js
let value = 0
```

> for each character in the string starting from the beginning

```js
let str = input

input.forEach(char => {...})
```

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

```js
let ascii = char.charCodeAt(0)
```

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

```js
value += ascii
```

> Set the current value to itself multiplied by 17

```js
value *= 17
```

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

```js
value = value % 256
```

Altogether, inside a `reduce()`:
```js
input.split('').reduce((value, char) => {
  let ascii = char.charCodeAt(0)
  value += ascii
  value *= 17
  value = value % 256
  return value
}, 0)
```

Does it generate the correct answer for `HASH`?
Yes! Yes it does.

That was a single string.

The next example offers something more akin to the puzzle input:
> a comma-separated list of steps

Sounds like I'll need a nested `reduce()`.

Here's my updated algorithm:
```js
input.split(',').reduce(
  (value, step) => {
    stepValue = step.split('').reduce(
      (value, char) => {
        let ascii = char.charCodeAt(0)
        value += ascii
        value *= 17
        value = value % 256
        return value
      }, 0
    )
    return value += stepValue
  }, 0
)
```

Does it generate the correct answer for the second example?
Yes! Yes it does.

Finally, does it generate the correct answer for my puzzle input?
Yes! Yes it does!!!

How hard could Part 2 be...?

### Part 2

#### A *lot* harder
Hooouuuuuweeeee!

This. Is. Complicated.

I'll need to read through all this a few times.

#### Trying to comprehend
> 256 boxes numbered 0 through 255

That sounds like an ordered list, or an `Array` in `JavaScript`.

> Inside each box, there are several lens slots

So, a 2D array?
```js
[
 [ , , ],
 [ , , ],
]
```

> keep a lens correctly positioned...insert or remove lenses as necessary

Throughout the program's run, array items will be added, deleted and moved around in a very particular order, it seems.

> lenses organized by focal length ranging from 1 through 9

Determine which box. Determine which lens. Grab that lens. Allocate to a slot in that box. Position it just right. Repeat.

Maybe?

> `HASHMAP`

An ordered collection of key-value pairs.

In `JavaScript`, this appears to be implemented as `Map`, which is a more rigid and secure version of an `Object`.

> 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.

For example:
```
rn=1
```

The sequence of letters is `rn`.

Running my HASH algorithm produces the value `0`.

So, the correct box for this step is `box 0`.

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

In the `rn=1` example, that character is an equals sign (=).

> [For equals signs] it will be followed by a number indicating the focal length of the lens that needs to go into the relevant box

So, the correct focal length of the lens that goes into `box 0` is `1`.

> 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

So, don't just add `1` into `box 0`; add `{label: rn, length: 1}` into `box 0`.

> If there aren't any lenses in the box, the new lens goes all the way to the front of the box

That makes sense.

And if there are already lenses in the box?
- If the same lens is in the box, update it
- Otherwise, add it at the end of the list of lenses

Hmm, maybe my nested items (representing the slots) should be Arrays of Objects or Maps. That way I can safely `slice`, `splice`, `shift`, `push`, etc.

> All 256 boxes are always present

Ok, so I'll need to initialize a 256-item data structure that's ready to insert lenses in the appropriate slots.

One that I can access the box number:
- An Array, where the index is the box number
- A Map, where the key is the box number

I'll attempt to understand and calculate `focusing power` later.

Before that, I need to walk through the example and confirm I understand all of what I wrote above.

#### Working through the example
The input:
```
rn=1,cm-,qp=3,cm=2,qp-,pc=4,ot=9,ab=5,pc-,pc=6,ot=7
```

As steps:
```
rn=1
cm-
qp=3
cm=2
qp-
pc=4
ot=9
ab=5
pc-
pc=6
ot=7
```

First step:
```
Run HASH on rn
=> Box 0

equals sign
=> focal length = 1

Check Box 0 for rn
=> Nothing

Add [rn 1] at front of Box 0
```

Resulting in this:
```
After "rn=1":
Box 0: [rn 1]
```

Check!

Second step:
```
Run HASH on cm
=> Box 0

dash sign
=> remove lens cm if it exists

Check Box 0 for cm
=> Nothing
```

Resulting in this:
```
After "cm-":
Box 0: [rn 1]
```

Check!

What should happen next?
```
After "qp=3":
Box 0: [rn 1]
Box 1: [qp 3]
```

That makes sense:
- `qp` HASHes to 1
- `Box 1` doesn't have `qp` lens
- It's added at the front with focal length `3`

What should happen next?
```
After "cm=2":
Box 0: [rn 1] [cm 2]
Box 1: [qp 3]
```

That makes sense:
- `cm` HASHes to 0
- Box 0 doesn't have `cm` lens
- It's added to the end of the Box

What should happen next?
```
After "qp-":
Box 0: [rn 1] [cm 2]
```

That makes sense:
- `qp` HASHes to 1
- Box 1 has a `qp` lens
- So it is removed

What should happen next?
```
After "pc=4":
Box 0: [rn 1] [cm 2]
Box 3: [pc 4]
```

That makes sense:
- `pc` HASHes to 3
- Box 3 doesn't have `pc` lens
- It's added to the end of the Box

Next, lens `ot` is added to the end Box 3
```
After "ot=9":
Box 0: [rn 1] [cm 2]
Box 3: [pc 4] [ot 9]
```

Next, lens `ab` is added to the end of Box 3
```
After "ab=5":
Box 0: [rn 1] [cm 2]
Box 3: [pc 4] [ot 9] [ab 5]
```

Next, lens `pc` is removed from Box 3
```
After "pc-":
Box 0: [rn 1] [cm 2]
Box 3: [ot 9] [ab 5]
```

Next, lens `pc` is added to the end of Box 3
```
After "pc=6":
Box 0: [rn 1] [cm 2]
Box 3: [ot 9] [ab 5] [pc 6]
```

Lastly, lens `ot`'s focus length is updated to `7`
```
After "ot=7":
Box 0: [rn 1] [cm 2]
Box 3: [ot 7] [ab 5] [pc 6]
```

Wow. I think I get it.

I just hope all this talk of exact positioning is merely the author over-articulating how ordered lists work.

Because I'm pretty sure that `splice()` will work great for me when I need to remove lenses.

Time to code this up!

#### Writing my Part 2 algorithm
Some changes I had to make to my Part 1 algorithm include:
- Accumulate an array of arrays
- Only run HASH on the letter characters in the step's string
- Save those letters as the lens' label

At this point, my algorithm displays the correct box numbers for the example input:
```js
input.split(',').reduce((boxes, step) => {
  let label = step.match(/\w+/)[0]
  let boxIndex = label
    .split('').reduce(
      (value, char) => {
      let ascii = char.charCodeAt(0)
      value += ascii
      value *= 17
      value = value % 256
      return value
    }, 0
  )
  return boxes
}, new Array(256).fill(null).map(el => new Array()))
```

Next, the beginning of accounting for `=` and `-`:
```js
if (step.includes('=')) {
  let fLength = step.match(/\d/)[0]
} else if (step.includes('-')) {
  
}
```

After some more 'hacking away', my nested-conditional looks like this:
```js
if (step.includes('=')) {
  let match = boxes[boxIndex]
    .findIndex(el => el.label == label)
  let fLength = step.match(/\d/)[0]
  if (match !== -1) {
    boxes[boxIndex][match].fl = fLength
  } else {
    boxes[boxIndex].push(
      { label: label, fl: fLength }
    )
  }
} else if (step.includes('-')) {
  
}
```

Printing the first three boxes when the step has an equals sign displays states of the boxes that seem correct.

So, I've got confidence this code works as intended for any step including an `=`.

Now, for the `-` condition.

```js
else if (step.includes('-')) {
  let match = boxes[boxIndex]
    .findIndex(el => el.label == label)
  if (match !== -1) {
    boxes[boxIndex].splice(match, 1)
  }
}
```

I wasn't seeing anything in Box 3.

I checked all my code.

It seemed to check out.

Then I realized...

...my `slice()` statement to only display the first few boxes was only showing me Boxes 0-2.

Ugh!

When I updated it to show Boxes 0-3 I saw exactly what I expected.

Phew!

I think I feel safe enough to move on to calculating `focusing power`.

#### Calculating `focusing power`
It looks like I'll need to iterate through each lens.

They are stored as objects nested in each of my 256 arrays.

Information I need to have so I can multiply them together:
> One plus the box number of the lens in question

I should have access to the box number while iterating.

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

That's just the index of each nested object. I'll have that for sure.

> The focal length of the lens

That's a property of the object. I'll have that, too.

Then I just multiply them together, huh? Cool!

This should be easy!......

#### Programmatically calculating `focusing power`
Aside from mistyping a value instead of a property name, this was the easiest part:
```js
boxes.reduce((fPower, box, index) => {
  return fPower += box.reduce((total, lens, i) => {
    return total += ((index + 1) * (i + 1) * lens.fl)
  }, 0)
}, 0)
```

It generated the correct answer for the example input.

Fingers crossed it generates the correct answer for my puzzle input!

...

Woohoo!!!

That second part was quite the tour de force of programming.

I was expecting something about my algorithm to be missing either an edge case or some clear part of the instructions.

Thankfully, no tricks here!

Onward, to Day 16!