29 April 2017

AOC 2016 - Day 5

Table of Contents

AOC 2016 - Day 5

Problem statement on Advent of Code website.

Code for this post can be found on GitHub.

Background

  • On Day 1, we located Easter Bunny headquarters.
  • On Day 2, we broke the code to use the bathroom in Easter Bunny HQ.
  • On Day 3, we helped the EBs' design department by removing invalid triangles from the list.
  • On Day 4, we figured out which rooms in the information kiosk are valid.

On Day 5, we will figure out how to get past security doors by calculating the code.

Problem - Part 1

For Part 1, we are given two pieces of information.

  1. The door ID
  2. An increasing integer index, starting at 0.

For each MD5 hash that starts with 00000 (five 0's), the 6th digit indicates the next character of the password. If we find eight hashes that start with five 0's, that provides the password.

Solution - Part 1

My strategy to solve this problem was two-fold.

  1. Write an MD5 algorithm in F#.
    1. I outlined my solution for a functional MD5 algorithm in F# in a previous blog post.
  2. Write a function to collect the required hashes and construct the final answer.

The vast majority of the functionality for this solution is in the MD5 algorithm, which I won't describe here again.

Collection function

Once I had an MD5 algorithm, I used the Seq module and its library functions to collect the required hashes and calculate the door password.

The strategy for the function is simple.

  1. Start by producing indices starting at 0.
  2. Map all the strings to hashes.
  3. Remove all hashes that don't match the criteria (i.e. hashes that don't start with 00000).
  4. Once we have eight hashes, stop producing indices and get the final answer.
let day5part1input = "cxdnnyjw"

let day5part1criteria = "00000"

let day5part1 input crit (md5sum:string -> string) =
  Seq.initInfinite (fun i -> input + string i)
  |> Seq.map md5sum
  |> Seq.filter (fun m -> m.StartsWith crit)
  |> Seq.take 8
  |> Seq.map (Seq.item 5 >> string)
  |> Seq.reduce ( + )

When I ran the function, I got F77A0E6E, which is the correct answer.

Problem - Part 2

The problem statement for Part 2 still uses the MD5 function, but adds a twist to the password computation. We still have the same information from the problem.

  1. The door ID
  2. An increasing integer index, starting at 0.

We are still only interested in hashes that start with five 0's, i.e. 00000. The sixth character of the hash now indicates the position in the solution and the seventh character is what goes into that position.

If we get multiple hashes that meet the criteria and indicate the same position, all but the first match are ignored. Hashes that meet the criteria but indicate an invalid position, i.e. anything other than 0-7, are also ignored.

Solution - Part 2

To solve Part 2, I wanted to use a similar approach to Part 1. However, I needed to way to determine when the algorithm had collected enough values to form a complete answer.

My overall strategy was as follows.

  1. Start by producing indices starting at 0.
  2. Map all the strings to hashes.
  3. Remove all hashes that don't match the criteria.
  4. Once I have a character for each position of the answer, stop producing indices and get the final answer.

Storing the pieces of the answer

I chose to use a Dictionary<int, string> collection to hold the values that would form the answer. The keys represent the position in the answer and the values are the single-character strings that, when concatenated, would form the answer.

First, I created a value that would hold the relevant pieces.

let answer = Dictionary<int, string> 8

Second, I created an add function that would only add values to the Dictionary if a value for the key was not already present.

let add (d:Dictionary<_,_>) kv =
  if not <| d.ContainsKey(fst kv) then
    d.Add(fst kv, snd kv)
  else ()

Third, I created a notComplete function to check whether I had collected enough values for an answer.

let notComplete (d:Dictionary<_,_>) = d.Count < 8

Collecting the pieces of the answer

Once I had decided on a storage strategy, I wrote a function to add values to the Dictionary until I had enough to get an answer.

The overall strategy for this part of the logic depends on the Seq.takeWhile function. This function will terminate the infinite sequence generator once the Dictionary is "full".

Seq.initInfinite (fun i -> input + string i)
|> Seq.map md5sum
|> Seq.filter
  (fun m ->
    (m.StartsWith crit)
      && (m.[5] = '0' || m.[5] = '1' || m.[5] = '2' || m.[5] = '3'
      || m.[5] = '4' || m.[5] = '5' || m.[5] = '6' || m.[5] = '7'))
|> Seq.map (fun m -> m.[5] |> string |> System.Int32.Parse, m.[6] |> string)
|> Seq.takeWhile (fun _ -> notComplete answer)
|> Seq.iter (fun m -> add answer m)

Producing the answer

As the last step, I pulled the values from the Dictionary and concatenated the strings to get the final answer.

I chose to explicitly pull the values based on key lookups because, while there are library functions to get a collection of the values, I did not see any guarantees about the order that the items would be in.

[
  for i in 0 .. 7 do
    yield answer.[i]
]
|> List.reduce ( + )

When I ran this function, I got back 999828EC which is, in fact, the correct answer.

Some side notes

Mutable vs. Immutable data structures

As you may have noticed, I am using a mutable data structure to store the needed values for the Part 2 solution. At the time, I struggled to find a "pure" functional way of solving the problem but couldn't come up with something off hand (and, to tell you the truth, I didn't try too hard since I had just finished the MD5 algorithm and wanted to be done with this problem).

However, the Part 2 algorithm can easily be rewritten using a tail-recursive function and immutable data structures. The tail-recursive part is important because, while I don't know how many hashes the algorithm has to go through, I do know that even the OOTB MD5 algorithm takes over 2 minutes to calculate the answer (and my functional MD5 algorithm takes over 7 minutes). From that, I assume that the stack would get very deep if the function was not tail-recursive.

Seq vs. ParallelSeq

In order to speed up the calculation, I attempted to use the ParallelSeq library to take advantage of my CPU's multiple cores. Using the ParallelSeq library did speed up my calculations considerably.

However, one thing I learned is that the ParallelSeq library does not take care of putting the calculated values back in their original order. Instead, it is the client's responsibility to track the order of values (if that is important - and in this case it was).

As an example, when I used the ParallelSeq library, the system produced C9E29889 as the answer for Part 2. However, the correct answer for Part 2 is 999828EC, which are the same characters but in the correct order.

In the end, I removed ParallelSeq from this solution but it is a library that I intend to investigate in the future.

Lessons learned

Here are the lessons I learned from this exercise.

  1. Take the time to implement a solution the way you want, so that you do not later have regrets about it. In this instance, I regret choosing a mutable data structure and imperative algorithm to solve Part 2 and it's something I hope to rectify in the near future.
  2. Just as when I implemented the MD5 algorithm in F#, it is critical to be extra vigilant when reading code. Much more so than any other technique, reading and understanding code is the fastest way to find and fix most bugs.

See you next time!

PS: Solution - Part 2 (Pure functional implementation)

After I wrote this blog post, but before posting it, I decided to rewrite the Part 2 solution using immutable data structures.

Rewriting the function was quite simple, and relied on the following strategy.

  1. Define a completion check to terminate the recursive function.
  2. Define a tail-recursive function to calculate the 8 characters of the answer.
  3. Combine the 8 characters to form the final answer.

Here is the code for the pure functional implementation of Part 2, broken into 3 chunks.

let day5part2alt input crit (md5sum : string -> string) =
  let complete l = l |> List.filter ((=) "") |> List.isEmpty

  let rec collector i acc =
    if complete acc then acc
    else
      let m = md5sum (input + string i)
      if (m.StartsWith crit) then
        match m.[5] with
        | '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' ->
          List.mapi (fun idx elt ->
            if elt = "" && idx = (m.[5] |> string |> System.Int32.Parse) then
              string m.[6]
            else elt) acc
          |> collector (i + 1)
        | _ -> collector (i + 1) acc
      else collector (i + 1) acc

  [ ""; ""; ""; ""; ""; ""; ""; "" ]
  |> collector 0
  |> List.reduce (+)

Running this function provides the same answer as above, i.e. 999828EC.

Performance comparison with day5part2

I compared day5part2 and day5part2alt to see whether my new implementation matches up to the previous one.

On average, I received the following results.

day5part2 vs. day5part2alt, raw numbers.
Function Real CPU Gen0 Gen1 Gen2

