Enumeration of integer expressions 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 expressions = ref []

let rec enum exp count value =
  if value > 0 && value <= n &&
     count > 0 && count <= c &&
     mem.(count-1).(value-1) = Impossible then
  begin
    mem.(count-1).(value-1) <- exp ;
    expressions := (exp,count,value) :: !expressions ;

    if count < c then
    begin
      let f (exp',count',value') =
        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) ;
      in
      List.iter f !expressions
    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