[Shootout-list] Fannkuch implementations - not reverse order

[Christophe TROESTLER]

----Next_Part(Fri_Mar_25_14_10_10_2005_646)--
Content-Type: Text/Plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

On Sun, 20 Mar 2005, Isaac Gouy <igouy2@yahoo.com> wrote:
> 
> Some Fannkuch implementations do the search in reverse order [...]
> OCaml have already been moved to "interesting alternative programs"
> - please let me know which other programs should be moved,

I believe the SML (SML/NJ and MLton) programs use the same algo than
the Caml one.  Also the OCaml bytecodes should be moved too then.

> and please contribute some boring vanilla implementations.

Here is a what I hope will fit as a "boring vanilla implementation"
for OCaml.

ChriS


----Next_Part(Fri_Mar_25_14_10_10_2005_646)--
Content-Type: Text/Plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Content-Disposition: inline; filename="fannkuch.ml"

(* fannkuch.ml

   The Great Computer Language Shootout
   http://shootout.alioth.debian.org/

   Contributed by Troestler Christophe
*)

(* Monomorphic version for speed *)
let max (x : int) y = if x < y then y else x

let rec count_flips c perm =
  let k = perm.(0) in
  if k = 0 then c else (
    for i = 0 to k / 2 do
      let k_i = k - i and perm_i = perm.(i) in
      perm.(i) <- perm.(k_i);  perm.(k_i) <- perm_i
    done;
    count_flips (c + 1) perm
  )

let count_flips = count_flips 0


let pfannkuchen n =
  let perm = Array.init n (fun i -> i)
  and perm' = Array.make n 0
  and count = Array.init n (fun i -> i + 1) in

  let m = n - 1 in
  let rec loop_perm maxflips r =
    if r = n then maxflips else (
      (* Rotate perm.(0 .. r-1) *)
      let perm0 = perm.(0) in
      for i = 0 to r - 1 do perm.(i) <- perm.(i+1) done;
      perm.(r) <- perm0;

      count.(r) <- count.(r) - 1;
      if count.(r) > 0 then (
	for i = 1 to r - 1 do count.(i) <- i + 1 done;
	if perm.(0) <> 0 && perm.(m) <> m then (
	  for i = 0 to m do perm'.(i) <- perm.(i) done;
	  loop_perm (max (count_flips perm') maxflips) 1
	)
	else loop_perm maxflips 1
      )
      else loop_perm maxflips (r+1)
    ) in
  loop_perm 0 1


let () =
  let n = try int_of_string Sys.argv.(1) with _ -> 1 in
  Printf.printf "Pfannkuchen(%i) = %i\n" n (pfannkuchen n)

----Next_Part(Fri_Mar_25_14_10_10_2005_646)----