Micro interpreter, gds version

gistfile1.ml

type exp = IfGt of int * int * block * block
         | Swap of int * int
         | Copy of int * int
and block = exp list;;

let rec eval (a : int array) = function
  | IfGt(i, j, b1, b2) -> go a 1 (if a.(i) > a.(j) then b1 else b2)       
  | Swap(i, j) -> 
      let ai = a.(i) and aj = a.(j) in
      a.(i) <- aj; a.(j) <- ai; 1
  | Copy(i, j) -> 
      a.(i) <- a.(j); 1
and go a n = function
  | [] -> n
  | e::es -> go a (n + eval a e) es
 
let evalBlock a blk =
  go a 0 blk 

let numSteps blk ua =
  let a = Array.copy ua in
  let n = evalBlock a blk in
  if a.(1) = 2 && a.(6) = 7 then n else 25000

let rec insert x l = match l with
  | [] -> [[x]]
  | a::m -> (x::l) :: (List.map (fun y -> a::y) (insert x m))
         
let rec perms = function
  | a::m -> List.flatten (List.map (insert a) (perms m))
  | l -> [l]

let inputs = 
  let zs = Array.make 4 0 in
  List.map (fun xs -> Array.append (Array.of_list xs) zs) (perms [1;2;3;4;5;6;7;8])

let calcScore blk = List.fold_left (fun sum a -> sum + numSteps blk a) 0 inputs

let cmp_swap i j = IfGt(i, j, [Swap(i, j)], [])

let mksornet cmp = 
  [cmp 0 1; cmp 2 3; cmp 4 5; cmp 6 7;
  cmp 0 2; cmp 1 3; cmp 4 6; cmp 5 7;
  cmp 1 2; cmp 5 6; cmp 0 4; cmp 3 7;
  cmp 1 5; cmp 2 6;
  cmp 1 4; cmp 3 6]

let sornet = mksornet cmp_swap

let (|>) x f = f x;;

Array.make 40 sornet |> Array.map calcScore |>  Array.fold_left min 999999999 |> print_int;;