Advent of Code 2016 Day 14
Part 1
 Doable, but likely not fast or eloquent
 Finding exactly 3 of a character in a row
 Finding exactly 5 of a character in a row
 Testing my algorithm on the first 1000 indices
 Switching data structures for
threes
andfives
 Pairing
threes
withfives
 Testing my keyfinder algorithm
 Thanks again, reddit solver
 Exactly!
 Way less code for a way more correct answer
Doable, but likely not fast or eloquent
 Day 17 introduced me to MD5 hashes, so making those will be easy
 Previous puzzles has me find an exact count of some character  either contiguous or not  within a string  though I still feel there is a more eloquent, declarative way to do that instead of my imperative tactics
 Then there's the whole
next 1000 hashes
part  I wonder how long it will take my eventual algorithm to process and check 1000 hashes for either 3 or 5 of the same character
Finding exactly 3 of a character in a row
I need an algorithm that tells me:
 Whether there is a character that appears exactly 3 times in a row
 And what that character is
Say I've got the string:
cc38887a5
My algorithm should return:
[true, '8']
Say I've got the string:
cc38287a5
My algorithm should return:
false
Say I've got the string:
cc38888a5
My algorithm should return:
false
This regular expression matches at least three in a row of any character:
/(.)\1{2}/
But it still finds a match if there are more than three in a row of any character.
This regular expression matches exactly three of a specified character  in this case 8
:
/(?<!8)(8)\1{2}(?!8)/

(?<!8)
is anegative lookbehind

(8)
creates a capture group 
\1
is a backreference to the capture group 
{2}
dictates finding two backreferences in a row 
(?!8)
is anegative lookahead
In other words:
 Look for an 8, followed by an 8, followed by an 8
 Where the three 8s are neither preceded nor followed by 8s
Sadly, backreference
s can't be used in a negative lookahead and lookbehind, as far as I can tell.
Could I use both, somehow?
 Maybe use
/(.)\1\1/
to hunt for any instances of at least 3 of any character in a string  Only if there's a match, then for each match use
/(?<!8)(8)\1\1(?!8)/
substituting8
for the character, to check for 2/2 matches  Lastly, if there still happen to be two matches, return the first character matched
Say I've got the string:
cc38887a5
 First test passes
 Second test passes
Say I've got the string:
cc38888a5
 First test passes
 Second test fails
At least that's the hope!
Finding exactly 5 of a character in a row
Now that I can find exactly 3, 5 is a small tweak to two regular expressions:
 Use
/(.)\1{4}/
to hunt for any instances of at least 5 of any character in a string  Only if there's a match, then for each match use
/(?<!8)(8)\1{4}(?!8)/
substituting8
for the character, to check for 2/2 matches  Lastly, if there still happen to be two matches, return the first character matched
Testing my algorithm on the first 1000 indices
Set threes as an empty array
Set fives as an empty array
For i from 0 to 1000
Generate an MD5 hash from the input string concatenated with i
If the hash contains any characters that appear three in a row
Add to threes a 2element array where the first element is the first triplet character and the second element is i
If the hash contains any characters that appear five in a row
For each character that appears five times
Add to fives a 2element array where the first element is the character and the second element is i
When my loop terminates and I display threes
and fives
, I notice:

threes
is filled with 2element arrays  The index in each array is unique  proving I didn't store the second possible triplet in a has with multiple triplets
 It contains the expected characters from when index was
18
,39
and92

fives
has only three arrays  Two of them are the expected characters from when index was
200
and816
So far, I feel like my 3 and 5characterinarow algorithms are working as required!
Switching data structures for threes
and fives
The algorithm above has each one as an array.
Therefore, any time a hash has a match for 3 characters in a row, I add a 2element array to the end.
The array eventually might look like this:
[['a',20],['0',34],['a',37]]
Notice a potential optimization?
 There are only 16 possible characters in a hexadecimal hash
 If I continue like this, I'll have to check every nested array for the character I want to pair
 It would be way easier to only check a list of matched indices associated with each character
Instead, my threes
and fives
will be dictionaries that would look like this:
{
'a': [20,37],
'0': [34]
}
That should be much faster to check any particular character for valid indices that would make it a key!
Pairing threes
with fives
 How long should I let a loop run?
 How often should I check either
threes
orfives
for a pair that generates a key?  How often, if ever, should I 'prune' either dictionary for indices that are already keys or are no longer viable given the current index?
After some time away from this puzzle to ponder these questions, I think I'm on to something:
Set index to 0
Set flag as false
Set keys as an empty array
Set threes as an empty dictionary
Set fives as an empty dictionary
Do as long as keys has fewer than 64 items
Generate an MD5 hash from the input string concatenated with i
If the hash contains any characters that appear three in a row
In threes, create or update the list associated with the first triplet character: add i
If the hash contains any characters that appear five in a row
For each character that appears five times
In fives, create or update the list associated with the character: add i
Set flag to true, indicating that there was a new potential key generated
If flag is true
For each key in fives
Set matches to an empty list
For each value in the key's associated list
Find the corresponding key in threes
For each value in the key's associated list
If the value in fives list minus the value in threes list is less than 1000 and greater than 0
Add the value in threes to keys
Add the value in threes to matches
For each value in matches
Delete that value from the list associated with the current key in threes
Set flag to false
Increment index by 1
Return the 64th item in keys
Testing my keyfinder algorithm
I used abc
as my input string.
Round 1
 My keys list had tons of values, all in the low thousands!
 That's because I forgot to set
