0 Comments

Today’s Advent of Code challenge combined two distinct problems – maze solving, which we’ve already tackled before this year, and the “travelling salesman” problem (which we did actually see last year).

I decided to create a two phase solution. Phase 1 was to generate a map of the shortest distances between all the points of interest in the maze. And Phase 2 was then to solve the travelling salesman problem by searching for the shortest possible routes through those points of interest.

For phase 1, I was once again able to reuse an algorithm I’d created before – the breadth first search. One slight modification I needed to make was for it to keep searching after it had found a solution. This is because I needed to find the shortest route to all points of interest, and sometimes the shortest route from a to b goes through c, so we need to keep going until we’ve discovered all points of interest.

Here’s my generic breadth first searcher:

let bfs (isSolution:'a->bool) (getChildren:'a->seq<'a>) (start:'a) =
    let q = new Queue<'a>()
    q.Enqueue(start)
    let rec search() = seq {
        if q.Count > 0 then
            let s = q.Dequeue()
            if isSolution s then 
                yield s
            for c in getChildren s do
                q.Enqueue(c)
            yield! search()
    }
    search()

And this meant I could create a shortestFrom function which, given a starting point of interest (start), uses the breadth first search to find the distance to all other points of interest. It uses a dictionary to track which points in the maze have already been visited.

Another technique I tried was that the maze parameter to this function is a function that looks up a location in the maze rather than being the array of strings directly. This makes my function less dependent on the choice of data structure I used to represent the maze.

let shortestFrom maze start =
    let startc = maze start
    let dist = Dictionary<int*int,int>()
    let getChildren ((x,y),d) = 
        [(-1,0);(0,-1);(1,0);(0,1)]
        |> Seq.map (fun (i,j) -> (x+i,y+j) )
        |> Seq.filter (dist.ContainsKey >> not)
        |> Seq.filter (fun p -> maze p <> '#')
        |> Seq.map (fun p -> dist.[p] <- d+1; (p,d+1))
    let isSolution (pos,d) =
        let c = maze pos
        c >= '0' && c < '9' && c <> startc
    bfs isSolution getChildren (start,0) |> Seq.map (fun (p,d) -> maze p,d)

Now with the help of a couple more helper functions (mazeLookup and mazeFind) I created a buildShortestPathLookup which creates a map of distances between every pair of points. There was some optimization potential here because the distance from A to B is calculated twice (we also calculate B to A), but the size of the input data meant this was not a big performance concern.

let mazeLookup (maze:string[]) (x,y) = maze.[y].[x]
let mazeFind (maze:string[]) c = 
    [for y in 0..maze.Length-1 do 
        for x in 0 ..maze.[y].Length-1 do 
            if maze.[y].[x] = c then yield (x,y)]
            |> List.tryFind (fun _ -> true)

let buildShortestPathLookup maze =
    ['0'..'9'] 
    |> Seq.choose (mazeFind maze)
    |> Seq.collect (fun c -> 
                shortestFrom (mazeLookup maze) c
                |> Seq.map (fun (t,d)-> ((mazeLookup maze c,t),d)))
    |> Map.ofSeq

With that map in place, finding the shortest path was as simple as trying all the possible visiting orders. Since there were eight cities in my map, the number of routes is 7!, which is just 5040. So it can be easily brute forced. For more cities, we should do a depth first search and abandon any route that is longer than the current best one we’ve found.

My findShortestPath function uses a recursive internal search function which works through a list of cities still to visit. And since part b of the problem also asks us to return to our original location, we need the search function to return not only the distance but the ending point, so we can append the distance back to home onto each visiting order.

let findShortestPath maze ret =
    let lookup = buildShortestPathLookup maze
    let rec search (toVisit:char list) current (dist:int) = seq {
        match toVisit with
        | [] ->  yield dist, current
        | _ ->
            for v in toVisit do
                let d = lookup.[(current,v)]
                yield! search (toVisit |> List.filter ((<>) v)) v (dist+d)
    }
    let toVisit = ['1'..'9'] |> List.choose (mazeFind maze) |> List.map (mazeLookup maze)
    let paths = search toVisit '0' 0
    if ret then
        paths |> Seq.map (fun (d,c) -> d + lookup.[c,'0'])
    else
        paths |> Seq.map fst

Now we have all the pieces in place to solve both parts of the problem, as well as check our work by solving the test input, which I’ve done each day so far this year and has helped a lot with the correctness of my solutions:

let maze = System.IO.File.ReadAllLines (__SOURCE_DIRECTORY__ + "\\input.txt")
let testMaze = System.IO.File.ReadAllLines (__SOURCE_DIRECTORY__ + "\\testinput.txt")