day5part2

174.758

174.689

21623

18

2

day5part2alt

166.528

166.437

20590

17

1

And here are the same results, converted to percentages.

day5part2 vs. day5part2alt, percentages.
Function Real CPU Gen0 Gen1 Gen2

day5part2

105%

105%

105%

106%

200%

day5part2alt

100%

100%

100%

100%

100%

Ignoring the Gen2 result, the mutable version is actually 5% worse across the board, in both processing time and increased garbage collection. It pays to be immutable.

See you next time!

22 April 2017

MD5 in F#, Functionally

Table of Contents

MD5 in F#, Functionally

Code for this post can be found on GitHub.

The Advent of Code Day 5 problem presented a very interesting challenge - it required an MD5 hash function to get the final answer.

As my goal with the AOC challenges is to increase my knowledge of F#, I chose to:

  • Implement my own version of the MD5 algorithm
  • Implement it functionally (no mutation, if possible)

Out-of-the-box implementation

.NET has an out-of-the-box implementation of MD5, which can be accessed quite easily from F#. It resides in the System.Security.Cryptography namespace. Here is a function that takes in a string and outputs its hash as a string.

let md5ootb (msg: string) =
  use md5 = System.Security.Cryptography.MD5.Create()
  msg
  |> System.Text.Encoding.ASCII.GetBytes
  |> md5.ComputeHash
  |> Seq.map (fun c -> c.ToString("X2"))
  |> Seq.reduce ( + )

This helps immensely in two ways:

  • It makes it very easy to check whether my hash function is working correctly because its output must match the OOTB MD5 algorithm's output.
  • It provides a baseline against which to compare performance.

Planning the implementation

First, let me just say that I have never implemented a "cryptographic" algorithm, such as a hash function, encryption algorithm, etc. I knew that the implementation would be more difficult than a normal algorithm and so I spent a considerable amount of time reading the following resources.

  1. RFC 1321: The MD5 Message-Digest Algorithm
  2. Wikipedia: MD5
  3. Rosetta Code: MD5/Implementation

The first two resources helped me understand the flow of logic. The last resource is a compilation of MD5 implementations collected in one spot and, luckily, written in multiple languages. This gave me different perspectives on how the code can be broken up, alternatives for implementation, etc.

I relied especially heavily on the Java, C#, Python, and Haskell implementations because those are the languages I am most familiar with.

For reference, here is the entire listing from Wikipedia.

'//Note: All variables are unsigned 32 bit and wrap modulo 2^32 when calculating
var int[64] s, K

'//s specifies the per-round shift amounts
s[ 0..15] := { 7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22 }
s[16..31] := { 5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20 }
s[32..47] := { 4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23 }
s[48..63] := { 6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21 }

'//Use binary integer part of the sines of integers (Radians) as constants:
for i from 0 to 63
    K[i] := floor(2^32 × abs(sin(i + 1)))
end for
'//(Or just use the following precomputed table):
'// ... (I did not use a pre-computed table, so I've removed it for brevity sake)

'//Initialize variables:
var int a0 := 0x67452301   //A
var int b0 := 0xefcdab89   //B
var int c0 := 0x98badcfe   //C
var int d0 := 0x10325476   //D

'//Pre-processing: adding a single 1 bit
append "1" bit to message
'// Notice: the input bytes are considered as bits strings,
'//  where the first bit is the most significant bit of the byte.[48]


'//Pre-processing: padding with zeros
append "0" bit until message length in bits ≡ 448 (mod 512)
append original length in bits mod (2 pow 64) to message


'//Process the message in successive 512-bit chunks:
for each 512-bit chunk of message
    break chunk into sixteen 32-bit words M[j], 0 ≤ j ≤ 15
'//Initialize hash value for this chunk:
    var int A := a0
    var int B := b0
    var int C := c0
    var int D := d0
'//Main loop:
    for i from 0 to 63
        if 0 ≤ i ≤ 15 then
            F := (B and C) or ((not B) and D)
            g := i
        else if 16 ≤ i ≤ 31
            F := (D and B) or ((not D) and C)
            g := (5×i + 1) mod 16
        else if 32 ≤ i ≤ 47
            F := B xor C xor D
            g := (3×i + 5) mod 16
        else if 48 ≤ i ≤ 63
            F := C xor (B or (not D))
            g := (7×i) mod 16
'//Be wary of the below definitions of a,b,c,d
        dTemp := D
        D := C
        C := B
        B := B + leftrotate((A + F + K[i] + M[g]), s[i])
        A := dTemp
    end for
'//Add this chunk's hash to result so far:
    a0 := a0 + A
    b0 := b0 + B
    c0 := c0 + C
    d0 := d0 + D
end for

var char digest[16] := a0 append b0 append c0 append d0 '//(Output is in little-endian)

'//leftrotate function definition
leftrotate (x, c)
    return (x << c) binary or (x >> (32-c));

Considerations

There are a few concerns I had about this implementation.

  1. The algorithm assumes that all values are stored in the little-endian format.
  2. The algorithm requires a bitwise-left-rotate function, which F# does not provide.
  3. How to store a 128-bit hash.

Initially, and I'm not sure why I thought this, I was under the assumption that Intel CPUs use the big-endian format. However, they actually use little-endian, which makes that consideration irrelevant.

It took me an embarrassing amount of time to hunt down a bug where I forgot that the F# left-shift operator <<< is NOT a left-rotate operator. Once I narrowed down on the bug, it was easy enough to implement a function to perform the rotations. However, this was a good lesson in never assuming anything when reading code - my eyes were just glazing over the <<< operator, even though the problem was staring me in the face.

Finally, I chose to store the values as 4 uint32 integers. This is similar to what the RFC authors, Wikipedia authors, and other implementations did on Rosetta Code. While F# does have the uint64 type, it would have required translating all the 32-bit-based pseudo-code / code (introducing an element of risk) and I'm not sure what benefits, if any, it would have provided.

Mapping from Wikipedia to F#

I started my analysis and design phase by taking the pseudo-code from Wikipedia and mapping it to how I wanted to break up my implementation. I tried to use the same names for variables and, for consistency's sake, I ended up using the Wikipedia naming scheme.

Oddly enough, Wikipedia uses different variable names compared to the RFC pseudo-code and I did not find a good reason for why the original writers did this.

Mapping from Wikipedia's pseudo-code to my F# implementation (function and value signatures).
# Wikipedia F#

1

'//s specifies the per-round shift
'//amounts
var int[64] s
val s : int list

2

'//Use binary integer part of the sines
'//of integers (Radians) as constants:
var int[64] K
val k : uint32 list

3

'//Initialize variables:
var int a0
var int b0
var int c0
var int d0
type MD5 =
  {a: uint32;
   b: uint32;
   c: uint32;
   d: uint32;}
val initialMD5 : MD5

4

'//Pre-processing: adding a single 1 bit
append "1" bit to message

'//Pre-processing: padding with zeros
append "0" bit until message length in
bits ≡ 448 (mod 512)

append original length in bits mod (2
pow 64) to message
val padMessage : msg:byte [] -> byte []

5

'//Process the message in successive
'//512-bit chunks:
for each 512-bit chunk of message
// Array.chunkBySize and Array.fold
val md5sum : msg:string -> string

6

'//Initialize hash value for this chunk:
var int A, B, C, D

'//Main loop:
for i from 0 to 63
  '// NOT THE CONTENTS OF THE LOOP
end for

'//Add this chunk's hash to result so
'//far:
a0, b0, c0, d0
// List.fold
val md5plus : m:MD5 -> bs:byte [] -> MD5

7

'//Main loop: (contents)
if ...
else if ...
else if ...
else if ...

dTemp, D, C, B, A
val md5round : msg:uint32 [] -> MD5 ->
i:int -> MD5

// Includes:
val fghi : (uint32 -> uint32 -> uint32
-> uint32) list

val gIdxs : int list

Implementation

Step 1: Define the shift in each of the 64 rounds

On the Wikipedia page, the per-round shift amounts are hard-coded as a 64-value int array.

s[ 0..15] := { 7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22 }
s[16..31] := { 5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20 }
s[32..47] := { 4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23 }
s[48..63] := { 6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21 }