flag
tofalse
Round 2
 My keys list had tons of values, all in the slightly higher thousands!
 That's because I forgot the condition about the difference between indices being
greater than 0
Round 3
 My keys list had 67 values in it!
 I guess that's ok, since multiple values could have been added when a new
fiveinarow
hash was found  But the expected 64th key was not
22728
 That key was at index 59
Rounds 4+
 I displayed the two indices being compared for each matched key pair, to confirm they were between 0 and 1000 apart: they were
 I displayed the character that should be 3 and 5inarow, and both hashes, to confirm my regular expressions were working correctly: they were
 I was stumped as to why
22728
wasn't the 64th key  Other than I must not be catching all the matching keys  there must be 5 keys I'm missing
 But I'm certain that I'm catching all keys with
exactly
3 and 5inarow!
Thanks again, reddit solver
 When I'm stumped, I turn to the reddit Solution Megathread
 Thankfully for this puzzle, one solver pasted their JavaScript code
 My intention was to run it, capture all 64 keys, and compare to my list of keys  expecting mine to be missing 5
Indeed, these keys (with their hashes) were missing from my list:
534 4fc7df57777400b3eeef5350a6eecbdf
1144 2e65dc4b3a55644440750cb643d3547c
8189 cc1111a7b059f0326fe4d4fc96fb50d3
8205 3dbee9bccf49a50000346e221d54bb93
8375 f11113032a16c4dfefcaa1d3eb43357c
8811 c3d313e7a72ea2111114dd4963979596
Exactly!
 Each key has a character that appears 4 or 5 times in a row, not exactly 3
Reading the instructions again:
It contains three of the same character in a row, like 777
 No declaration of
exactly
One of the next 1000 hashes in the stream contains that same character five times in a row, like 77777
 No declaration of
exactly
My regular expressions were being too particular!
I feel delighted for two reasons:
 I discovered what my algorithm was doing wrong
 I kind of solved this puzzle on extrahard mode at first, didn't I?
Way less code for a way more correct answer
When attempting to match exactly
three in a row, my JavaScript looked like this:
let matches = [...hash.matchAll(/(.)\1{2}/g)].map(el => el[1])
.filter(match => {
let regex = new RegExp(
`(?<!${match})(${match})\\1\\1(?!${match})`
)
let pass = hash.match(regex)
return pass ? true : false
})
Without the need for an exact amount, it looks like this:
let match = hash.match(/(.)\1{2}/)
My five in a row algorithm had an even bigger reduction in code because after the filter()
was a forEach()
!
With just that change, I ran my program again using abc
as the input string:

22728
was the64
th key!
Then I ran it on my puzzle input string
 I got the correct answer!
Part 2
 Hmm, I wonder how long this will take now
 One update, then the moment of truth
Hmm, I wonder how long this will take now
Approximately 24K times, my algorithm:
 Generates a hash
 Tests it using two regular expressions
 Often looks up and adds a value to a list associated with a key in a dictionary
 And less often iterates through all keys and their values in one dictionary, a particular key and all of its values in another dictionary, and ultimately adds a few values to a list
That feels like a couple hundredthousand operations.
Now, multiply the first bullet by 2017.
That feels like millions  if not 10s or 100s of millions  of operations.
I can only hope my algorithm finishes in under...say...15 seconds?
One update, then the moment of truth
Instead of this:
let hash = MD5(salt + index).toString()
I need this:
let hash = MD5(salt + index).toString()
for (let i = 0; i < 2016; i++) {
hash = MD5(hash).toString()
}
Now for the moment of truth using the example input string:
 Pressed 'Run'
 Waited a minute...seeing nothing still
 Stopped
 Added a line to show the list of keys any time a new fiveinarow match was found
 Pressed 'Run' again
 Saw some outputs!
Kept waiting...
Several minutes now...seeing more keys in the list!
Nearly 10 minutes later:
 The correct answer!
Yikes! 10 minutes!
Well, as long as it finished.
Now for the moment of truth using my input string:
 Pressed 'Run'
Over 20 minutes later:
 The correct answer!
Yikes! Over 20 minutes!
I did it!!
 I solved both parts!
 I wrote too exacting of an algorithm for Part 1 using some new regular expression syntax!
 I feel like my Part 1 algorithm is clever in its approach
 My Part 1 algorithm terminates in under 2 seconds!
 My Part 2 algorithm finishes.......eeeevvveeennntttuuuaaalllyyy...
This puzzle was exactly
what I needed as a reminder to not misread  or incorrectly interpret  the constraints  or lack thereof  for a puzzle.
I could have finished a lot sooner had I not been so exacting.
That's ok, though. It means I'll remember this puzzle longer than had I approached it correctly from the onset, right?
Top comments (0)