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:
-
qpHASHes to 1 -
Box 1doesn't haveqplens - 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:
-
cmHASHes to 0 - Box 0 doesn't have
cmlens - It's added to the end of the Box
What should happen next?
After "qp-":
Box 0: [rn 1] [cm 2]
That makes sense:
-
qpHASHes to 1 - Box 1 has a
qplens - So it is removed
What should happen next?
After "pc=4":
Box 0: [rn 1] [cm 2]
Box 3: [pc 4]
That makes sense:
-
pcHASHes to 3 - Box 3 doesn't have
pclens - 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!
Top comments (0)