0 Comments

Today’s Advent of Code challenge was, in theory at least, a bit easier, since it bore great similarity to the day 4 challenge from last year. This meant I could start with the code from last year, that looked for MD5 hashes starting with “00000” and use that to provide an input sequence for my password generator.

However, my hopes of solving the problem in record time were dashed by how long it took my i5 Surface Pro 3 to actually run the code. It was around 5 minutes for the solution to part b.

I decided to see if I could slightly improve matters by eliminating converting the hash to a string before testing if it is “interesting”, and I also changed it to use Seq.initInfinite rather than putting an arbitrary upper bound on how many hashes we’ll create. So here’s my revised function to generate a sequence of “interesting hashes”:

let md5 = System.Security.Cryptography.MD5.Create()

let findHash doorId = 
    let isInteresting (hash:byte[]) = hash.[0] = 0uy && hash.[1] = 0uy && hash.[2] <= 0xFuy
    Seq.initInfinite (sprintf "%s%d" doorId) 
    |> Seq.map (System.Text.Encoding.ASCII.GetBytes >> md5.ComputeHash)
    |> Seq.filter isInteresting
    |> Seq.map (fun h -> BitConverter.ToString(h).Replace("-",""))

With this function in place, Part a is easily solved by taking the first 8 values from this sequence, and extracting the sixth character from each one and concatenating to a string:

let input = "abbhdwsy"

let findPassword doorId =
    findHash doorId |> Seq.take 8 |> Seq.map (fun h-> h.Substring(5,1)) |> String.Concat |> (fun s -> s.ToLower())

findPassword input |> printfn "Part a: %s"

For part b, we still need to take the sequence of interesting hashes from findHash, but we need to apply each one to our target password, which I initialise to “????????”. I created a function that takes a tuple of position and character and applies that to the current password if applicable:

let useChar (password:string) (pos, ch) =
    if pos < 8 && password.[pos] = '?' then
        sprintf "%s%c%s" (password.Substring(0,pos)) ch (password.Substring(pos+1))
    else
        password

Now we can use Seq.scan to apply each hash to our useChar function and then use Seq.find to keep going until we’ve got all 8 characters of our password filled in.

let findPassword2 doorId =
    findHash doorId 
    |> Seq.map (fun h -> int h.[5] - int '0', h.[6]) 
    |> Seq.scan useChar "????????"
    |> Seq.find (fun f -> f.IndexOf("?") = -1)
    |> (fun s -> s.ToLower())

findPassword2 input |> printfn "Part b: %s"

As usual the full code is up on GitHub, and I welcome any suggestions for improving it, particularly if I can squeeze a bit more performance out of it.

Vote on HN
comments powered by Disqus