findShortestPath testMaze false |> Seq.min |> printfn "Test: %d"
findShortestPath maze false |> Seq.min |> printfn "Part a: %d"
findShortestPath maze true |> Seq.min |> printfn "Part b: %d"

Hopefully tomorrow’s puzzle won’t be too taxing, as I don’t think I’ll be allowed to get away with a few hours of programming on Christmas Day! Full code for today’s answer is up on GitHub.

0 Comments

In yesterday’s Advent of Code post, I talked about “YAGNI” – you aren’t gonna need it. Well, for today’s solution, we did need to borrow some code from day 12. We were simulating a computer with the same instruction set, except for there was one new instruction – toggle.

Since we had a discriminated union defined for all possible instructions, in theory we should just have needed to add a new entry to it, and written the code to process the instruction.

However, it was more complicated than that. My day 12 solution assumed the program was immutable – but now it could change. And the toggle command can result in some impossible to implement instructions.

One benefit of using discriminated unions in F# is that you can “make illegal states impossible to represent”. But that meant my Instruction type was now too restrictive – I needed to be able to store invalid versions of some commands.

So my domain model now looks like this:

type Source= Constant of int | Register of string 

type Instruction = Copy of Source*Source | Inc of Source | Dec of Source | Jnz of Source*Source | Toggle of Source

And after introducing a helper function called read, here’s the new implementations of the original functions. As you can see, copy, inc and dec now need to ignore invalid forms of the instruction:

let read (state:Map<string,int>) = function | Constant n -> n | Register r -> state.[r]

let copy source dest (state:Map<string,int>) =
    match dest with 
    | Register register -> state.Add(register, read state source)
    | _ -> state

let inc arg (state:Map<string,int>) =
    match arg with 
    | Register register -> state.Add(register, state.[register] + 1)
    | _ -> state

let dec arg (state:Map<string,int>) =
    match arg with
    | Register register -> state.Add(register, state.[register] - 1)
    | _ -> state

let jnz source offset (state:Map<string,int>) =
    if read state source = 0 then 1 else read state offset

But what about the toggle instruction? This needs to update the program itself. Now I allowed myself to cheat a little here, and mutated the program array, rather than returning a new program, which would have been the correct functional approach. So the toggle function ends up modifying the program, and returns the same register state, and instructing us to move to the next command (offset of 1):

let toggle state source (prog:_[]) index =
    let offset = index + (read state source)
    if offset >= 0 && offset < prog.Length then
        let toggled = match prog.[offset] with
                        | Copy (source, register) -> Jnz (source, register) 
                        | Inc register -> Dec register 
                        | Dec register -> Inc register
                        | Jnz (source,off) -> Copy (source, off)
                        | Toggle source -> Inc source
        prog.[offset] <- toggled
    state,1

And what happens to our apply function from day 12? Well now it needs to take the program array in so that toggle can modify it, but otherwise it is pretty similar:

let apply (st:Map<string,int>) (prog:_[]) index = 
    match prog.[index] with
    | Copy (source, register) -> copy source register st, 1
    | Inc register -> inc register st, 1
    | Dec register -> dec register st, 1
    | Jnz (source,offset) -> st, jnz source offset st
    | Toggle source -> toggle st source prog index

The good news is that almost all the rest of the code was similar. The solve function remains the same, recursively working through each instruction. The input parsing just needed to cope with the new tgl command. And the start state had 7 in the “a” register.

let rec solve (prog:Instruction[]) (state:Map<string,int>) index =
    if index >= prog.Length then
        state
    else
        let newState,next = apply state prog index 
        solve prog newState (index+next)

let (|Source|_|) str = match System.Int32.TryParse str with true, value -> Some (Constant value) | _ -> Some (Register str)

let parseInstruction (inst:string) =
    let parts = inst.Split(' ')
    match parts with 
    | [| "cpy"; Source src; Source dst |] -> Copy (src,dst)
    | [| "inc"; Source reg |] -> Inc reg
    | [| "dec"; Source reg |] -> Dec reg
    | [| "jnz"; Source src; Source offset |] -> Jnz (src, offset) 
    | [| "tgl"; Source src |] -> Toggle src
    | _ -> failwith ("can't parse " + inst)

let program = System.IO.File.ReadAllLines (__SOURCE_DIRECTORY__ + "\\input.txt") |> Array.map parseInstruction

let startState = Map.empty.Add("a",7).Add("b",0).Add("c",0).Add("d",0)

let endState = solve program  startState 0
printfn "part a: %d" endState.["a"]

It took a few seconds to run, but got me my answer to the first part of the puzzle.

Part 2 in theory was easy. Just change the start state so we have 12 in register a and wait for the answer. But there was a huge hint in the puzzle description. We might be waiting a long time, and sure enough leaving the code running for 30 minutes did not yield an answer.

