Posted in:

Today’s Advent of Code puzzle had us concatenating and reversing strings (inspired by the dragon curve).  Obviously neither is particularly hard to do, but there was some obvious potential for optimisation, since the strings consisted only of 1s and 0s, and the strings could get extremely long. So I suspected that part b of today’s puzzle could force me to rework some code.

However, the usual rules apply of premature optimization. First get it working, then make it fast. So again I opted for an outside in approach, and using the test cases in the puzzle description to validate my work.

So the top-level solve function just needed to “expand” the input to a target size, and then calculate the checksum.

let solve initialState diskSize =
    let expanded = expand initialState diskSize
    checkSum expanded

The expand function itself was recursive, we keep expanding until we reach the target size:

let rec expand (initial:string) targetSize =
    if initial.Length >= targetSize then
        initial.Substring(0,targetSize)
    else
        expand (expandOnce initial) targetSize

And I factored out expandOnce to make running the test cases easier. I used a StringBuilder with a pre-calculated length as an attempt at making this at least a little bit more performant for a very long string.

let rec expandOnce (input:string) =
    let len = input.Length
    let sb = System.Text.StringBuilder(input, 1 + len * 2)
    sb.Append('0') |> ignore
    let flip c = if c = '1' then '0' else '1'
    [ for n in 1..len -> flip input.[len-n] ]
        |> Seq.iter (sb.Append >> ignore)
    sb.ToString()

The checkSum function followed a similar pattern. It was recursive, calling down into a checkSumOnce function. This one also has potential for optimization, but the easy way was to use Seq.chunkBySize to decide if each pair of characters matched or differed.

With the test cases passing, I was able to solve both parts a and b easily:

solve "11110010111001001" 272 |> printfn "part a: %s"
solve "11110010111001001" 35651584 |> printfn "part b: %s"

Part a ran in 2ms, and part b in 24 seconds. I decided to see if I could improve on that a bit, and in expandOnce I changed the for loop to not create a temporary list which got part b down to 15 seconds. Here’s the faster version of expandOnce:

let append (sb:StringBuilder) (c:char) = sb.Append (c) |> ignore

let rec expandOnce (input:string) =
    let len = input.Length
    let sb = StringBuilder(input, 1 + len * 2)
    append sb '0'
    for n in 1..len do 
        append sb (if input.[len-n] = '1' then '0' else '1')
    sb.ToString()

But it turns out that the checksum calculation was taking a lot of time as well. A quick change to use StringBuilder there as well brought part b down to a fairly respectable 0.5s. Here’s the optimized checkSumOnce:

let checkSumOnce (input:string) =
    // assume even length input
    let csLen = input.Length / 2
    let sb = StringBuilder(csLen)
    for n in 0..csLen-1 do
        append sb (if input.[n*2] = input.[n*2+1] then '1' else '0')
    sb.ToString()

Obviously on the reddit solution thread, there were some even more aggressive optimizations on display, but this goes to show just how significant a performance increase is possible with a few small changes. It’s also worth saying that in functional languages like F#, there are times when allowing some mutable state will vastly speed things up. In this example, we’ve been able to speed up the expandOnce and checkSumOnce functions using a StringBuilder, but managed to keep both of those functions “pure” – they have no side effects, they don’t access global state, change their inputs, and always will return the same output given the same input. So I still feel this solution stays within the spirit of “functional programming”

My day 16 solution available on GitHub.