One-Time Pad

Advent of Code 2016 Day 14

Part 1

1. Doable, but likely not fast or eloquent
2. Finding exactly 3 of a character in a row
3. Finding exactly 5 of a character in a row
4. Testing my algorithm on the first 1000 indices
5. Switching data structures for threes and fives
6. Pairing threes with fives
7. Testing my key-finder algorithm
8. Thanks again, reddit solver
9. Exactly!
10. 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 a negative lookbehind
• (8) creates a capture group
• \1 is a backreference to the capture group
• {2} dictates finding two backreferences in a row
• (?!8) is a negative 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, backreferences 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)/ substituting 8 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)/ substituting 8 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 2-element 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 2-element 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 2-element 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 and 92
• fives has only three arrays
• Two of them are the expected characters from when index was 200 and 816

So far, I feel like my 3- and 5-character-in-a-row 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 2-element 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 or fives 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 key-finder 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 to false

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 five-in-a-row 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 5-in-a-row, 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 5-in-a-row!

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 extra-hard 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 the 64th key!

Then I ran it on my puzzle input string

• I got the correct answer!

Part 2

1. Hmm, I wonder how long this will take now
2. 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 hundred-thousand 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 five-in-a-row 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?