Today’s Advent of Code challenge brought back memories of the day 6 puzzle from last year. In one sense, it was a typical Advent of Code challenge – parse the input into a sequence of instructions, work out how to apply each instruction, and then apply all the instructions on the input data.

The parsing could quite easily have been done with a bit of string splitting, but last year, but I really have been meaning to start making more use of “Active Patterns” in F#, a technique Sehnsucht put me onto last year.

And so I decided that the regular expression matching and int parsing would be done with active patterns. Here’s how I used them to parse instructions into an Instruction discriminated union:

open System.Text.RegularExpressions

type Instruction = Rect of int*int | RotateRow of int*int | RotateCol of int*int

let (|Matches|) pattern =
  let rgx = Regex (pattern, RegexOptions.Compiled)
  fun input -> [for m in rgx.Matches input do for g in m.Groups -> g.Value]

let (|Int|_|) str = match System.Int32.TryParse str with true, value -> Some value | _ -> None

let parseInstruction = function 
    | Matches @"rect (\d+)x(\d+)" [_; Int width; Int height] -> Rect(width,height)
    | Matches @"rotate row y\=(\d+) by (\d+)" [_; Int row; Int steps] -> RotateRow(row,steps)
    | Matches @"rotate column x\=(\d+) by (\d+)" [_; Int row; Int steps] -> RotateCol(row,steps)
    | x -> failwith ("parseError " + x)
let instructions = System.IO.File.ReadAllLines (__SOURCE_DIRECTORY__ + "\\input.txt") |> Array.map parseInstruction

To keep track of the state of each light, there were a lot of possible data structures. I opted simply for a 2D array of integers (could have been booleans, but integers allowed me to count lights on by summing the array). I would then create three functions to apply each of the instructions to the array.

Now this problem could be perfectly easily solved by mutating the array in place, although rotating a row or column is a bit of a pain to do in place. So I decided to make more “functional” instruction appliers by making them return a new 2D array with the relevant changes:

let rect (width,height) (state:int[,]) = 
    let out = Array2D.copy state
    for w in 0..width-1 do
        for h in 0..height-1 do
            out.[h,w] <- 1

let rotateRow (row,steps) (state:int[,]) = 
    let out = Array2D.copy state
    let rowLength = Array2D.length2 state
    for w in 0..rowLength-1 do
        out.[row,(w+steps)%rowLength] <- state.[row,w]
let rotateCol (col,steps) (state:int[,]) = 
    let out = Array2D.copy state
    let colLength = Array2D.length1 state
    for w in 0..colLength-1 do
        out.[(w+steps)%colLength,col] <- state.[w,col]

There is a performance cost to copying the arrays, but for the size of array and number of instructions it’s not a big deal.

Now we can make a folder function that applies each instruction, and use Array.fold to apply it onto a starting empty array. Then we use the Seq.cast trick to flatten the 2D array into a sequence of all elements in all rows, and sum them.

let applyInst (state:int[,]) = function
    | Rect(a,b) -> rect (a,b) state
    | RotateRow(a,b) -> rotateRow (a,b) state
    | RotateCol(a,b) -> rotateCol (a,b) state

    |> Array.fold applyInst (Array2D.create 6 50 0) 
    |> Seq.cast<int> 
    |> Seq.sum 
    |> printfn "Part a: %d"

Now the second part of the puzzle was great. You simply had to visualize your LCD display to read off the code shown by the lights. Obviously there were a number of ways to do this, including by just printing to the console.

But I did two simple visualizations. First, I drew it using WPF. I created a canvas and added a rectangle for each on pixel, and used a render transform to increase the size:

#r "PresentationCore.dll"
#r "PresentationFramework.dll"
#r "System.Xaml.dll"
#r "UIAutomationTypes.dll"
#r "WindowsBase.dll"

open System.Windows
open System.Windows.Media
open System.Windows.Media.Imaging
open System.Windows.Shapes
open System.Windows.Controls

