(* Copyright (C) 2008 Mauricio Fernandez <mfp@acm.org> http//eigenclass.org *)
(* Solution to the coding challenge at
 * http://beust.com/weblog/archives/000491.html *)
open Printf

let permutations f len =
  let rec loop n len l1 = function
      d::tl -> aux (n * 10 + d) (len - 1) l1 tl; loop n len (d::l1) tl
    | [] -> ()
  and aux n len l1 l2 = match len with
      0 -> f n
    | len -> loop n len [] (List.rev_append l1 l2)
  in for i = 1 to 9 do
    let l = List.filter ((<>) i) (Array.to_list (Array.init 10 (fun i -> i))) in
      aux i (len - 1) [] l
  done

let () =
  let max = 10_000_000_000 in

  let count = ref 0 and prev = ref 0 and maxj = ref 0 and base = ref 0 in
  let report () =
    printf "Found %d numbers under %d.\n" !count max;
    printf "Max jump: %d (%d -- %d).\n" !maxj !base (!base + !maxj)

  in try
    for i = 1 to 10 do
      permutations
        (fun num ->
           if num >= max then raise Exit;
           (* printf "%d\n" num; *)
           incr count;
           let jump = num - !prev in
             if jump > !maxj then (maxj := jump; base := !prev);
             prev := num)
        i
    done;
    report ()
  with Exit -> report ()