Enumeration of integer expre ssions which only contains 8s

open Printf

type exp =
| Impossible
| Eight
| Add of exp * exp
| Sub of exp * exp
| Div of exp * exp
| Mul of exp * exp
| Sqrt of exp

let rec print out = function
| Impossible -> ()
| Eight -> fprintf out "8"
| Add (a,b) -> fprintf out "(%a + %a)" print a print b
| Sub (a,b) -> fprintf out "(%a - %a)" print a print b
| Div (a,b) -> fprintf out "(%a / %a)" print a print b
| Mul (a,b) -> fprintf out "(%a * %a)" print a print b
| Sqrt (a) -> fprintf out "sqrt(%a)" print a

let n = 256
let c = 4

let mem = Array.init c (fun _ -> Array.make n Impossible)

let rec enum exp count value =
  if value > 0 && value <= n &&
     count > 0 && count <= c &&
     mem.(count-1).(value-1) = Impossible then
  begin
    printf "%a = %d (%d)\n" print exp value count ;
    mem.(count-1).(value-1) <- exp ;

    if count < c then
    begin
      for i = 0 to c-1 do
        for j = 0 to n-1 do
          let exp' = mem.(i).(j)
          and count' = i+1
          and value' = j+1 in
          if exp' <> Impossible then
          begin
            enum (Add (exp, exp')) (count + count') (value + value') ;
            enum (Sub (exp, exp')) (count + count') (value - value') ;
            enum (Sub (exp', exp)) (count + count') (value' - value) ;
            enum (Mul (exp, exp')) (count + count') (value * value') ;
            if value mod value' = 0 then
              enum (Div (exp, exp')) (count + count') (value / value') ;
            if value' mod value = 0 then
              enum (Div (exp', exp)) (count + count') (value' / value) ;
          end
        done
      done
    end ;

    let froot = sqrt (float_of_int value) in
    let iroot = int_of_float froot in
    if float_of_int iroot = froot then
      enum (Sqrt exp) count iroot ;
  end

let _ =
  enum Eight 1 8 ;
  for j = 0 to 29 do
    printf "%d: %a\n" (j+1) print mem.(c-1).(j) ;
  done