Could the program be optimised? Well, I did two things to find out. First of all, I made a version of my program that printed out what it was doing. This made it pretty obvious that there were some loops going on. Here’s a small section of the output:

[4] copying Register "b" to Register "c"
[5] incrementing Register "a"
[6] decrementing Register "c"
[7] jnz Register "c" Constant -2
[5] incrementing Register "a"
[6] decrementing Register "c"
[7] jnz Register "c" Constant -2
[5] incrementing Register "a"
[6] decrementing Register "c"
[7] jnz Register "c" Constant -2
[5] incrementing Register "a"
[6] decrementing Register "c"
[7] jnz Register "c" Constant -2
[5] incrementing Register "a"
[6] decrementing Register "c"
[7] jnz Register "c" Constant -2
[5] incrementing Register "a"
[6] decrementing Register "c"
[7] jnz Register "c" Constant -2
[8] decrementing Register "d"
[9] jnz Register "d" Constant -5
[4] copying Register "b" to Register "c"

We can see that there are some loops going on there. Looking again at my puzzle input I noticed that this pattern appeared in a few places:

inc a
dec c
jnz c -2

We’d keep incrementing register a until we’d decremented register c to 0. So essentially this was implementing a += c. But there was more. In two places, this three instruction pattern became a five instruction pattern:

inc a
dec c
jnz c -2
dec d
jnz d -5

Now we’re repeating the a += c operation d times. So this essentially is the same as implementing a += (c * d). So could I strip this code out and replace it with a multiply command? Not so fast – the extensive use of offsets, and the presence of the toggle command meant I didn’t want to mess with the contents of the instruction array.  But from examining the output of my part a solution I could tell that the only toggles that affected this 5 instruction pattern were toggling inc to dec. The jnz commands remained intact.

So I decided to do a very quick experiment. What happens if I put something very hacky into the apply function? When I hit either of these 5 instruction patterns, just increment a by the product of c and d. I use abs because whether we’re incrementing or decrementing d or c, we must be heading towards 0 or we’d have an infinite loop. So here’s the experimental hack version of apply (my loops appeared at indexes 5 and 21, and once we’ve processed them we move on 5 commands):

let apply (st:Map<string,int>) (prog:_[]) index = 
    if index = 5 || index = 21 then // multiplication loops
        st.Add("a",st.["a"] + (abs st.["c"]) * (abs st.["d"])), 5
    else
        match prog.[index] with
        | Copy (source, register) -> copy source register st, 1
        | Inc register -> inc register st, 1
        | Dec register -> dec register st, 1
        | Jnz (source,offset) -> st, jnz source offset st
        | Toggle source -> toggle st source prog index

This produced the correct answer for part a and in a fraction of the time. I then tried it on part b, but got the wrong answer. What had I done wrong?

Well, the perils of mutable code had come to bite me. Now that my solver function can mutate the program array, it’s not the same after solving part a of the problem. Had I kept it all immutable, it would have worked first time. The quick fix was to take a copy of the program array before running it through the solver:

let endState = solve (program |> Array.copy) startState 0
printfn "part a: %d" endState.["a"]

let endStateB = solve (program |> Array.copy) (startState.Add("a",12)) 0
printfn "part b: %d" endStateB.["a"]

This worked, and solved the problem in blazing fast time.

But just like yesterday, we have a solution that only works for our specific input. This one could at least be improved to be more general purpose. I could update the apply function to recognize the five instruction pattern and turn it into a multiply instruction. And if I were refactoring this code (for which there is sadly no time), I’d also return a new program from toggling, rather than mutating the existing one.

But once again, this puzzle is a great lesson in how paying attention to the shape of your input data can allow you to optimize your algorithm for your specific needs. My solution is up on GitHub if you want to see the full code.

0 Comments

For the second time in this year’s Advent of Code challenge, I feared I would not be able to get my two stars today. The first part of the puzzle was easy enough – parse the input with a regular expression active pattern, and then a nested for loop enabled me to find number of possible moves:

let (|Regex|_|) ptrn str = match Regex.Match(str, ptrn) with m when m.Success -> Some([ for g in m.Groups -> g.Value ] |> List.tail) | _ -> None

let parseLine line =
    match line with
    | Regex @"/dev/grid/node-x(\d+)-y(\d+)\s+(\d+)T\s+(\d+)T\s+(\d+)T\s+\d+\%" [x;y;s;u;a] -> Some ((int x,int y),int s,int u,int a)
    | _ -> None

let input = System.IO.File.ReadAllLines (__SOURCE_DIRECTORY__ + "\\input.txt")
 