In F#, I used some convenience functions in the List module to achieve the same result.

let s =
  [[7; 12; 17; 22]; [5; 9; 14; 20]; [4; 11; 16; 23]; [6; 10; 15; 21]]
  |> List.collect (List.replicate 4)
  |> List.concat

val s : int list

Step 2: Calculate the binary integer portion of integer sines

Wikipedia provides two methods of calculating the constants that are based on the sine function. First, here is the description from the RFC.

... constructed from the sine function. Let T[i] denote the i-th element of the table, which is equal to the integer part of 4294967296 times abs(sin(i)), where i is in radians.

Wikipedia's two methods of defining K[i] (Wikipedia's name for T[i]) are as follows:

for i from 0 to 63
    K[i] := floor(2^32 × abs(sin(i + 1)))
end for
'//(Or just use the following precomputed table):
K[ 0.. 3] := { 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee }
K[ 4.. 7] := { 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501 }
K[ 8..11] := { 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be }
K[12..15] := { 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821 }
K[16..19] := { 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa }
K[20..23] := { 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8 }
K[24..27] := { 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed }
K[28..31] := { 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a }
K[32..35] := { 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c }
K[36..39] := { 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70 }
K[40..43] := { 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05 }
K[44..47] := { 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665 }
K[48..51] := { 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039 }
K[52..55] := { 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1 }
K[56..59] := { 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1 }
K[60..63] := { 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391 }

For my solution, I chose to go the function route instead of hard-coding the table into the source code. This was primarily for brevity's sake. A side benefit was that it allowed me to put in a long and oddly satisfying function chain.

let k =
  [1. .. 64.] |> List.map (sin >> abs >> (( * ) (2.**32.)) >> floor >> uint32)

val k : uint32 list

Step 3: Define the types

I defined one new type for this problem, MD5. This record holds an MD5 hash as 4 uint32 values.

type MD5 =
  {
    a : uint32
    b : uint32
    c : uint32
    d : uint32
  }

let initialMD5 =
  {
    a = 0x67452301u
    b = 0xefcdab89u
    c = 0x98badcfeu
    d = 0x10325476u
  }

Step 4: Padding the message

The MD5 algorithm doesn't require a message of a certain length, but instead adds padding so that the final message length is a multiple of 512 bits (or 64 bytes).

There are 3 steps involved in padding:

'//Pre-processing: adding a single 1 bit
append "1" bit to message

'//Pre-processing: padding with zeros
append "0" bit until message length in bits ≡ 448 (mod 512)
append original length in bits mod (2 pow 64) to message

This part actually gave me some trouble because I thought that I had to add one bit (containing 1) to my message in the MSB (most significant bit) slot, and then start appending 0s or the message length immediately after that. That turns out not to be the case, and reading the RFC and other implementations on Rosetta Code provided a good solution to the problem.

Essentially, following the message, we need to add a 0x80 16-bit word followed by the length (restricted to 8 bytes). The intervening space, if any, is filled with 0 bytes.

let padMessage (msg : byte []) =
  let msgLen = Array.length msg
  let msgLenInBits = (uint64 msgLen) * 8UL

  let lastSegmentSize =
    let m = msgLen % 64
    if m = 0 then 64
    else m

  let padLen =
    64 - lastSegmentSize + (if lastSegmentSize >= 56 then 64
                            else 0)

  [|
    yield 128uy
    for i in 2..padLen - 8 do
      yield 0uy
    for i in 0..7 do
      yield ((msgLenInBits >>> (8 * i)) |> byte)
  |]
  |> Array.append msg

val padMessage : msg:byte [] -> byte []

This is the one part of the implementation that had the highest potential to be "impure". Specifically, the part that constructs the padding. However, F# array comprehensions removed the need to mutate an array to construct the padding before it is appended to the msg.

Step 7: The core of the main loop (Yes, I know this is out of order)

The Wikipedia pseudo-code is written in an imperative manner where the main loops are encountered before we get to the meat of the hash construction algorithm. However, in order to explain my construction, I will start by looking at the implementation for a single iteration of the "Main loop", and then build my way out from there.

The Wikipedia pseudo-code for this step is as follows.

        if 0 ≤ i ≤ 15 then
            F := (B and C) or ((not B) and D)
            g := i
        else if 16 ≤ i ≤ 31
            F := (D and B) or ((not D) and C)
            g := (5×i + 1) mod 16
        else if 32 ≤ i ≤ 47
            F := B xor C xor D
            g := (3×i + 5) mod 16
        else if 48 ≤ i ≤ 63
            F := C xor (B or (not D))
            g := (7×i) mod 16
'//Be wary of the below definitions of a,b,c,d
        dTemp := D
        D := C
        C := B
        B := B + leftrotate((A + F + K[i] + M[g]), s[i])
        A := dTemp

In F#, I have three separate constructs that we need to look at. First, I followed the technique used by a few other implementations and collected the functions represented by F in a function list. This allows index-based access to the correct function.

let fxyz x y z : uint32 = (x &&& y) ||| (~~~x &&& z)
let gxyz x y z : uint32 = (z &&& x) ||| (~~~z &&& y)
let hxyz x y z : uint32 = x ^^^ y ^^^ z
let ixyz x y z : uint32 = y ^^^ (x ||| ~~~z)

let fghi =
  [fxyz; gxyz; hxyz; ixyz]
  |> List.collect (List.replicate 16)

val fxyz : x:uint32 -> y:uint32 -> z:uint32 -> uint32
val gxyz : x:uint32 -> y:uint32 -> z:uint32 -> uint32
val hxyz : x:uint32 -> y:uint32 -> z:uint32 -> uint32
val ixyz : x:uint32 -> y:uint32 -> z:uint32 -> uint32
val fghi : (uint32 -> uint32 -> uint32 -> uint32) list

Second, I turned g into a set of functions and, as above, collected the pre-computed indices in a list.

let g1Idx = id
let g2Idx i = (5*i + 1) % 16
let g3Idx i = (3*i + 5) % 16
let g4Idx i = (7*i) % 16

let gIdxs =
  [g1Idx; g2Idx; g3Idx; g4Idx]
  |> List.collect (List.replicate 16)
  |> List.map2 (fun idx func -> func idx) [0..63]

val g1Idx : ('a -> 'a)
val g2Idx : i:int -> int
val g3Idx : i:int -> int
val g4Idx : i:int -> int
val gIdxs : int list

Finally, I implemented a single round of the MD5 computation.

