**ps. look out for all my other solutions for ***Advent of Code* challenges here.

## Day 14

See details of the challenge here.

Today’s challenge is very similar to that of Day 5, but the requirements for a valid hash value is different this time.

As before, we’ll start by defining a **hash** function that will accept a string and return its MD5 hash value represented as hexdecimal values. After comparing the performance of using **String.format** + **String.Concat** (what I used in *Day 5*) and **BitConverter.ToString** it was a no brainer to go with the latter as it proved to be over 10 times faster even with the additional *String.Replace* and *String.ToLower* calls in this case.

Since part 2 requires us to add key stretching to the hash generation process, our **solve** function will take a hash function as argument.

A brute force approach would be to use **Seq.windowed 1001** to produce sliding windows of 1001 MD5 hashes so we can look for patterns where:

- the first hash has a sequence of 3, eg, “777”
- one of the next 1000 hash values has a sequence of 5 of that character, ie, “77777”

This naive approach took 10s to compute part 1, and over 9 mins for part 2. Most of the time were spent looking for sequences of 5, so an optimization here would be to find all sequences of 5 and storing their indices in a cache. This way, whenever you find a hash with a sequence of 3 – say “777” at index 18 – you can look up the cache for indices associated with “7” and see if there’s any index in the range of 19 – 1018.

This simple optimization took the run time for part 1 to around 300ms.

### Part 2

*Of course, in order to make this process even more secure, you’ve also *

*implemented key stretching.*

*Key stretching forces attackers to spend more time generating hashes. *

*Unfortunately, it forces everyone else to spend more time, too.*

*To implement key stretching, whenever you generate a hash, before you use it, *

*you first find the MD5 hash of that hash, then the MD5 hash of that hash, and so *

*on, a total of 2016 additional hashings. Always use lowercase hexadecimal *

*representations of hashes.*

*For example, to find the stretched hash for index 0 and salt abc:*

*– Find the MD5 hash of abc0: 577571be4de9dcce85a041ba0410f29f.*

*– Then, find the MD5 hash of that hash: eec80a0c92dc8a0777c619d9bb51e910.*

*– Then, find the MD5 hash of that hash: 16062ce768787384c81fe17a7a60c7e3.*

*– …repeat many times…*

*– Then, find the MD5 hash of that hash: a107ff634856bb300138cac6568c0f24.*

*So, the stretched hash for index 0 in this situation is a107ff…. In the end, *

*you find the original hash (one use of MD5), then find the hash-of-the-previous-hash *

*2016 times, for a total of 2017 uses of MD5.*

*The rest of the process remains the same, but now the keys are entirely different. *

*Again for salt abc:*

*– The first triple (222, at index 5) has no matching 22222 in the next thousand *

*hashes.*

*– The second triple (eee, at index 10) hash a matching eeeee at index 89, and so *

*it is the first key.*

*– Eventually, index 22551 produces the 64th key (triple fff with matching fffff *

*at index 22859.*

*Given the actual salt in your puzzle input and using 2016 extra MD5 calls of key *

*stretching, what index now produces your 64th one-time pad key?*

This implementation took around 2 mins to run, and most of the time are spent in generating the hash values (since they are 2016 times more expensive than previously).

I was able to shave 10s off the runtime by hand rolling the bytes-to-hexdecimal part of the **hash** function, but it’s still far from good enough really. So, please let me know in the comments any ideas you have on what we could try next.

## Links