Posted in:

The first part of today’s Advent of Code challenge was relatively straightforward. We have a list of instructions, which we need to parse and apply one by one to get our output. Each instruction scrambles a string in some way, by rotating, reversing or swapping characters.

Here’s my discriminated union of instruction types:

type Instruction = SwapPos of int * int
                   | SwapLetter of char * char
                   | RotateRight of int
                   | RotateLeft of int
                   | RotatePos of char
                   | Reverse of int * int
                   | Move of int * int

I wanted one function to apply each of these instructions. I could have made them take and return strings, but decided that char[] might be easier. In the spirit of F#, I also kept these functions pure, returning a new char[] instead of mutating the input one. Interestingly that made some of the instructions easier, but others harder to implement.

The first six were quite simple to create. I used a combination of techniques including Array.mapi which gives us each element in the array along with its index, and used array comprehensions. Also there was plenty of scope for reuse in the rotation. I didn’t take time to optimise these functions from a performance perspective, as the strings are just 8 characters and our input is only 100 commands.

let swap x y (a:_[]) = Array.mapi (fun n c -> if n = x then a.[y] elif n = y then a.[x] else c) a

let swapLetter x y = Array.map (fun c -> if c = x then y elif c = y then x else c)

let rotateLeft n (a:_[]) = [|for i in 0..a.Length-1 -> a.[(n+i)%a.Length]|]
let rotateRight n (a:_[]) = rotateLeft (a.Length-(n%a.Length)) a

let rotatePos c (a:_[]) =
    let n = Array.findIndex ((=) c) a
    rotateRight (n + if n >= 4 then 2 else 1) a

let reverse x y (a:_[]) =
    Array.mapi (fun n c -> if n < x || n > y then a.[n] else a.[x + y - n]) a

The one instruction that felt quite ugly to implement was actually the move command. The simplest way I could think of would first be to generate a temporary array with the element to be moved removed, and then to make another with it inserted in the target location. But I wanted to try it without a temporary array, and ended up with this rather cumbersome solution:

let move x y (input:char[]) =
    input |> Array.mapi (fun n c ->
        if (n < x && n < y) || (n > x && n > y) then
            input.[n]
        else if n = y then
            input.[x]
        else if x < y then
            input.[n+1]
        else
            input.[n-1])

With our seven functions in place, we now need a function to apply the correct instruction. F#’s pattern matching functions are good for this:

let apply = function
            | SwapPos (x,y) -> swap x y 
            | SwapLetter (x,y) -> swapLetter x y 
            | RotateRight n -> rotateRight n 
            | RotateLeft n -> rotateLeft n 
            | RotatePos c -> rotatePos c 
            | Reverse (x,y) -> reverse x y 
            | Move (x,y) -> move x y

Next we need to be able to parse the input instructions. This could be done fairly easily with string splitting:

let parseInstruction (inst:string) =
    let parts = inst.Split(' ')
    match parts.[0..1] with
    | [| "swap"; "position" |] -> SwapPos (int parts.[2], int parts.[5])
    | [| "swap"; "letter" |] -> SwapLetter (parts.[2].[0], parts.[5].[0])
    | [| "reverse"; "positions" |] -> Reverse (int parts.[2], int parts.[4])
    | [| "rotate"; "left" |] -> RotateLeft (int parts.[2])
    | [| "rotate"; "right" |] -> RotateRight (int parts.[2])
    | [| "move"; "position" |] -> Move (int parts.[2], int parts.[5])
    | [| "rotate"; "based" |] -> RotatePos (parts.[6].[0])
    | _ -> failwith ("parse error: " + inst)

Finally we have the pieces in place to create a scrambler that takes a starting string and a list of instructions and returns the scrambled string. A fold is ideal for this sort of thing:

let scramble (input:string) instructions =
    instructions |> Seq.map parseInstruction |> Seq.fold (fun s i -> apply i s) (input.ToCharArray()) |> System.String

This allowed me to solve part a of the challenge:

System.IO.File.ReadAllLines (__SOURCE_DIRECTORY__ + "\\input.txt") 
|> scramble "abcdefgh"
|> printfn "Part a: %s"

But part b was interesting – we now needed to unscramble a string. Given an ending point, what was the starting string? This meant we would need to create an undo function for each of the seven instructions, and then apply them in reverse order.

This sounded like a lot of work until I realised that most instructions would be easily reversable. A rotate left becomes a rotate right. A swap undoes itself. So with the exception of RotatePos, all undo functions were straightforward:

let undo = function
            | SwapPos (x,y) -> swap x y 
            | SwapLetter (x,y) -> swapLetter x y 
            | RotateRight n -> rotateLeft n 
            | RotateLeft n -> rotateRight n 
            | RotatePos c -> undoRotate c
            | Reverse (x,y) -> reverse x y 
            | Move (x,y) -> move y x

But how to implement undoRotate? Undoing it would simply be a rotate left, but the tricky part would be working out how many positions to rotate by. I tried looking for a pattern with a five character test string, but that ended up getting confusing and it seemed there may even be ambiguous situations with more than one possible reversal instruction.

It occurred to me I could brute-force the reversal function. If I tried every value of rotate left, at least one of them would give an instruction that undid the original RotatePos command for this input. So undoRotate tries all possible left-rotations and finds the one that gives us our original answer back when we apply the RotatePos command. Yes, it’s clumsy, and it turns out for 8 character strings there was a pattern that could have got me directly to the amount, but this does at least work:

let undoRotate c (a:_[]) =
    a |> Array.mapi (fun n c -> n, apply (RotateLeft n) a) |> Seq.find (fun (n,t) -> (apply (RotatePos c) t) = a) |> snd

Now we can make an unscramble function which is very similar to scramble except we must reverse the order of the instructions (with Seq.rev), and use undo instead of apply:

let unscramble (input:string) instructions =
    instructions |> Seq.map parseInstruction |> Seq.rev |> Seq.fold (fun s i -> undo i s) (input.ToCharArray()) |> System.String

And this gets us our answer for part b.

System.IO.File.ReadAllLines (__SOURCE_DIRECTORY__ + "\\input.txt") 
|> unscramble "fbgdceah"
|> printfn "Part b: %s"

To critique my own solution, it’s not particularly concise, nor is it optimised for performance, but arguably neither of those were important to solve today’s problem. What I do like is the way that F# discriminated unions bring structure to the code, and that by creating lots of little functions to apply the instructions I was very easily able to run unit tests as I went along, checking that each bit worked as expected. Puzzles like these are a perfect fit for TDD.

My code is up on GitHub if you’re interested.