Project Euler — Problem 112 Solution

Problem

Work­ing from left-to-right if no dig­it is exceed­ed by the dig­it to its left it is called an increas­ing num­ber; for exam­ple, 134468.

Sim­i­lar­ly if no dig­it is exceed­ed by the dig­it to its right it is called a decreas­ing num­ber; for exam­ple, 66420.

We shall call a pos­i­tive inte­ger that is nei­ther increas­ing nor decreas­ing a “boun­cy” num­ber; for exam­ple, 155349.

Clear­ly there can­not be any boun­cy num­bers below one-hun­dred, but just over half of the num­bers below one-thou­sand (525) are boun­cy. In fact, the least num­ber for which the pro­por­tion of boun­cy num­bers first reach­es 50% is 538.

Sur­pris­ing­ly, boun­cy num­bers become more and more com­mon and by the time we reach 21780 the pro­por­tion of boun­cy num­bers is equal to 90%.

Find the least num­ber for which the pro­por­tion of boun­cy num­bers is exact­ly 99%.

Solution

// define func­tion f which com­pares the sort­ed and orig­i­nal dig­its of the sup­plied
// num­ber n and returns if they’re the same
let f (sort:int[] -> int[]) (n:int) =
let dig­its = n.ToString().ToCharArray() |> Array.map (fun c -> int(c.ToString()))
not(digits |> Seq.exists2 (fun e e’ -> e > e’) (sort dig­its))

// cur­ry the func­tion f to form the isIn­creas­ing and isDe­creas­ing func­tions
let isIn­creas­ing = f (fun l -> Array.sort l)
let isDe­creas­ing = f (fun l -> Array.sortBy (fun x -> 1 — x) l)

let isBoun­cy n = not(isIncreasing n) && not(isDecreasing n)

let answer =
let muta­ble boun­cy­Count, boun­cyRa­tio, n = 0, 0.0, 100
while boun­cyRa­tio > 0.99 do
n - n+1 if isBoun­cy n then boun­cy­Count - bouncyCount+1 boun­cyRa­tio - double(bouncyCount)/double(n) n [/code]