let nodes = input |> Array.choose parseLine

seq {for (pos,s,u,a) in nodes do
        for (pos',s',u',a') in nodes do
            if pos <> pos' && u <> 0 && u < a' then
                yield 1} |> Seq.length |> printfn "part a: %d"

However, when I saw the second part of the puzzle, I realised that the brute force solution, whether tackled breadth or depth-first would take forever. We needed a much cleverer approach.

Basically the challenge involved us shifting data around a grid of computers. We could only move data from one computer to the next if there was enough space. But with a grid size of 30x33 nodes, the number of possibilities was overwhelming.

But there was a trick to solving part 2. And that was to notice something about the input data. In our grid, there were some nodes with so much data they could never be moved at all. So they were like walls in a maze. And there was just one empty node. All the other nodes had just enough data on them that they could only be copied to the empty node, but all had enough capacity to receive the data from any other node.

So this was essentially like a slide puzzle, where the empty node moves around the grid as we copy data onto it. We copy data until empty node is next to the one that has the target data. And then we shuffle the data up to the target node.

I wrote a very simple function to visualize the layout of my puzzle input. It visualizes the grid rotated, but that doesn’t matter for finding the shortest route:

let printPos (pos,s,u,a) =
    if u = 0 then "_" elif u > 100 then "#" else "."

nodes |> Array.chunkBySize 30 |>
    Array.map (Array.map printPos >> String.concat " ")
    |> (fun a -> System.IO.File.WriteAllLines(__SOURCE_DIRECTORY__ + "\\grid.txt", a))

Once I printed this out, it suddenly became obvious that the challenge was actually quite a simple one, hiding in the seemingly random problem input. My grid looks like this:

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . _
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .

The #’s mark ‘walls’ and the ‘_’ marks the empty node. And we just needed to move the data from the bottom left to top left.

Suddenly it becomes very obvious how to solve this. To get the empty node next to the bottom left we need to move it up 12 nodes, left 29 nodes and then down 28 nodes. Moving the target data up to the top left is a bit more complex as once we copy it up, the empty node is now the wrong side of the target data, so it takes four moves (right, up, up, left) to get it above the target data again. We have to repeat this five move sequence 35 times before needing one final copy to get the data to its target destination. So my answer could be calculated manually:

12+29+28+(31*5)+1 |> printfn "part b: %d"

Now in one sense, I was very pleased to get my answer, but this does feel a bit unsatisfactory. We’ve not written a general solution that could solve all possible inputs. I suppose we could write a solver that could solve “similar” inputs – where the optimal strategy was essentially the same. But a solver that found the shortest solution for all inputs would be very hard to create.

So today’s problem makes me think of the classic “YAGNI” principle: “You aren’t gonna need it”. So often as programmers we spend a long time writing complex code to meet imagined requirements that never materialize. But often just writing the minimal code that solves the actual problem we have today can save huge amounts of time. Yes, we may need to rewrite if harder inputs do come along in the future, but time now can be better spent on things we know we need.

The code is available on GitHub

0 Comments

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. SoundoRotate 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.

0 Comments

Today’s challenge required us to merge together overlapping numeric ranges.

The parsing of the input was relatively straightforward – I chose to use int64 as some of the numbers were outside the range of a 32 bit integer.

let parseRange (r:string) = 
    let parts = r.Split('-')
    int64 parts.[0], int64 parts.[1] 

let ranges = System.IO.File.ReadAllLines (__SOURCE_DIRECTORY__ + "\\input.txt") 
                |> Array.map parseRange

The strategy I ended up on was to produce a sequence of ranges (represented as tuples) which were the gaps between the ranges of “blocked” ip addresses in the input data. We simply needed to sort the “blocked” ranges into order of their starting address and then for each range we would optionally yield a new range of allowed addresses, or recursively call ourselves with the remaining ranges and a new lowest address to test:

let getAllowed blockedRanges =
    let rec mergeRanges n ranges = seq {
        match ranges with
        | [] -> yield (n,4294967295L)
        | (lo,hi)::tail ->
            if n < lo then yield (n,lo-1L)
            yield! mergeRanges (max n (hi+1L)) tail
    }
    mergeRanges 0L (blockedRanges |> Seq.sortBy fst |> Seq.toList)

This allowed me to use the same function to solve both parts of the problem:

getAllowed ranges |> Seq.head |> fst |> printfn "part a: %d"
getAllowed ranges |> Seq.sumBy (fun (lo,hi) -> hi - lo + 1L) |> printfn "part b: %d"

My solution does have the quirk of returning a potentially invalid range at the end, although it doesn’t affect the calculation of the sum. My excuse is that I had limited time today due to my internet access going down in the morning. My code is on GitHub.