Summary Ranges Exercise – How can I improve this code?

General
1

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.

2

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
3

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.

Here’s the latest version, with some other changes:

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)]
            | head::tail -> 
                let newHead =
                    match head with 
                    | 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]
                newHead @ tail
        )
    |> 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
4

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 failwiths, I think the rest is going to just be subjective.

1 Like
5

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.