// Branches are pruned off the search tree according to the rules:

// 1. contain "Not Not" as no-operation

// 2. cause a stack underrun as faulty

// 3. put more items on the stack than can be removed with one item left as faulty

// 4. contain code like "Vx Vy And|Or|Eor" where x = y as no-operation

// 5. contain code like "Vx Vy And|Or|Eor" where x > y as duplicate

​

type Op = And = 0 | Or = 1 | Xor = 2 | Not = 3 | V1 = 4 | V2 = 5 | V3 = 6 | V4 = 7

​

let printCode = function

  | []  -> printf "[] "

  | prg -> prg |> List.rev |> List.iter (printf "%A ")

​

let maxLength = 3

let numberOfFunctions = (8.0 / 7.0) * ((8.0 ** float maxLength) - 1.0)

let mutable totalProcessed = 0L

​

​

let rec search func size stackDepth =

    totalProcessed <- totalProcessed + 1L

    if stackDepth = 1 && maxLength < 5 then printCode func; printfn ""

    if size < maxLength then

      let remaining = maxLength - size

      if stackDepth > 1 then

        match func with

        | x::y::xs when y >= Op.V1 && x > y ->

          search (Op.And::func) (size + 1) (stackDepth - 1)

          search (Op.Or::func)  (size + 1) (stackDepth - 1)

          search (Op.Xor::func) (size + 1) (stackDepth - 1)

        | _ -> ()

      if stackDepth <= remaining && stackDepth > 0 then

        match func with

        | Op.Not::_ -> ()

        | _ ->

          search (Op.Not::func) (size+1) stackDepth

​

      if stackDepth < remaining then

        search (Op.V1::func) (size + 1) (stackDepth + 1)

        search (Op.V2::func) (size + 1) (stackDepth + 1)

        search (Op.V3::func) (size + 1) (stackDepth + 1)

        search (Op.V4::func) (size + 1) (stackDepth + 1)

search [] 0 0

printfn "V1 V1 Xor" // Has to be inserted manually because it is pruned away as a no-operation

​

printfn "Number of programs: %A" numberOfFunctions

printfn "Programs processed: %A" totalProcessed

printfn "%.2f%% of programs skipped" (100.0 - (float totalProcessed / numberOfFunctions) * 100.0)