let md5round (msg:uint32[]) {MD5.a=a; MD5.b=b; MD5.c=c; MD5.d=d} i =
  let rotateL32 r x = (x<<<r) ||| (x>>>(32-r))
  let f = fghi.[i] b c d
  let a' = b + (a + f + k.[i] + msg.[gIdxs.[i]] |> rotateL32 s.[i])
  {a=d; b=a'; c=b; d=c}

val md5round : msg:uint32 [] -> MD5 -> i:int -> MD5

The md5round function takes in the computed-so-far MD5 hash and an index, calculates the updated hash, and passes it back to the caller.

Step 6: Hash a single 512-bit chunk

This step actually implements the "Main loop", using the logic we coded for a single iteration of the loop.

Here is Wikipedia's pseudo-code, although I have removed the text (replaced by a comment) that is part of Step 7.

for each 512-bit chunk of message
    break chunk into sixteen 32-bit words M[j], 0 ≤ j ≤ 15
//Initialize hash value for this chunk:
    var int A := a0
    var int B := b0
    var int C := c0
    var int D := d0
//Main loop:
    for i from 0 to 63
        '// SEE STEP 7
    end for
'//Add this chunk's hash to result so far:
    a0 := a0 + A
    b0 := b0 + B
    c0 := c0 + C
    d0 := d0 + D
end for

Note that although Wikipedia uses the labels a0, b0, c0, and d0, these are mutable values that permanently change with each 512-bit chunk that is processed. Thus, each new 512-bit chunk starts with these 4 values that have been changed by all the previous chunks that have been processed.

The flow in this part of the code, without the details from Step 7, can be broken down into 3 parts:

  1. Start with an initial value.
  2. Run an algorithm a limited number of times, wherein each execution of the algorithm uses the results from the previous run as the input.
  3. Take the final value and continue with the overall flow.

This is a perfect scenario for a fold operation. Here is the F# code from my implementation.

let md5plus m (bs:byte[]) =
  let msg =
    bs
    |> Array.chunkBySize 4
    |> Array.take 16
    |> Array.map (fun elt -> System.BitConverter.ToUInt32(elt, 0))
  let m' = List.fold (md5round msg) m [0..63]
  {a=m.a+m'.a; b=m.b+m'.b; c=m.c+m'.c; d=m.d+m'.d}

val md5plus : m:MD5 -> bs:byte [] -> MD5

md5plus expects the caller to pass in the initial value for the fold and the message that must be processed.

md5round operates on a message (that will not change for a single 512-bit chunk), an MD5 value, and an index. Those are the values that md5plus is using for the fold.

At the end, md5plus passes back an updated MD5 hash which incorporates the changes derived from processing the given 512-bit chunk.

Step 5: Process the entire message and derive a single MD5 hash

The last step is to bring together all the individual pieces into a single algorithm that can:

  • Take in a message of any length
  • Pad the message correctly
  • Calculate the MD5 hashes for each 512-bit chunk
  • Produce a single MD5 hash.

Wikipedia's pseudo-code for this step is quite simple.

var char digest[16] := a0 append b0 append c0 append d0
'//(Output is in little-endian)

However, since I built the solution as a set of functions, this final function must do a little more work.

let md5sum (msg: string) =
  System.Text.Encoding.ASCII.GetBytes msg
  |> padMessage
  |> Array.chunkBySize 64
  |> Array.fold md5plus initialMD5
  |> (fun {MD5.a=a; MD5.b=b; MD5.c=c; MD5.d=d} ->
    System.BitConverter.GetBytes a
    |> (fun x -> System.BitConverter.GetBytes b |> Array.append x)
    |> (fun x -> System.BitConverter.GetBytes c |> Array.append x)
    |> (fun x -> System.BitConverter.GetBytes d |> Array.append x))
  |> Array.map (sprintf "%02X")
  |> Array.reduce ( + )

val md5sum : msg:string -> string

The main part of the algorithm is just the first 4 lines:

let md5sum (msg: string) =
  System.Text.Encoding.ASCII.GetBytes msg
  |> padMessage
  |> Array.chunkBySize 64
  |> Array.fold md5plus initialMD5

The rest of the function is devoted to converting the MD5 hash into a user-friendly representation.

Testing

Based on the testing I've done so far, this algorithm works correctly and produces exactly the same results as the OOTB MD5 algorithm.

I first started by implementing the "standard" tests (originally specified in the RFC) and comparing the results with the OOTB algorithm.

Then, I added an FsCheck test that compared my algorithm against the OOTB one for 10,000 tests - all passed without any problems. Now that I've finally learned how to properly use FsCheck at a basic level, I'm starting to find it difficult to completely trust my results unless all the FsCheck tests pass. I don't think that this is necessarily a bad thing, because it tends to make explicit assumptions that I made in my code (e.g. for my MD5 algorithm, I assume that the original message is an actual string and not just a NULL).

Performance

Raw data for performance measurements on GitHub.

I measured performance by using the AOC Day 5, Part 1 problem, which computes thousands of MD5 hashes. Here are the results, derived using F# interactive's #time directive. I ran each test 3 times and averaged the results.

Average run-time and garbage collection performance of the algorithms, in seconds
Algorithm Real CPU Gen0 Gen1 Gen2
OOTB 53.37 53.37 6780.33 6.00 0.67
Functional 172.79 172.76 34754.00 17.67 1.67

Here is the same chart, but with percentages.

Average run-time and garbage collection performance of the algorithms as a percentage, with the OOTB algorithm as the baseline.
Algorithm Real CPU Gen0 Gen1 Gen2
OOTB 100% 100% 100% 100% 100%
Functional 324% 324% 513% 294% 250%

Obviously, my functional version of this algorithm is a LOT worse than the OOTB implementation.

Lessons Learned

  1. Be extremely careful of assumptions when reading code. Each character and symbol should be analyzed to ensure that it is appropriate for the task at hand.
  2. Define the tee function at the beginning of each project because it WILL be useful at some point.
  3. It's been a goal of mine to implement a "cryptographic" algorithm for a few years now, but I never found the time before. I have to say that it was a lot of fun and I can't wait to do it again!
    • Not strictly a lesson, unless that lesson is "have fun with hobby projects".

See you next time!

14 April 2017

AOC 2016 - Day 4

Table of Contents

AOC 2016 - Day 4

Problem statement on Advent of Code website.

Code for this post can be found on GitHub.

Background

  • On Day 1, we located Easter Bunny headquarters.
  • On Day 2, we broke the code to use the bathroom in Easter Bunny HQ.
  • On Day 3, we helped the EBs' design department by removing invalid triangles from the list.

On Day 4, we will figure out which rooms on an encrypted information kiosk are valid and which ones are not.

Problem - Part 1

The kiosk lists one room per line. Each room entry consists of 3 parts.

  1. Encrypted name comprised of lowercase letters separated by dashes
    • Always follows by a dash
  2. Sector ID
  3. Checksum
    • Always in square brackets

For Part 1, we have to determine which entries are real by calculating a checksum based on the encrypted name. The actual answer we have to provide is the sum of the sector IDs for all valid rooms.

Before I dive into the solution, I want to note that this problem has a lot of moving parts and, even though I've already solved it, it took me over half an hour to understand it again. There's just something about it that confuses the heck out of me every time.

Solution - Part 1

I approached the solution from a few different angles before I settled on the following solution.

I started by first trying to understand the overall steps involved in the solution. Then, once I had a basic picture worked out, I focused on creating a data structure that could hold all the data that I needed.

I knew I wanted a single 'flow' to the logic and to do that, I would have to pull together separate pieces of data and then start tying them together. With the right data structure, I could basically thread it through all my functions and tie them together nicely at the end.

My overall solution strategy is as follows.

  1. Store each unchanged line of data.
  2. Extract the sector ID and checksum.
    • Based on the requested answer, we can assume that all sector IDs are numeric values.
  3. Calculate the checksums for each encrypted room name.
  4. Finally, filter the list and add up the valid rooms' sector IDs.

The one thing that I noticed above all else is that I had to go out and learn a lot more about regular expressions in general and .NET regular expressions specifically to solve this problem.

Create the data structure

My whole solution hinges on a data structure that can hold all the data I need a series of disparate functions that only come together at the end.

type Line = {
  line: string
  sectorID: int
  calculatedChecksum: string
  providedChecksum: string
}

let emptyLine = {
  line = ""; sectorID = 0; calculatedChecksum = ""; providedChecksum = "";
  decryptedText = ""
}

As you can tell, I chose to go with a record for this solution. emptyLine is simply an empty Line for convenience in various functions.

line
Holds the unaltered line from the input file.
sectorID
The provided sector ID extracted from the raw line.
calculatedChecksum
The calculated checksum based on the encrypted room name.
providedChecksum
The provided checksum extracted from the raw line.

Store each unchanged line of data

I chose to make this its own step because of the lesson I learned from my last solution, where the parsing strategy was different between Parts 1 and 2.

The code to extract each line from the input file is quite simple.

let lines filename =
  File.ReadAllLines filename
  |> Seq.cast
  |> Seq.map (fun x -> {emptyLine with line = string x})

Extract the provided sector ID and checksum

Extracting the sector ID proved to be quite an issue until I read the problem over a few more times. Once I understood that the sector ID is numeric only (since we have to add them up) and the encrypted name (and thus the checksum) is composed of lower-case letters only, the regular expression was relatively simple.

let extractSectorIDs lines =
  lines
  |> Seq.map
    (fun l ->
    {l with
      sectorID = (Regex.Match (l.line, @"[0-9]+")).Groups.[0].Value |> int})

Extracting the checksum was easier because the problem states that the checksum is enclosed by square brackets [].

let extractProvidedChecksums lines =
  lines
  |> Seq.map
    (fun l ->
      {l with
        providedChecksum =
        (Regex.Match (l.line, @"\[([a-zA-Z]+)\]")).Groups.[1].Value})

The hardest thing was knowing which Group I wanted from each regular expression. This required a decent amount of trial and error in online .NET regex tools and F# interactive.

Calculate the checksum

I started by:

  1. Extracting the encrypted room name from each line
  2. Removing the dashes
  3. Concatenating all parts of the encrypted name (if more than 1)
let calculateChecksums lines =
  lines
  |> Seq.map
    (fun l ->
      {l with
        calculatedChecksum =
        (Regex.Matches (l.line, @"([a-zA-Z]+)\-"))
        |> Seq.cast
        |> Seq.map
          (fun (x : System.Text.RegularExpressions.Match) ->
            let substr = x.Value
            substr.Substring(0, String.length substr - 1))
        |> String.concat ""
        |> calculateChecksum
      }
    )

Once the encrypted name was cleaned up and transformed, I passed it over to a separate function to calculate the checksum.

let calculateChecksum (line: string) =
  line
  |> Seq.countBy id
  |> Seq.sortBy fst
  |> Seq.sortByDescending snd
  |> Seq.truncate 5
  |> Seq.fold (fun accum (elt, _) -> accum + elt.ToString()) ""

This function relies heavily on the assertion in the .NET documentation that Seq.sort and its variants are stable sorts.

Tie it all together

The last step is to tie all the steps together by threading a seq<Line> through the logic.

let day4part1 =
  lines puzzleInput
  |> extractSectorIDs
  |> extractProvidedChecksums
  |> calculateChecksums
  |> Seq.filter (fun x -> x.providedChecksum = x.calculatedChecksum)
  |> Seq.fold (fun accum elt -> accum + elt.sectorID) 0

All the heavy lifting has already been done by the time we get to Seq.filter. I chose to go with Seq.fold instead of Seq.reduce because the latter can fail with an ArgumentException when the sequence is empty.

When you run this function on the input file, you get 158835, which is, in fact, the correct answer.

Problem - Part 2

For Part 2, we have to decrypt the encrypted room name using a shift cipher.

The question we have to answer is "what is the sector ID of the room where North Pole objects are stored?"

Solution - Part 2

The changes were minimal for Part 2.

  1. Add a field to the Line record to hold the decrypted text.
  2. Write a shift cipher.
  3. Tie it all together.

Modify the data structure

I added the last field to the record - decryptedText.

type Line = {
  line: string
  sectorID: int
  calculatedChecksum: string
  providedChecksum: string
  decryptedText: string
}
decryptedText
The decrypted room name. Needed to understand where the North Pole objects are being stored.

Write the shift cipher algorithm

A shift cipher, or Caesar cipher, is a relatively simple substitution cipher. Julius Caesar is widely credited as being its inventor. The key to the Caesar cipher is knowing two things:

  1. The space through which we have to shift (e.g. only lowercase letters, upper and lowercase letters, the entire ASCII table, etc.)
  2. The number of places to shift within the space.

So, I made some assumptions to guide the development of this algorithm.

  1. I restricted the space to lowercase letters only. The single example provided by the problem bears out this assumption.
  2. The shift count is the sector ID.
  3. The algorithm should not shift dashes, but just convert them directly to spaces.
let shiftCipher (letter: char) shift =
  let asciiStart = 97
  let numChars = 26
  let charToInt x = (int x) - asciiStart
  let intToChar x = char (x + asciiStart)
  if letter = '-' then ' '
  else letter |> charToInt |> (+) shift |> (fun x -> x % numChars) |> intToChar

Tie it all together

The function that tied together the solution for Part 2 went through a few iterations and makes at least one large assumption.

  1. The initial part of the algorithm is similar to Part 1, since our starting point is the list of valid rooms.
  2. Then, I calculated the decrypted name for each room.
  3. Finally, I settled on a big assumption that the room storing the "North Pole objects" would start with the word "north".
    • This assumption turned out to be correct, obviously.
    • I also tried other variations, such as 'north' in the text, 'North' in the text, 'North Pole' in the text, etc.
    • This actually affected my shift cipher algorithm, since capital letters change the shift space.
let day4part2 =
  lines puzzleInput
  |> extractSectorIDs
  |> extractProvidedChecksums
  |> calculateChecksums
  |> Seq.filter (fun x -> x.calculatedChecksum = x.providedChecksum)
  |> Seq.map
    (fun l ->
    {l with
      decryptedText =
      (Regex.Match (l.line, @"([a-zA-Z]+\-)+")).Groups.[0].Value
      |> Seq.map (fun elt -> shiftCipher elt l.sectorID)
      |> System.String.Concat
    })
  |> Seq.filter (fun l -> l.decryptedText.StartsWith("north"))

When you calculate day4part2, you get sector ID 993, which is the correct answer.

Testing

This is the first AOC problem where I introduced testing, something that was long overdue. I did not use any framework, but created a separate script file that contained basic unit tests. These tests printed their results to the console and were quite crude (I calculated the results manually and then turned those results into unit tests).

Despite how simple the tests were, they cut down the trial and error time considerably. I especially felt the impact on this problem where I kept hitting roadblocks every step of the way.

Lessons Learned

I learned a few lessons from this exercise.

  1. Creating separate functions for different pieces of the solution was a good idea and allowed for a lot of reusability.
    • I will definitely be continuing this trend in the future.
  2. The semi-automated testing, as crude as it was, helped immensely.
    • This is even easier for AOC since we have specific examples given with each Part of each problem.
    • I definitely need to put even more effort into testing in the future.

See you next time!

AOC 2016 - Day 3

Table of Contents

AOC 2016 - Day 3

Problem statement on Advent of Code website.

Code for this post can be found on GitHub.

Background

  • On Day 1, we located Easter Bunny headquarters.
  • On Day 2, we broke the code to use the bathroom in Easter Bunny HQ.

Problem - Part 1

On Day 3, we are walking through a design department and see a list values specifying various triangles. Our job is to be a good citizen and help the design department by identifying the triangles which are "possible".

Solution - Part 1

The algorithm which determines whether a triangle is "possible" is stated as follows:

In a valid triangle, the sum of any two sides must be larger than the remaining side.

I rephrased this for myself as follows:

In a valid triangle, the sum of the two smaller sides must be larger than the largest side.

The steps of the solution are as follows:

  1. Parse each line of the input file into 3 integers
    • This is the first problem where I broke down and finally learned how to parse an input file.
    • The problem input was 1,902 lines.
    • I did not want to copy those lines into my source file.
  2. Filter the list of triangles by removing those which are not possible.
  3. Calculate the length of the list.

Some choices I made up-front:

  • Based on experience with the previous two problems, I assumed that some part of the problem would change.
  • My guess was that it would either be the input or the way we determine valid triangles.
  • Thus, I parameterized the triangle algorithm.
  • I thought that if the input changes (specifically, the input file), I would go back and parameterize that as well.

Save the input

For Step 1, I started by creating an input file.

Validate a triangle

I wrote a small function to determine whether a triangle is valid or not.

let possibleTriangle ptr =
  ptr
  |> Seq.sort
  |> fun x -> (Seq.item 0 x) + (Seq.item 1 x) > (Seq.item 2 x)

Parse and filter the list of triangles

The largest part of the solution was to write a function to:

  1. Read the file
  2. Parse the values
  3. Filter the list to remove invalid triangles
let possibleTrianglesCount triangleEvaluator =
  File.ReadLines @"./puzzle_input"
  |> Seq.map
    ((fun line -> Regex.Matches (line, @"[0-9]+"))
    >> Seq.cast
    >> Seq.map
      (fun (x : System.Text.RegularExpressions.Match) -> x.Value |> int)
    )
  |> Seq.filter triangleEvaluator

I like the fact that the 3 steps needed to perform this part of the job are so obviously mapped to the source code:

  1. Read the file ==> File.ReadLines
  2. Parse the file and turn the values into ints ==> Seq.map
  3. Filter the list ==> Seq.filter

Get the count of valid triangles

The last step was to connect possibleTriangle to possibleTrianglesCount.

let day3part1 =
  possibleTrianglesCount possibleTriangle
  |> Seq.length

I deliberately kept the summarization step separate from the filtering action on the off-chance that the problem for Part 2 would ask me to do something different with the list of valid triangles (oh, how wrong I was!).

This function, when executed on the input, gives a value of 982, which is the correct answer.

Problem - Part 2

Part 2 threw in a twist that I did not expect. It changed the way that the program has to interpret the input file:

  • Even though the input file is organized in 3 columns of numbers, values in each row are unrelated to each other
  • Instead, the data must be read in column-order.

For example, if this is the input file with just 9 numbers:

101 301 501
102 302 502
103 303 503

Then the three triangles are:

  • 101, 102, 103
  • 301, 302, 303
  • 501, 502, 503

Solution - Part 2

My goal for the solution to Part 2 was to try and re-use as much code as possible. The first, obvious candidate for re-use was the possibleTriangle function. Unfortunately, I could not re-use the parsing code, since that code was embedded in the possibleTrianglesCount function.

Parse and filter the list of triangles

To parse and filter the list of triangles, I chose the following steps:

  1. Parse file into ints
  2. Transform input from 3 columns of ints into 1 longer column
  3. Group values into seqs of 3
  4. Filter the list
let possibleVerticalTrianglesCount triangleEvaluator =
  (* Turn 3 columns of ints into 1 column *)
  let colOfInts ints =
    ints
    |> Seq.map (Seq.item 0)
    |> Seq.append (ints |> Seq.map (Seq.item 1))
    |> Seq.append (ints |> Seq.map (Seq.item 2))
  (* Read the data, serialize it, re-group it, then filter using evaluation function *)
  File.ReadLines @"./puzzle_input"
  |> Seq.map
    ((fun line -> Regex.Matches (line, @"[0-9]+"))
    >> Seq.cast
    >> Seq.map
      (fun (x : System.Text.RegularExpressions.Match) -> x.Value |> int)
    )
  |> colOfInts
  |> Seq.chunkBySize 3
  |> Seq.filter triangleEvaluator

Thanks to F#'s OOTB functions in the Seq module, the only real change compared to the previous function was adding the part to change columns of 3 integers into a single column of integers.

Get the count of valid triangles

The last step was to invoke the new function.

let day3part2 =
  possibleVerticalTrianglesCount possibleTriangle
  |> Seq.length

This function produces a value of 1826, which is the correct answer.

Lessons Learned

From Day 3, I picked up a few more lessons learned.

  1. Parameterize everything, since there is almost no other way to really have re-use in these problems.
  2. Write more tests!!!
    1. Writing the code to turn a list of 3 columns into 1 took quite a bit of trial and error in F# interactive, and having automated tests, either with or without intermediate outputs, would have sped up the process greatly.
    2. This is something I noted before, on the Day 2 blog post.
    3. Obviously, I didn't learn my lesson while solving the Day 3 problem.

See you next time!

10 April 2017

AOC 2016 - Day 2 Alternate Solutions

Table of Contents

AOC 2016 - Day 2 Alternate Solutions

Problem on AOC website.

Code for this post can be found on GitHub.

This post is a follow-up to my last post on my solution for AOC Day 2 and how I was unhappy with the design (though my initial results were still correct).

Since that time, I have implemented a set of five graph data structures to make the solution more robust than simply encoding the minimum solution with a function.

These data structures have a few advantages:

  • The data types are much more robust - for the board and the graphs. Instead of talking in terms of raw numbers / strings, I can now speak in terms of Vertices and Edges.
  • The solution's design allows for the underlying data structure to be swapped out as long as we can provide implementations of two key functions - create and getNext.
  • Different graph structures can be compared in terms of (basic) performance. I will provide my numbers at the end of this blog.

Modeling a board

Code on GitHub

Storing a board in a text file

First, I changed the way that boards are stored. Rather than hard-coding the board or worse, encoding the representation directly into the algorithm with no easy way to change it, I picked a very simple text-based format.

Blank spaces are represented by dots / periods (.). All other characters represent a unique Vertex.

For day 2, part 1, the following board is stored in a text file.

123
456
789

Similarly, here is the day 2, part 2 board:

..1..
.234.
56789
.ABC.
..D..

Boards are represented internally as a set of vertices and edges. Let's look at those in more detail.

Vertices

A Vertex is a tuple consisting of an integer accompanied by a string label. Here are the type and module signatures for Vertex.

type Vertex =
  | V of int * string
  with
    override ToString : unit -> string
  end
module Vertex = begin
  val create : idx:int -> label:string -> Vertex
  val toInt : _arg1:Vertex -> int
  val toString : x:Vertex -> string
  val strToV : lbl:string -> (seq<Vertex> -> Vertex)
  val intToV : idx:int -> (seq<Vertex> -> Vertex)
end

Here are the expected properties of a Vertex.

  • Each Vertex must be represented by a unique integer.
  • Each Vertex must have a unique string label (for strToV to work correctly).
  • While not strictly required, the on-screen display for certain graph data structures is much prettier if each string label has a length of 1 (aka a single character).

All the properties listed above are not enforced by the data type. However, some properties are enforced by the Board creation algorithm.

Edges

The AOC Day 2 problem requires directed graphs. Thus, an edge is stored as a pair of vertices and a direction.

We have four directions in the AOC problem - Right, Left, Up, and Down.

Direction also has both a type and an accompanying module:

type Direction =
  | R
  | L
  | U
  | D
  with
    override ToString : unit -> string
  end
module Direction = begin
  val opposite : _arg1:Direction -> Direction
  val toDirection : _arg1:string -> Direction
end

As I was working on the alternate solutions for Day 2, I added certain functions to various modules as I was writing the graph structures. However, in certain cases, I did not require those functions in the final solution but still left them in the module. A good example of this is the opposite function in the Direction module.

The Edge type and module are as follows:

type Edge =
  | E of Vertex * Direction * Vertex
  with
    override ToString : unit -> string
  end
module Edge = begin
  val create : dir:Direction -> v1:Vertex * v2:Vertex -> Edge
  val toString : e:Edge -> string
  val fromV : Edge -> Vertex
  val toV : Edge -> Vertex
  val direction : Edge -> Direction
end

fromV, direction, and toV represent the three individual components of an Edge.

Some properties of an Edge:

  • Edges are defined solely by the two vertices they connect and the direction of the connection. They have no other unique identifiers (internal or external).

Building the board

Now that all the building blocks are in place, we can build the Board. The type and module for Board are as follows.

type Board =
  {vertices: seq<Vertex>;
    edges: seq<Edge>;}
  with
    override ToString : unit -> string
  end
module Board = begin
  val transpose : rows:seq<#seq<'b>> -> seq<seq<'b>>
  val validEdge : l1:string * l2:string -> bool
  val potentialEdgesByRow :
    verts:seq<Vertex> -> rows:seq<#seq<string>> -> seq<Vertex * Vertex>
  val reverse : x:'a * y:'b -> 'b * 'a
  val squareup : strs:seq<seq<string>> -> seq<seq<string>>
  val parseBoard : strB:string -> Board
end

Most of the functions for the Board module are internal functions and should not be invoked by an external client. The most important function in the module is parseBoard, which takes in a string representing the board (e.g. the text files I mentioned earlier) and returns a constructed Board that meets a number of requirements.

  • Boards are two-dimensional.
  • Each character in the string representation that is not a blank space is turned into a unique vertex.
  • Each vertex is given a unique integer ID.
  • Boards do not contain diagonal edges.
  • Each pair of neighboring vertices has two edges between them.
  • Given two neighboring vertices, the two edges between them have opposite directions.

Generic solution framework

The solution performs the following steps to get to the final answer for the problem.

  1. Create a Board from the boardFile.
  2. Use that Board to create a graph using bCreateF.
  3. Translate the instructions from the instrFile into Directions.
  4. Take each line of instructions and run them through the graph. The start Vertex for each line of instructions is the result from the previous line of instructions, except for the first line of instructions which uses Vertex "5" as its start Vertex.
  5. Turn the result from each line of instructions into a string, then concatenate them.

The solution framework has two functions, moveAll and day2part1. The former uses bGetNextF to move through a line of instructions. The latter is the connector that converts a board and lines of instructions into a final answer.

The solution framework's signature is as follows.

module Solution = begin
  val moveAll :
    func:(Vertex -> 'a -> Vertex) ->
      startv:Vertex -> instrs:seq<'a> -> Vertex
  val day2part1 :
    boardFile:string ->
      instrFile:string ->
        bCreateF:(Board -> 'a) ->
          bGetNextF:('a -> Vertex -> Direction -> Vertex) -> string
end

Graph data structures

The graph data structures below are admittedly naively implemented, except inductive graphs which make use of the Hekate library. However, they all follow certain rules:

  • Each data structure's type is hidden within its respective module.
  • Once a graph is created, it is not modified in any way.
  • If the getNext function cannot find a move in the given direction from the given source vertex, it will return the source vertex to the caller.

Adjacency Matrix

Code on GitHub.

Per Wikipedia, an adjacency matrix is "a square matrix used to represent a finite graph".

Since the AOC Day 2 implementation requires a directed graph, the adjacency matrix cannot be a symmetric matrix. For my implementation, the label for each row represents the "from Vertex", the label for each column represents the "to Vertex" and the value at their intersection represents the Direction of movement.

For example, when looking at the Day 2, Part 1 board below, you can read the first entry as "When you start from Vertex 1 and go Right, you arrive at Vertex 2".

Here is the text representation of the Day 2, Part 1 board as an adjacency matrix.

  123456789
1 .R.D.....
2 L.R.D....
3 .L...D...
4 U...R.D..
5 .U.L.R.D.
6 ..U.L...D
7 ...U...R.
8 ....U.L.R
9 .....U.L.

And here is the text representation of the Day 2, Part 2 board.

  123456789ABCD
1 ..D..........
2 ..R..D.......
3 UL.R..D......
4 ..L....D.....
5 .....R.......
6 .U..L.R..D...
7 ..U..L.R..D..
8 ...U..L.R..D.
9 .......L.....
A .....U....R..
B ......U..L.RD
C .......U..L..
D ..........U..

Internally, an adjacency matrix is stored as an Array2D [,]. The scheme used to create this data structure is somewhat fragile because it assumes that the first Vertex has a unique integer ID of 0 and that subsequent vertices' IDs are incremented deterministically without gaps. Since we control Board and Vertex creation, we can rely on this assumption for now but it would be a dangerous assumption to make in production code.

The getNext function takes the following steps to move through the board:

  1. Use the 2D array to find the row representing the from Vertex.
  2. Once found, go through the row and looks for the desired Direction.
  3. If found, use that column index to go from an integer to a Vertex using Board.vertices.
  4. If not found, return the from Vertex to the caller.
let getNext am from dir =
  match am with
  | AM(x, b) ->
    let fromInt = Vertex.toInt from
    let colBase = Array2D.base2 x
    x.[fromInt..fromInt,colBase..]
    |> Seq.cast<Direction option>
    |> Seq.tryFindIndex (( = ) (Some dir))
    |> function
      | Some idx -> Seq.item idx b.vertices
      | None -> from

Edge List

Code on GitHub.

An edge list is an extremely simple graph implementation which does not transform the original Board's internal structures in any way. It is, as the name implies, an exhaustive list of all edges in the graph.

Here is a visual representation of the Day 2, Part 1 board.

Edges: ["4->U->1"; "7->U->4"; "5->U->2"; "8->U->5"; "6->U->3"; "9->U->6"; "1->D->4";
 "4->D->7"; "2->D->5"; "5->D->8"; "3->D->6"; "6->D->9"; "1->R->2"; "2->R->3";
 "4->R->5"; "5->R->6"; "7->R->8"; "8->R->9"; "2->L->1"; "3->L->2"; "5->L->4";
 "6->L->5"; "8->L->7"; "9->L->8"]

And the Day 2, Part 2 board.

Edges: ["6->U->2"; "A->U->6"; "3->U->1"; "7->U->3"; "B->U->7"; "D->U->B"; "8->U->4";
 "C->U->8"; "2->D->6"; "6->D->A"; "1->D->3"; "3->D->7"; "7->D->B"; "B->D->D";
 "4->D->8"; "8->D->C"; "2->R->3"; "3->R->4"; "5->R->6"; "6->R->7"; "7->R->8";
 "8->R->9"; "A->R->B"; "B->R->C"; "3->L->2"; "4->L->3"; "6->L->5"; "7->L->6";
 "8->L->7"; "9->L->8"; "B->L->A"; "C->L->B"]

The getNext function for an edge list is quite simple as well.

let getNext (EL(b)) from dir =
  let destv =
    Seq.tryFind
      (fun (E(v1,d,v2)) -> v1 = from && d = dir)
      b.edges
  match destv with
  | Some(E(_,_,v2)) -> v2
  | None -> from

Adjacency List

Code on GitHub

As opposed to an edge list, an adjacency list takes a Vertex-centric approach to representing graphs. Many implementations of adjacency lists internally use a data structure like a hashmap or hashtable, where the key is a Vertex and the value is a list of vertices (possibly with additional data) that the key can connect to.

For my implementation, I used two separate data structures to implement the adjacency lists - dict and Map. The keys are Vertex instances and the values are lists of Edges.

Here is a visual representation of the Day 2, Part 1 board.

1==>1->D->4, 1->R->2,
2==>2->D->5, 2->R->3, 2->L->1,
3==>3->D->6, 3->L->2,
4==>4->U->1, 4->D->7, 4->R->5,
5==>5->U->2, 5->D->8, 5->R->6, 5->L->4,
6==>6->U->3, 6->D->9, 6->L->5,
7==>7->U->4, 7->R->8,
8==>8->U->5, 8->R->9, 8->L->7,
9==>9->U->6, 9->L->8,

Here is the Day 2, Part 2 board.

1==>1->D->3,
2==>2->D->6, 2->R->3,
3==>3->U->1, 3->D->7, 3->R->4, 3->L->2,
4==>4->D->8, 4->L->3,
5==>5->R->6,
6==>6->U->2, 6->D->A, 6->R->7, 6->L->5,
7==>7->U->3, 7->D->B, 7->R->8, 7->L->6,
8==>8->U->4, 8->D->C, 8->R->9, 8->L->7,
9==>9->L->8,
A==>A->U->6, A->R->B,
B==>B->U->7, B->D->D, B->R->C, B->L->A,
C==>C->U->8, C->L->B,
D==>D->U->B,

The getNext implementations for both the dict and Map versions are very similar, only differing in how the various values are accessed.

First, here is the getNext implementation for the dict-version of adjacency lists.

let getNext (AL(d,_)) from dir : Vertex =
  let es = d.Item from
  match Seq.tryFind (fun (E(_,d,_)) -> dir = d) es with
  | Some (E(_,_,v2)) -> v2
  | None -> from

And, similarly, here is the Map-version of getNext.

let getNext (AL(d,_)) from dir =
  let es = Map.find from d
  match Seq.tryFind (fun (E(_,d,_)) -> dir = d) es with
  | Some (E(_,_,v2)) -> v2
  | None -> from

Inductive Graph

Code on GitHub.

Finally, I used an inductive graph library, Hekate, as my final representation of a graph in F#. As I noted in my last blog post, inductive graphs were introduced by Erwig in his 2001 paper and then implemented (first) as the Haskell fgl library.

Inductive graphs are functional data structures that allow similar operations to other inductive data structures such as lists and trees.

Despite using a library here instead of implementing the data structure myself, I actually enjoyed writing code with this library. The authors have done a great job of using familiar syntax and patterns with Hekate. The only downside I could find is that the Hekate library is almost completely undocumented. I learned how to use the library from the unit tests I found on GitHub and from reading Erwig's original paper.

Here is the Day 2, Part 1 board represented visually as an inductive graph.

map
  [(V (0,"1"),
    (map [(V (1,"2"), L); (V (3,"4"), U)], "1",
     map [(V (1,"2"), R); (V (3,"4"), D)]));
   (V (1,"2"),
    (map [(V (0,"1"), R); (V (2,"3"), L); (V (4,"5"), U)], "2",
     map [(V (0,"1"), L); (V (2,"3"), R); (V (4,"5"), D)]));
   (V (2,"3"),
    (map [(V (1,"2"), R); (V (5,"6"), U)], "3",
     map [(V (1,"2"), L); (V (5,"6"), D)]));
   (V (3,"4"),
    (map [(V (0,"1"), D); (V (4,"5"), L); (V (6,"7"), U)], "4",
     map [(V (0,"1"), U); (V (4,"5"), R); (V (6,"7"), D)]));
   (V (4,"5"),
    (map [(V (1,"2"), D); (V (3,"4"), R); (V (5,"6"), L); (V (7,"8"), U)], "5",
     map [(V (1,"2"), U); (V (3,"4"), L); (V (5,"6"), R); (V (7,"8"), D)]));
   (V (5,"6"),
    (map [(V (2,"3"), D); (V (4,"5"), R); (V (8,"9"), U)], "6",
     map [(V (2,"3"), U); (V (4,"5"), L); (V (8,"9"), D)]));
   (V (6,"7"),
    (map [(V (3,"4"), D); (V (7,"8"), L)], "7",
     map [(V (3,"4"), U); (V (7,"8"), R)]));
   (V (7,"8"),
    (map [(V (4,"5"), D); (V (6,"7"), R); (V (8,"9"), L)], "8",
     map [(V (4,"5"), U); (V (6,"7"), L); (V (8,"9"), R)]));
   (V (8,"9"),
    (map [(V (5,"6"), D); (V (7,"8"), R)], "9",
     map [(V (5,"6"), U); (V (7,"8"), L)]))]

And here is the Day 2, Part 2 board as an inductive graph. Please note that F# Interactive actually truncated the print out. I am assuming it did this due to the size of the map.

map
  [(V (0,"1"), (map [(V (2,"3"), U)], "1", map [(V (2,"3"), D)]));
   (V (1,"2"),
    (map [(V (2,"3"), L); (V (5,"6"), U)], "2",
     map [(V (2,"3"), R); (V (5,"6"), D)]));
   (V (2,"3"),
    (map [(V (0,"1"), D); (V (1,"2"), R); (V (3,"4"), L); (V (6,"7"), U)], "3",
     map [(V (0,"1"), U); (V (1,"2"), L); (V (3,"4"), R); (V (6,"7"), D)]));
   (V (3,"4"),
    (map [(V (2,"3"), R); (V (7,"8"), U)], "4",
     map [(V (2,"3"), L); (V (7,"8"), D)]));
   (V (4,"5"), (map [(V (5,"6"), L)], "5", map [(V (5,"6"), R)]));
   (V (5,"6"),
    (map [(V (1,"2"), D); (V (4,"5"), R); (V (6,"7"), L); (V (9,"A"), U)], "6",
     map [(V (1,"2"), U); (V (4,"5"), L); (V (6,"7"), R); (V (9,"A"), D)]));
   (V (6,"7"),
    (map [(V (2,"3"), D); (V (5,"6"), R); (V (7,"8"), L); (V (10,"B"), U)], "7",
     map [(V (2,"3"), U); (V (5,"6"), L); (V (7,"8"), R); (V (10,"B"), D)]));
   (V (7,"8"),
    (map [(V (3,"4"), D); (V (6,"7"), R); (V (8,"9"), L); (V (11,"C"), U)], "8",
     map [(V (3,"4"), U); (V (6,"7"), L); (V (8,"9"), R); (V (11,"C"), D)]));
   (V (8,"9"), (map [(V (7,"8"), R)], "9", map [(V (7,"8"), L)])); ...]

The getNext algorithm is relatively simple, considering that each Vertex stores information about both its predecessors and successors, i.e. what points to the Vertex and what the Vertex points to, respectively.

let getNext ig from dir =
  match Graph.Nodes.successors from ig with
  | None -> from
  | Some succs ->
    succs
    |> List.tryFind (fun (_,d) -> d = dir)
    |> function
      | None -> from
      | Some (dest,_) -> dest

Testing

Code on GitHub.

In the past, I have struggled quite a bit with properly implementing FsCheck tests. However, this time around, the combination of using FsCheck directly (as opposed to using it in combination with a testing library like Fuchu or Xunit) and using it from F# script files (as opposed to compiled programs) made the experience much more pleasant and was a great learning experience.

I wrote tests using FsCheck to ensure that my implementations were correct - and I'm glad I did. I found a number of elementary mistakes by having automated tests that I could easily run after each change to validate my results. For each data structure, I wrote 6 tests:

  1. A printout of the Day 2, Part 1 board (to be verified manually).
  2. A printout of the Day 2, Part 2 board (to be verified manually).
  3. The Day 2, Part 1 test provided in the AOC problem description.
  4. The Day 2, Part 2 test provided in the AOC problem description.
  5. The Day 2, Part 1 problem stated in the AOC problem description.
  6. The Day 2, Part 2 problem stated in the AOC problem description.

I could not automate the first two tests because each data structure's printout was quite different from the others.

I was able to implement the last two tests because I had already solved Day 2's problems and knew the correct answers.

Performance

Raw data on GitHub - requires a program that can read XLSX files.

After writing the five graph data structure implementations, I decided to run some basic performance tests on them. Having a generalized solution framework allowed me to attribute all differences in runtimes to the specific data structure being used.

To perform the tests in the most "unbiased" way possible, I ran each test 5 times and took the average of the results. For each run, I executed the last 4 tests listed in the Testing section.

Without further ado, here are the results from using F# interactive's #time directive.

Average run-time and garbage collection performance of the algorithms, sorted by the Real average column in ascending order.
Algorithm Real average CPU average Gen0 average Gen1 average Gen2 average
Adjacency List Dict 0.8452 0.8326 104.2 25.2 0
Adjacency List Map 0.8684 0.8576 105.8 21.6 0
Inductive Graph 0.9894 0.9852 136.2 33 0
Adjacency Matrix 4.4932 4.4798 530.6 78.8 0.6
Edge List 359.2024 359.1448 68896.6 61.4 3.6

I then took the Adjacency List Dict implementation as the baseline (since it was the fastest) and translated the same table into percentages.

Average run-time and garbage collection performance as a percentage, with Adjacency List Dict as the baseline.
Algorithm Real CPU Gen0 Gen1 Gen2
Adjacency List Dict 100% 100% 100% 100% -
Adjacency List Map 103% 103% 102% 86% -
Inductive Graph 117% 118% 131% 131% -
Adjacency Matrix 532% 538% 509% 313% 100%
Edge List 42499% 43135% 66120% 244% 600%

Observations

I was not surprised to find that the Edge List was the worst performer. However, I was surprised by how much worse its performance was, even on a small board, than the next worst algorithm, the Adjacency Matrix.

Along those same lines, I was surprised by how poor the performance of the Adjacency Matrix was. However, I have a feeling that a more optimized implementation could do much better than my naive attempt. I believe my observation (as to my poor Adjacency Matrix writing skills) is accurate considering that it, along with the Adjacency List, is one of the most popular data structures for storing graphs.

The inductive graph performed very well for a relatively new data structure that was intended, from the beginning, to be a new way of storing graphs in functional languages. Its run-time performance was approximately 17% worse than the baseline and memory performance (based on garbage collection) was approximately 31% worse than the baseline. For someone who needs a graph data structure for more than just a getNext function, it could be a serious contender and warrants additional testing.

Next steps

I am satisfied with the results of this investigation into graph data structures in F#. I was able to implement all algorithms in a functional manner within a generic framework. I believe I have accomplished the goal that I set out with, which was to find a more robust and 'realistic' way of representing graph-like structures in F#.

However, here are some items that I could not (or did not) complete and may be worth looking into:

  • Change the base data structures to enforce more of the expected properties / invariants.
  • Make the types for Vertex, Edge, Direction, etc. private and move them within their respective modules.
  • Test with larger / more complex boards to better understand performance.
  • Change the way boards are parsed from text files so that when the same character appears multiple times on a board, it is treated as the same Vertex (allowing for more complex board structures).
  • Change boards to allow 3D representations.
  • Remove copying from Adjacency Matrix's create function.
  • Implement (or find existing libraries) and test more functions of graph data structures.

I will now be returning to blogging about my solutions for Advent of Code 2016 problems. I am greatly looking forward to this because I have temporarily stopped solving more problems until I catch up with my blog posts. Hopefully, I will be able to post my Day 3 solutions in the next week.

See you next time!