Skip to content

If Google would be looking to hire F# programmers – part 4

May 3, 2013

As the next installment of the series let’s take the following problem from the bookgiven an arbitrary positive number find a next higher number consisting of the same digits. If such does not exist, then return the original number.

The base line approach would be splitting the number into a list of digits, making the list of all digit permutations, assembling digits back into numbers, sorting list of numbers, and finally picking the element next to the given. Apparently, the time and space complexities of this “solution” are awful, so let’s improve.

  • The first useful observation towards the optimized solution would be the following: solution exists iff a pair of adjacent digits exists in the given number, where the left is strictly less, than right.
  • The next useful observation would be: if we scan the list of digits of the given number from right to left by a sliding window of width 2, then the first occurred pair that matches the first observation would be the place of change; everything to the left of it (if any exists) must stay intact.
  • The final useful observation: taken the pair matching second observation, the sublist to the right including the right element of the pair is sorted from right to left; the digit that must substitute the left element of the pair must be minimal greater digit from the sublist; the left element that we just substituted should be placed some place to the right preserving the sublist order.

Now if we concatenate (if non-empty) the sublist to the left of changing digit, followed by substituting digit, followed by reversed sublist after accommodating of changing digit, and convert resulting digit list back to number, this would yield the solution with surprisingly good time complexity of O(n) and space complexity of O(n), where n is number of digits in the original number.

As this problem is of “puzzle” type let’s add some spice to the solution showing how F# can be advantageous for its coding. One such feature would be making the solution generic, i.e. accepting any integral type as input (byte, BigInteger, nativeint, whatever consisting of just digits). Achieving this statically (i.e. relying onto compiler with constraining right types) would require using inline F# facility. Let’s see this implemented in the code below:

let inline nextHigher number =

    let GenericTen = (LanguagePrimitives.GenericOne<'a> <<< 3) +
                     (LanguagePrimitives.GenericOne<'a> <<< 1)

    let toDigits n =
        let rec toDigitList digits n =
            if n = LanguagePrimitives.GenericZero then digits
            else toDigitList ((n % GenericTen) :: digits) (n / GenericTen)
        toDigitList [] n

    let fromDigits digits =
        let rec fromDigitList n = function
            | [] -> n
            | h::t -> fromDigitList (n * GenericTen + h) t
        fromDigitList LanguagePrimitives.GenericZero digits

    let make p ll  =
        ll |> List.rev |> List.partition ((<) p)
        |> fun (x,y) -> (x.Head::y) @ (p::(x.Tail))

    let rec scan (changing: 'a list) source =
        match source with
        | [] -> changing
        | h::t -> if h >= changing.Head then
                    scan (h::changing) t
                  else
                    (List.rev t) @ (make h changing)

    number |> toDigits |> List.rev
    |> fun x -> scan [(x.Head)] (x.Tail) |> fromDigits

A reader has commented upon previous posts that despite his previous F# coding experience the snippets look quite opaque. I’ll try addressing this matter by giving extended comments over the code.
The main inlined function nextHigher number definition in line #1 yields a quite impressive inferred list of constraints:


val inline nextHigher :
number: ^a -> ^d
when ( ^a or ^b) : (static member ( % ) : ^a * ^b -> ^a0) and
^a : (static member get_Zero : -> ^a) and
( ^a or ^b) : (static member ( / ) : ^a * ^b -> ^a) and
^a : equality and
( ^d or ^b) : (static member ( * ) : ^d * ^b -> ^c) and
^a0 : (static member get_One : -> ^a0) and
^a0 : (static member ( + ) : ^a0 * ^a0 -> ^b) and
^a0 : (static member ( << ^a0) and
^a0 : comparison and
( ^c or ^a0) : (static member ( + ) : ^c * ^a0 -> ^d) and
^d : (static member get_Zero : -> ^d)

While the constraints above can be slightly simplified it is still quite impressive how good is type inference in F#.

A variable Generic10 in line #3 is self-described – it resolves to 10 for any primitive numeric type with a static member One and operators <<< and +.

A pair of auxiliary functions defined in lines #6 and #12 perform disassembly of a numeric value into digits (toDigits) and vice versa (fromDigits). The functions allow solution to work upon any integral type via static checks.

The code in lines #18 – #31 implements the algorithm per se. Function make p ll declared in line #18 performs the conversion of pivot digit p and scanned part of the input number into corresponding part of the final order. Function scan in line #22 performs search for the pivot digit in the reversed list of digits ensuring either return of original value (line #24) if the solution does not exist, or the solution itself in line #28. Finally, lines #30-31 represent the execution pipeline.

I want to wrap up this post with some tests and corner cases demonstrating the implementation in action:

nextHigher 1987654321 // Just working on int
val it : int = 2113456789
nextHigher 987654321L // Working on long, solution does not exist
val it : int64 = 987654321L
nextHigher 32154321 // Pivot digit is in the middle
nextHigher 12uy // Working on unsigned bytes
val it : byte = 21uy
// Working on bigint
nextHigher 5598734987954054911111111111111I
val it : System.Numerics.BigInteger =
5598734987954059111111111111114 {IsEven = true;
IsOne = false;
IsPowerOfTwo = false;
IsZero = false;
Sign = 1;}
nextHigher 136442n // It even works with nativeints!!
val it : nativeint = 142346n

To be continued after approximately 2 week break…

Advertisements

From → F#

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: