# Summary Ranges Exercise – How can I improve this code?

I’ve been trying an exercise from leetcode.com - https://leetcode.com/problems/summary-ranges/
Basically, given a list of integers (sorted and unique), produce a list of ranges.
e.g. [0; 1; 2; 4; 5; 7; 12; 13; 14; 15; 18; 20] → [“0 → 2”; “4 → 5”; “7”; “12 → 15”; “18”; “20”]

I’m already up to my fourth version of the code:

1. Recursion;
2. Recursion with shorter lists;
3. List.fold;
4. List.foldBack (removing extra list reversal).

But I’m wondering if there are more improvements/optimisations/tidy-ups that I can do.

Here’s the current code:

``````let describe range =
match range with
| [] -> failwith "empty range"
| [single] -> single.ToString()
| [lower ; upper] -> lower.ToString() + " -> " + upper.ToString()
| _ -> failwith "too many items"

let summaryRanges numbers =
(numbers, [])
||> List.foldBack (fun number ranges ->
match ranges, number with
| [], currentNumber -> [[currentNumber]]
| currentRange::restOfRanges, currentNumber ->
match currentRange with
| [single] when single = currentNumber + 1 -> [currentNumber ; single]::restOfRanges
| [_] -> [currentNumber]::currentRange::restOfRanges
| [lower ; upper] when lower = currentNumber + 1 -> [currentNumber ; upper]::restOfRanges
| [_ ; _] -> [currentNumber]::currentRange::restOfRanges
| _ -> failwith "too many items in the range"
)
|> List.map describe

[0; 1; 2; 4; 5; 7; 12; 13; 14; 15; 18; 20] |> summaryRanges
``````

In particular, I’m wondering if there is anything I can do to try and lessen the code repetition, but any advice would be appreciated.

In F# you should think about the types involved. Think about what a range is and define a type to represent it. That will remove the failwiths and code repetition.

1 Like

Types, yes, that’s the ticket, and something I should have been able to come up with myself; thank you.

I got so ‘hung up’ on using lists, and lists of lists, that I totally forgot that I could use some simple types to do it better.

``````type SummaryItem =
| Single of Value:int
| Range of Lower:int * Upper:int

let describe item =
match item with
| Single value -> value.ToString()
| Range (lower, upper) -> lower.ToString() + " -> " + upper.ToString()

let summaryRanges numbers =
(numbers, [])
||> List.foldBack (fun number items ->
match items with
| [] -> [Single (Value = number)]
| Single value when value = number + 1 -> [Range (Lower = number, Upper = value)]
| Range (lower, upper) when lower = number + 1 -> [Range (Lower = number, Upper = upper)]
| Single _
| Range (_, _) -> [Single (Value = number) ; head]
)
|> List.map describe

[0; 1; 2; 4; 5; 7; 12; 13; 14; 15; 18; 20] |> summaryRanges
``````

If there are further improvements then I’d appreciate being told about them.

Thanks again.

1 Like

I tried my hand at the solution to this guy:

``````let rec finishRange lastVal = function
| x :: xs when x = lastVal + 1 -> finishRange x xs
| xs -> (lastVal, xs)

let rec ranges = function
| startOfRange :: xs ->
let (endOfRange, rest) = finishRange startOfRange xs
(startOfRange, endOfRange) :: ranges rest
| [] -> []

let describe = function
| (x, y) when x = y -> string x
| (x, y) -> sprintf "%i->%i" x y

let summarizeRanges xs =
let summaries = ranges xs |> List.map describe
printfn "%A" summaries
``````

But I have no arguments why this implementation is better than your second implementation. It offers no improvements, just a different code style.
I don’t think there’s much to optimize here (it’s going to be O(n) pretty much no matter what). Once you get rid of the `failwith`s, I think the rest is going to just be subjective.

1 Like

Thanks for this alternative version.

As you say, a different way to do the same thing.

There are some ‘odds and ends’ in your code which I need to remember and use elsewhere.