Advent of Code 2023 Day 15

Part 1

Seems pretty cut and dry

start with a current value of 0

let value = 0

for each character in the string starting from the beginning

let str = input

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

Determine the ASCII code for the current character of the string

let ascii = char.charCodeAt(0)

Increase the current value by the ASCII code you just determined

value += ascii

Set the current value to itself multiplied by 17

value *= 17

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

value = value % 256

Altogether, inside a reduce():

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:

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?

[
 [ , , ],
 [ , , ],
]

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:

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

if (step.includes('=')) {
  let fLength = step.match(/\d/)[0]
} else if (step.includes('-')) {

}

After some more 'hacking away', my nested-conditional looks like this:

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.

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:

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!