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
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()
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
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
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
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.