Posted in:

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.