let drawState (state:int[,]) scale =
    let width = Array2D.length2 state
    let height = Array2D.length1 state
    let canvas = new Canvas(Background=Brushes.DarkGreen,
                            RenderTransform=ScaleTransform(ScaleX = scale, ScaleY = scale),
                            Width = (float width),
                            Height = (float height),
                            HorizontalAlignment = HorizontalAlignment.Left,
                            VerticalAlignment = VerticalAlignment.Top
    for x in {0..width-1} do
        for y in {0..height-1} do
            if state.[y,x] = 1 then 
                let p = Rectangle(Width=1.0,Height=1.0,Fill=Brushes.Lime)
                canvas.Children.Add(p) |> ignore
                Canvas.SetLeft(p, float x)
                Canvas.SetTop(p, float y)
    printfn "%f %f" canvas.Width canvas.Height    

let scaleFactor = 10.0
let canvas = drawState endState scaleFactor
let window = Window(Title ="Advent of Code", Content=canvas, 
                    Width = 20.0 +  canvas.Width * scaleFactor, Height = 40.0 + canvas.Height * scaleFactor)

This gives us a visualization like this:


Obviously if we wanted to be really fancy we could use a timer, and animate the full sequence as we process each instruction. There were some fantastic visualizations from the community on Reddit.

One thing I didn’t like about my solution was that the code wasn’t calculated programmatically. I did wonder whether I could use an OCR library, or even send the image off to Microsoft Cognitive Services to OCR it. I think it would work, although the code I wrote to make a bitmap made an image that cognitive services rejected for being too small. Here’s the code to turn the puzzle output into a bitmap with WinForms though:

open System.Windows.Forms
open System.Drawing

let drawState (state:int[,]) =
    let width =Array2D.length2 state
    let height = Array2D.length1 state
    let bm = new Bitmap (width, height)
    for x in {0..width-1} do
        for y in {0..height-1} do
            bm.SetPixel(x,y, if state.[y,x] = 1 then Color.Black else Color.White)

let image  = drawState endState 

This creates a tiny bitmap containing our answer


As always, there’s lots of ways my solution could be improved on, but the main thing is that I’m learning a few new techniques as I go.


Today’s Advent of Code challenge was particularly well suited to regular expressions (and reminiscent of last year’s naughty and nice strings problem). We have a list of “ip addresses” and need to test them according to some rules.

The first task was to split them out into “supernet” and “hypernet” sequences, so the string “abc[def]ghi” has two “supernet” sequences of abc and ghi and one hypernet sequence of def.

I did manage to come up with a regular expression that can find strings enclosed in square brackets, and by doing that I was able to use Regex.Split to get them into an alternating sequence of supernet, hypernet, supernet etc. So I then needed to split out every odd and even into separate sequences. I think I made a bit heavy weather of this, so do let me know if there’s a more elegant way. But here’s what I came up with:

let filterByIndex predicate sequence = 
    sequence |> Seq.indexed |> Seq.filter (fst >> predicate) |> Seq.map snd 

let parseIpAddress ipAddress =
    let parts = Regex.Split(ipAddress,@"\[(.*?)\]")
    let supernetSequences = parts |> filterByIndex (fun n -> n % 2= 0) |> Seq.toArray 
    let hypernetSequences = parts |> filterByIndex (fun n -> n % 2= 1) |> Seq.toArray
    supernetSequences, hypernetSequences

Now we needed to test each ip address. Part of this was looking for an “abba” string – two letters next to each other, with two different letters on either side. I attempted to solve this with regular expressions. “(\w)(\w)\2\1” is close but doesn’t stipulate that the inner characters are different to the outer ones. In the end I realised that it would make more sense to use Seq.windowed, which turns a sequence like “abcdef” into “abc”, “bcd”, “def” and use a pattern matching function to test for an “abba”:

let containsAbba s = s |> Seq.windowed 4 |> Seq.exists (function | [|a;b;c;d|] -> a=d&&b=c&&a<>b | _ -> false)

Now we can solve the first part of the problem by checking if there is a supernet containing an “abba” but no hypernets do:

let supportsTls ipAddress = 
    let super,hyper = parseIpAddress ipAddress
    let containsAbba s = s |> Seq.windowed 4 |> Seq.exists (function | [|a;b;c;d|] -> a=d&&b=c&&a<>b | _ -> false)
    (super |> Array.exists containsAbba) && not (hyper |> Array.exists containsAbba)

input |> Seq.filter supportsTls |> Seq.length |> printfn "Part a: %d"

Part b had a similar problem, we looked for instances of “aba” (same character repeated separated by a different character) inside of the supernets which we again could use Seq.windowed for. And then each “aba” gets turned into a “bab” by switching the inner and outer characters. Then we just need to find if the corresponding “bab” for one of the “aba”s can be found in the hypernets.

So my code for part b ended up like this:

let supportsSsl ipAddress = 
    let super,hyper = parseIpAddress ipAddress
    let findAbas s = s |> Seq.windowed 3 |> Seq.filter (function | [|a;b;c|] -> a=c&&a<>b | _ -> false) |> Seq.map System.String
    let abas = super |> Seq.collect findAbas
    let makeBab (aba:string) = sprintf "%c%c%c" aba.[1] aba.[0] aba.[1]
    let babExists bab = hyper |> Seq.exists (fun s -> s.Contains(bab))
    super |> Seq.collect findAbas |> Seq.exists (makeBab >> babExists)

input |> Seq.filter supportsSsl |> Seq.length |> printfn "Part b: %d"

Overall I feel that my solution for today could certainly be cleaned up a bit, but it does at least work, and I’m particularly proud that so far this year, I’ve entered the correct answer for each puzzle first time. I suspect its a combination of reading the question more carefully, using the example test cases, and using a functional programming language. I’ve still got nowhere near the leaderboard, but I can at least hide behind the excuse that the problems go live at 5am here, so the leaderboard is already full by the time I start the problems.


Today’s challenge was relatively kind, although this tweet from Eric Wastl makes me fear that things could be about to get tricky.

Our input is a list of strings, but what we want is a sequence of the first character from each line, then the second and so on. Sadly F# doesn’t have a direct equivalent to Python’s zip function which is perfect for this problem. I could have repurposed the rotate function I created for day 3, which rotates an array of arrays to solve this, but actually it was simpler just to iterate the input sequence multiple times picking out a letter at a different index each time.

We’re looking for the most (or least for part b) frequent character in each column of the input, and so Seq.countBy is ideal for this which returns a tuple of each character and its frequency. We can then use Seq.maxBy (or Seq.minBy for part b)

My decodePos function takes the sequence of input strings, the selector (Seq.maxBy or Seq.minBy) and the position index we are decoding:

let decodePos (messages:seq<string>) selector n =
    messages |> Seq.map (fun msg -> msg.[n]) |> Seq.countBy id |> selector snd |> fst

And now we just need to run this for each position, which we do by using the length of the first string in the list and applying decodePos to each index. Note that in F# 4, constructors are first-class functions so I can pipe the array of characters directly into the System.String constructor:

let decodeMessages (messages:string[]) selector =
    [|0..messages.[0].Length-1|] |> Array.map (decodePos messages selector) |> System.String 

Now we can use these functions to solve both parts of the problem:

let input = System.IO.File.ReadAllLines (__SOURCE_DIRECTORY__ + "\\input.txt")
decodeMessages input Seq.maxBy |> printfn "Part a: %s"
decodeMessages input Seq.minBy |> printfn "Part b: %s"

That was the code for my original solution, and you can view it on GitHub. But I wanted to try it with zip as well, so I made a poor man’s Python zip that works for string arrays:

let zip (a:string[]) =
    [| for x in 0..a.[0].Length-1 -> [| for y in a -> y.[x] |] |]

and this means we can implement decodeMessages like this:

let decodeMessages selector (messages:string[]) =
    messages |> zip |> Array.map (Seq.countBy id >> selector snd >> fst) |> System.String

Although arguably, we should make this code a bit more readable by expressing the decoding of a single character from an array of characters into its own function. Something like this:

let decodeMessages selector = 
    let decodeChar = Seq.countBy id >> selector snd >> fst
    zip >> (Array.map decodeChar) >> System.String

My alternative solution can be found here.

As always with these puzzles, there is no one “right” way to solve it. I like solutions that are succinct, readable, perform well, and easily adapted to changing requirements. But there’s usually a compromise between those constraints.


For my entry in the F# Advent Calendar we’re going to port a simple game to F#. The game is called “Asterisk”, and has very simple mechanics – you must progress through levels, avoiding hitting stars, and you can only go up or down. With each new level, three more stars appear, until it is impossible to progress any further.

It’s based on a game I used to play for hours on my dad’s BBC Micro, and I’ve implemented it a few times in various languages including C# WinForms, Silverlight and IronPython with WPF. You can find the code for some of these older versions here.


Port vs Rewrite

To get me started I decided that I would port my IronPython version to F#, since that used WPF for the graphics and collision detection, which made sense for my F# version to use.

Of course, F# is a very different language to Python. With Python I used lots of dynamic language features and mutable state. But the F# language encourages us towards strongly typed and immutable code.

Maybe things would have gone more smoothly had I rewritten from scratch in F#, but porting is what I opted for, so in this post I’ll share a few of the things I learned along the way.

WPF and F#

First of all, I needed a basic infrastructure for using WPF and the MVVM pattern in F#. I created a MVVM module to cover this:

module Mvvm
    open System
    open System.Windows
    open System.Windows.Input
    open System.Windows.Markup
    open System.Windows.Media
    open System.ComponentModel

    let checkCollisionPoint (point:Point) (control:UIElement) =
        let transformPoint = control.RenderTransform.Inverse.Transform(point)
        VisualTreeHelper.HitTest(control, transformPoint) <> null

    let loadXaml path =
        let uri = new Uri(path, UriKind.Relative)
        let stream = Application.GetResourceStream(uri).Stream
        XamlReader.Load stream

    let runApp rootElement =
        let app = new Application()
        app.Run rootElement

    type ViewModelBase() =
        let propertyChangedEvent = new DelegateEvent<PropertyChangedEventHandler>()
        interface INotifyPropertyChanged with
            member x.PropertyChanged = propertyChangedEvent.Publish

        member x.OnPropertyChanged propertyName = 
            propertyChangedEvent.Trigger([| x; new PropertyChangedEventArgs(propertyName) |])
    type DelegateCommand (action:(obj -> unit)) =
        let event = new DelegateEvent<EventHandler>()
        let mutable canExecute = true
        interface ICommand with
            member x.CanExecuteChanged = event.Publish
            member x.CanExecute arg = canExecute
            member x.Execute arg = action(arg)
        member x.SetCanExecute ce = 
            canExecute <- ce
            event.Trigger([|x; EventArgs.Empty|])

A few things of interest in here. First of all, this code demonstrates some of the techniques you can use to work with .NET events in F#, using the [<CLIEvent>] attribute, and the Publish and Trigger methods.

In the loadXaml function you can see that I decided to make my XAML files into application resources, so I needed to read them in with Application.GetResourceStream.

One of the big benefits of WPF for this game is that collision detection comes built in to the framework. We can test a point to see if it collides with a control on our canvas, which we do in checkCollisionPoint using VisualTreeHelper.HitTest.

The Game Area

The GameArea module manages the visual part of the game. It draws new levels, and places stars in random positions on the canvas. Here’s the code to generate and place the stars for a new level:

let redrawScreen { canvas = canvas; polyline = polyline; stars = stars } level =
    drawBorders canvas

    for n in [1..level*3] do
        let star = Mvvm.loadXaml "star.xaml" :?> Path
        stars.Add star
        Canvas.SetLeft(star, float(rand.Next(10, int(width) - 10)))
        Canvas.SetTop(star, float(rand.Next(2, int(height) - 10)))
        canvas.Children.Add star |> ignore

    canvas.Children.Add(polyline) |> ignore

The need to use float and int in the calculations of the star positions highlights how much stricter the F# compiler is about types compared to C# or IronPython. You can’t just mix and match ints and floats; you have to explicitly cast them.

Every time the user needs to move to a new position, we must perform a collision detection. Have they hit any of the stars on the screen, or have they hit one of the walls? Here’s the full collision detection code:

let isCollision stars x y width height =
    if y <= 0.0 || y >= height then
        // we've hit top or bottom
    elif x >= width then
        // we've hit the right edge but missed the gap
        not ((height / 2.0 + 15.0) > y && y > (height / 2.0 - 15.0))
        let isStarCollision star =
            let testX = x - Canvas.GetLeft(star)
            let testY = y - Canvas.GetTop(star)
            let testPoint = Point (testX, testY)
            Mvvm.checkCollisionPoint testPoint star
        stars |> Seq.exists isStarCollision

The Main ViewModel

Porting the MainViewModel to F# was relatively straightforward except for one circular dependency issue I ran into.  To illustrate, imagine this simple MVVM Command used by a ViewModel. The code won’t compile because we can’t reference the MyCommand member. There’s no easy way to reorganize these declaration to eliminate the circular references:

type MyCommand(func) =
    let mutable enabled = true
    member x.Execute() = func
    member x.Enabled 
        with get () = enabled
        and set (value) = enabled <- value

type MyViewModel() =
    let myFunc() = 
        printfn "Hello"
        MyCommand.Enabled <- false  // won't compile

    let myCommand = MyCommand(myFunc)

    member x.MyCommand 
        with get() = myCommand

How can we resolve this? Well it turns out there was a simple bit of F# syntax I was unaware of. If we say “as this” in our type declaration, we are able to use it to reference our class members before their declaration. Simple when you know how:

type MyViewModel() as this =
    let myFunc() = 
        printfn "Hello"
        this.MyCommand.Enabled <- false  

    let myCommand = MyCommand(myFunc)

    member x.MyCommand 
        with get() : MyCommand = myCommand

Making it Functional

Now I didn’t want to simply port from IronPython over to F#. Once it was working I wanted to refactor towards a more functional approach.

So first of all, I decided to see if I could eliminate some of the mutable state and change the game so that every time a timer event occurred, a new game state was created, rather than the existing one being modified.

So I came up with the following basic domain model. The GameState stores our current position, the direction we’re headed and what level we’re on. And we also model the possible game events that can happen – a timer tick or a keypress resulting in a change of direction. Whenever a GameEvent occurs, we will generate a new GameState, but there will also be a RenderAction to apply to keep the UI in sync with the GameState.

type Direction = Up | Down
type GameState = { xPos:float; yPos:float; direction:Direction; currentLevel:int}
type RenderAction = NewPoint | NewLevel | GameOver
type GameEvent = Tick | ChangeDirection of Direction

So our timer tick handler function returns a new game state and a render action. And it needs to be passed a helper collision tester function (colTest) to help it know if the game should end:

let handleTick colTest gs =
    if gs.currentLevel = 0 then
        NewLevel, { currentLevel = 1; xPos = 0.0; yPos = GameArea.height / 2.0; direction = Down }
        let newX = gs.xPos + 1.0
        let newY = gs.yPos + match gs.direction with | Up -> -1.0 | Down -> 1.0

        let crash = colTest newX newY GameArea.width GameArea.height
        if crash then
            GameOver, gs
        else if gs.xPos >= GameArea.width then
            NewLevel, { currentLevel = gs.currentLevel + 1; xPos = 0.0; yPos = GameArea.height / 2.0; direction = Down }
            NewPoint,  { gs with  xPos = newX; yPos = newY } 

The advantage of this refactoring to a functional approach is that this method is completely unit testable and and agnostic of the actual presentation technology. We could use this logic with a WinForms or HTML Canvas UI if we wanted.


I also wanted to make the code more functional by treating all the game events as a stream of observables. This meant that the game logic boils down to subscribing to an observable of game events and producing a set of render actions to be handled by the UI.

In F# it’s very easy to subscribe to events with Observable.subscribe

timer.Tick |> Observable.subscribe onTimerTick

But we can go further and filter and map observable events. So for example to filter out all presses of the space bar and turn them into ChangeDirection Up commands we can do:

let isSpace (a:KeyEventArgs) = a.Key = Key.Space

xaml.KeyDown |> Observable.filter isSpace |> Observable.map (fun _ -> ChangeDirection Up)

I wanted to merge all the events I was interested in into a single stream. There’s an Observable.merge function that will combine two observables, so to combine multiple observables we need to use List.reduce. Here’s us merging five observables into a stream of Game Events:

[ timer.Tick |> Observable.map (fun _ -> Tick) 
  xaml.KeyDown |> Observable.filter isSpace |> Observable.map (fun _ -> ChangeDirection Up)
  xaml.KeyUp |> Observable.filter isSpace |> Observable.map (fun _ -> ChangeDirection Down)
  xaml.MouseLeftButtonDown |> Observable.map (fun _ -> ChangeDirection Up)
  xaml.MouseLeftButtonUp |> Observable.map (fun _ -> ChangeDirection Down)          
|> List.reduce Observable.merge 
|> Observable.subscribe onGameEvent

Making it Christmassy

Finally, since this is the F# Advent Calendar, I did want to make it a bit more Christmassy. Sadly time did not permit for me to add XAML snow, but I did use my incredible ninja graphic design skills to create this XAML Christmas tree:

<Path xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
  Data="M 8,18 v-4 h -5 l 5,-4 h -4 l 4,-4 h -3 l 5,-5 l 5,5 h -3 l 4,4 h-4 l 5,4 h-5 v4 Z">
        <ScaleTransform ScaleX="0.8" ScaleY="0.8" />

which looks like this:


Now we can randomly select stars or trees and get a more festive looking game:


Taking it Further

Now although I did make some efforts to make this game more functional (and more Christmassy), there is certainly still a lot of scope for improvement. So over to you, whether you’re an F# beginner or guru, why not clone my GitHub repo, have a play of the game, and see if you can improve the code or add a new feature.

Happy Christmas, and enjoy the rest of your F# Advent. If you’re a regular follower of my blog, you’ll know that I’ve also been attempting to solve the Advent of Code challenges in F#. You can read about my solutions here.


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

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.