Posted in:

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.