# Advent of Code Day 14–The Power of Windows

- Posted in:
- F#
- Advent of Code

The day 14 Advent of Code challenge involved us looking for hashes that met certain criteria. One of those criteria involved finding three repeated characters in a string. Obviously this could be done with regex, but the `Seq.window`

function is also handy for this sort of thing. If we take a list `[1;2;3;4;5]`

and pass it into `Seq.window 3`

then we get out a sequence of 3 element arrays like this: `[|1;2;3|] [|2;3;4|] [|3;4;5|]`

So we can use this to create a `threeInARow`

function that finds the first element in a sequence repeated three times. The function is generic – it doesn’t care what the sequence is of so long as the elements can be meaningfully tested for equality. And it returns an option which is a great way in F# of return either no result (`None`

) or a specific value (`Some myValue`

).

let threeInARow s = s |> Seq.windowed 3 |> Seq.tryFind (function | [|a;b;c|] -> a=b && b=c | _ -> false) |> Option.map (fun a -> a.[0])

I also needed to support calculating hashes. I made a general purpose function called `hash`

that took a string, and returned a lower-case string representation of its hash. And then a more specific function for calculating the hash from a salt and index called `getHash`

. I could have put all the code in one function, but it turned out with part b that breaking out the `hash`

function as it’s own logical step was a good idea. The Single Responsibility Principle applies just as much to functions as classes, and it often pays dividends later in development as you end up with smaller reusable parts.

let md5 = System.Security.Cryptography.MD5.Create() let hash (s:string) = Encoding.Default.GetBytes(s) |> md5.ComputeHash |> (fun h -> BitConverter.ToString(h).ToLower().Replace("-","")) let getHash salt n = sprintf "%s%d" salt n |> hash

But to decide if a particular hash counted as a “key” or not, we needed to not only evaluate that hash, but the next 1000 hashes as well. It was pretty obvious that a naive implementation of the search for keys would needlessly recalculate the hash for the same index many times over.

But `Seq.windowed`

to the rescue again. If we evaluate `[1;2;3;4;5] |> Seq.map someFunc |> Seq.windowed 3`

, we’ll find that `someFunc 3`

is only called once, even though it’s result appears three times in the output sequence. So by using a window size of 1001, we could pass blocks of 1001 hashes into our `isKey`

test function to check whether it constituted a valid “key” or not. Here’s the `isKey`

function

let isKey (hashes:string[]) = let next1000Contains rpt = let find = String(rpt,5) [for n in 1..1000 -> hashes.[n]] |> Seq.exists (fun h -> h.Contains(find)) match threeInARow hashes.[0] with | Some c -> next1000Contains c | _ -> false

And this allows us to create a `solver`

function that generates windowed blocks of 1001 hashes, uses `Seq.indexed`

to keep track of what index we’re on, filters out any that are not “keys” and then picks out the item at a specific index (we needed the 64th).

let solve hasher targetIndex = Seq.initInfinite id |> Seq.map hasher |> Seq.windowed 1001 |> Seq.indexed |> Seq.filter (snd >> isKey) |> Seq.skip (targetIndex-1) |> Seq.head |> fst

For part b of the problem, we calculate a stretched hash, which repeats hashing 2016 times. It’s nice and easy to implement using our `hash`

function and `List.fold`

:

let stretchedHash salt n = [1..2016] |> List.fold (fun s n -> hash s) (getHash salt n)

Thanks to our use of `Seq.windowed`

, this additional compute burden didn’t cause us to have to recalculate the hash for any index more than once. Another approach of course would have been to use memoization to remember the hashes in a dictionary. Memoization comes at a cost of greater memory use, but simplified the code elsewhere.

let input = "ngcjuoqr" solve (getHash input) 64 |> printfn "part a: %d" solve (stretchedHash input) 64 |> printfn "part b: %d"

Full code available on GitHub as usual.