Advent of Code 2022 Day 3
Part 1
- Divide (in half) and conquer
- Setting my priorities
- Split, Walk and Sum
- My full algorithm in JavaScript
Divide (in half) and conquer
- Slice each string in half
- Use the first half as a control
- Check only as many characters as needed
- Until the second half contains the current character
For example:
ttgJtRGJQctTZtZT
Cut in half gets:
ttgJtRGJ
QctTZtZT
Starting with the first half's first character:
*
ttgJtRGJ
Got any 't's?
QctTZtZT
*
Same-type identified!
Another example:
vJrwpWtwJgWrhcsFMMfFFhFp
Cut in half:
vJrwpWtwJgWr
hcsFMMfFFhFp
Starting with the first half's first character:
*
vJrwpWtwJgWr
Got any 'v's?
hcsFMMfFFhFp
Moving to the next character:
*
vJrwpWtwJgWr
Got any 'J's?
hcsFMMfFFhFp
Skipping ahead to the first same character:
*
vJrwpWtwJgWr
Got any 'p's?
hcsFMMfFFhFp
*
Same-type identified!
Setting my priorities
-
a - z
are1 - 26
-
A - Z
are27 - 52
Sure, I could manually create, say:
- A dictionary mapping letter to number
- Array with each letter occupying the appropriate index
But I want to do this programmatically!
Thankfully, I can use character codes!
Some examples:
-
A
is 65 -
a
is 97
Going from string to number in JavaScript:
'A'.charCodeAt()
Going from number to string in JavaScript:
String.fromCharCode(65)
Creating an array with slots for one alphabet casing:
new Array(26)
Leveraging each slot's index to populate items with letters:
new Array(26)
.fill(null)
.map(
// Uppercase
(,i) => String.fromCharCode(i + 65)
)
Generating both alphabets and merging into a single array:
new Array(26)
.fill(null)
.map(
(,i) => String.fromCharCode(i + 65 + 32)
)
.concat(
new Array(26)
.fill(null)
.map(
(,i) => String.fromCharCode(i + 65)
)
)
My array is 0-based. I'll need to account for that by adding one in my main algorithm.
Split, Walk and Sum
Split
I need to extract two equal length substrings from each string:
let [s1, s2] = [
sack.slice(0, sack.length / 2),
sack.slice(sack.length / 2)
]
Walk
I need to identify the single duplicated letter, checking only as many letters as needed:
let i = 0
let char = null
while (char == null) {
char = s2.includes(s1[i]) ? s1[i] : null
i++
}
Sum
I need to accumulate a total score derived from the priority amounts of each identified letter:
let priorities = ['a','b','c',]
.reduce((types, sack) => {
// Split
// Walk
return types += priorities.indexOf(char) + 1
}, 0)
My full algorithm in JavaScript
const priorities = new Array(26)
.fill(null)
.map(
(,i) => String.fromCharCode(i + 65 + 32)
)
.concat(
new Array(26)
.fill(null)
.map(
(,i) => String.fromCharCode(i + 65)
)
)
return input
.split('\n')
.reduce((types, sack) => {
let [s1, s2] = [
sack.slice(0, sack.length / 2),
sack.slice(sack.length / 2)
]
let i = 0
let char = null
while (char == null) {
char = s2.includes(s1[i]) ? s1[i] : null
i++
}
return types += priorities.indexOf(char) + 1
}, 0)
Part 2
-
reduce()
is out? Ohfor
Pete's sake! - My full algorithm in JavaScript
reduce()
is out? Oh for
Pete's sake!
I need to review every three lines in a batch:
for (let s = 0; s < sacks.length; s += 3) { }
I need to walk the first of three lines and check each of the other lines for a matching character:
let i = 0
let char = null
while (char == null) {
char = sacks[s + 1].includes(sacks[s][i])
&& sacks[s + 2].includes(sacks[s][i])
? sacks[s][i] : null
i++
}
I need to track a total and increment it with each group's priority amount:
let total = 0
// Inside the loop
total += priorities.indexOf(char) + 1
My full algorithm in JavaScript
() => {
let total = 0
let sacks = input.split('\n')
for (let s = 0; s < sacks.length; s += 3) {
let i = 0
let char = null
while (char == null) {
char = sacks[s + 1].includes(sacks[s][i])
&& sacks[s + 2].includes(sacks[s][i])
? sacks[s][i] : null
i++
}
total += priorities.indexOf(char) + 1
}
return total
}
I did it!!
- I solved both parts!
- I scratched my head once during Part 1 because I was unknowingly chopping off the first letter of the second sack!
- I reused most of my code from Part 1 in Part 2!
Lots of fun with strings and arrays today!
Top comments (0)