Advent of Code 2016 Day 4
Part 1
- Bring on the gauntlet!
- A simple
regex
to get letters and numbers - Preparing the extracted parts
- Tallying each letter's occurrence in the string
- The trickiest part: sorting the letters correctly
- Finishing my working algorithm
- Testing and celebrating
Bring on the gauntlet!
An outline of my tasks ahead:
- Start with multi-line input as usual
- Reduce to a sum, as is often the case
- Extract the letters and numbers
- Reduce a string to a dictionary of each letter's counts
- Sort the keys by number and alphabetical order
- Keep only the first five keys
- Compare to a string
- If both are equal, add to the sum, otherwise add 0
A simple regex
to get letters and numbers
From this string:
aaaaa-bbb-z-y-x-123[abxyz]
I need these:
aaaaa bbb z y x 123 abxyz
To get them, I just need this:
/\w+/g
-
\w
matches any word, digit or whitespace -
+
matches 1 or more
In essence, it matches and separates each part that isn't a -
or [
or ]
.
Preparing the extracted parts
My regex
returns a list of matches full of other metadata.
I just need each matched sub-string.
Using spread
and map()
I can get what I need:
let parts = [...name.matchAll(/\w+/g)].map(el => el[0])
Now I've got:
['aaaaa','bbb','z','y','x','123','abxyz']
Next, I need to separate the id
and checksum
:
let [id, checksum] = parts.slice(-2)
-
slice(-2)
creates an array only the last two items - I store both items into separate variables using
array deconstruction
Lastly, I need one string from the remaining parts:
parts.slice(0,-2).join('')
-
slice(0,-2)
creates an array with all but the last two items -
join('')
concatenates each item together into one string
Tallying each letter's occurrence in the string
For this example:
'aaaaabbbzyx'
I need to create this array:
[ ['a': 5], ['b': 3], ['z': 1], ['y': 1], ['x': 1] ]
My algorithm in JavaScript:
Object.entries(
parts
.slice(0,-2)
.join('')
.split('')
.reduce(
(tallies, letter) => {
tallies[letter] = (tallies[letter] || 0) + 1
return tallies
}, {}
)
)
-
Object.entries()
will generate a nested array where each inner array has two items: the letter and the count -
parts.slice(0,-2).join('').split('')
creates the string, then splits it into an array of single-character strings -
reduce()
generates the dictionary of letters and their counts -
tallies[letter] = (tallies[letter] || 0) + 1
sets as the value for any given letter it's current value - or 0 if there is none yet - then increments it by 1
The trickiest part: sorting the letters correctly
Now that I've got this:
[ ['a': 5], ['b': 3], ['z': 1], ['y': 1], ['x': 1] ]
I really want this:
[ ['a': 5], ['b': 3], ['x': 1], ['y': 1], ['z': 1] ]
Way overthinking it
Create an empty string
Create an index at 0
Do as long as the string's length is less than 5
If the number associated with the letter in the nested array at the current index is the only instance of that number among all the nested arrays
Add the letter to the string
Else
Create a collection of all nested arrays with that number
Sort the collection alphabetically by key
Add the letter of the first item in the sorted collection
Remove the array with that letter from the original collection
I couldn't get that to work.
But that's ok, because I found a much simpler, eloquent and concise solution!
I just needed sort()
Sort the nested arrays by tally in descending order
If two or more tallies are equal, sort those by letter in alphabetical order
My algorithm in JavaScript:
.sort(
(a, b) => b[1] - a[1] || (a[0] > b[0] ? 1 : -1)
)
I was shocked when I noticed it worked!
And very delighted!
Finishing my working algorithm
I now have a sorted nested array.
The rest of my chained-method statement looks like this:
parts
// earlier methods
.slice(0,5)
.map(el => el[0])
.join('') ? +id : 0
-
slice(0,5)
extracts the first five nested arrays -
map(el => el[0])
keeps only the letter from each array -
join('')
concatenates the letters into a string -
? +id : 0
will make sense in a moment
My full algorithm in JavaScript:
return input.reduce((sum, line) => {
let parts = [...line.matchAll(/\w+/g)].map(el => el[0])
let [id, checksum] = parts.slice(-2)
return sum += checksum == Object.entries(
parts
.slice(0,-2)
.join('')
.split('')
.reduce(
(tallies, letter) => {
tallies[letter] = (tallies[letter] || 0) + 1
return tallies
}, {}
)
).sort(
(a, b) => b[1] - a[1] || (a[0] > b[0] ? 1 : -1)
)
.slice(0,5)
.map(el => el[0])
.join('') ? +id : 0
}, 0)
The parts I omitted until now:
-
sum += checksum == ... ? +id : 0
incrementssum
by either the number-coerced id string, or by 0, depending on the 5-character string generated by the rest of the algorithm
Testing and celebrating
- It worked on the example strings!
- It worked on my puzzle input!
Part 2
- Enter:
charCode
s,modulo
andfind...
! - Creating an alphabet array
- Identifying the correct new letter
-
Find...
ing the correct real name
Enter: charCode
s, modulo
and find...
!
-
charCode
s to generate an array ofa-z
-
modulo
to identify the correct new letter -
find...
to manually search forNorth Pole object storage
or something like it
Creating an alphabet array
I need this:
['a', 'b', '...', 'y', 'z']
I could certainly make it manually by typing it out fully.
But I'd rather generate it programmatically.
I need an array with 26 items:
new Array(26)
Where each item is a letter.
But I only really have indices to work with:
new Array(26).fill(null).map((el, index) => //??? )
What can I use that will evaluate to the letters a-z
?
charCode
s!
'a'.charCodeAt(0) // 97
'b'.charCodeAt(0) // 98
'z'.charCodeAt(0) // 113
And to get the letter mapped to a charCode
:
String.fromCharCode(97) // 'a'
Thus, filling in the ???
in my algorithm:
new Array(26).fill(null).map(
(el, index) => String.fromCharCode(index + 97)
)
Voila! I've got my alphabet array!
Identifying the correct new letter
- Say the letter is
b
and theid
is40
-
b
is at index1
since it is the second letter of the alphabet 1 + 40 = 41
41 % 26 = 15
- The real letter is at index
15
:p
When codified as an algorithm, the steps above are accomplished for any given letter in this single line:
alphabet[(alphabet.indexOf(letter) + id) % alphabet.length]
My full algorithm in JavaScript:
input.forEach(line => {
let parts = [...line.matchAll(/\w+/g)].map(el => el[0])
let [id, checksum] = parts.slice(-2)
let alphabet = new Array(26).fill(null).map(
(el, index) => String.fromCharCode(i + 97)
)
console.log(
parts
.slice(0,-2)
.join('-')
.split('')
.map(letter => {
return letter == '-' ? ' ' :
alphabet[
(alphabet.indexOf(letter) + +id) % alphabet.length
]
})
.join(''), id
)
})
Find...
ing the correct real name
With my full algorithm in JavaScript complete, it was time to browse the real names for references to storage
.
colorful egg storage
radioactive flower storage
magnetic fuzzy dye storage
weaponized basket storage
classified radioactive scavenger hunt storage
cryogenic scavenger hunt storage
fuzzy bunny storage
northpole object storage
That last one was it!
I submitted the numeric ID, and it was the correct answer!
I did it!!
- I solved both parts!
- I practiced a bunch of fundamental programming techniques!
- I wrote detailed explanations in hopes they help future beginner programmers feel more comfortable with JavaScript!
Top comments (2)
How on earth did you do this beautiful picker?
It comes for free when you create a Series on dev.to. When you write an article, click the small gear icon next to the 'Save draft' and 'Publish article' button. In the pop-up menu, you can create or add the article to an existing series. All articles in the same series will feature that picker!