# The 3, 3, 8, 8 Puzzle

I was inspired by this puzzle to create a program which could solve the problem for me. I figured I'd use F# because it's starting to look really cool.

Here's my F# solution code as a script:

```// Light F# syntax.
#light

// Definition of the binary operator type.
type BinOp = (Math.BigNum -> Math.BigNum -> Math.BigNum)

// Terms in the postfix expression are either numbers or operators.
type Term =
| Number of Math.BigNum
| Operator of BinOp

// The result of an operation is either a number or Invalid.
type Result =
| Invalid

// Array of possible numbers and operators.
let postfix_terms =
[|Number 3N;
Number 8N;
Operator (fun (x:Math.BigNum) (y:Math.BigNum) -> x + y);
Operator (fun (x:Math.BigNum) (y:Math.BigNum) -> x - y);
Operator (fun (x:Math.BigNum) (y:Math.BigNum) -> x * y);
Operator (fun (x:Math.BigNum) (y:Math.BigNum) -> x / y)|]

// Increments a number in base 6. The number is represented as a string of
// integers. Overflow is not accounted for (i.e. the length of the number
// doesn't change). The base is 6 because the digits of the number are used
// to index the postfix_terms array and there are 6 elements in the array.
// Example (in base 6):
// [5;5;3;5;5;2;1]
// +1
// ---------------
// [0;0;4;5;5;2;1]
let rec inc_indexer indexer =
match indexer with
| hd::tl ->
match hd with
| 5 -> 0::(inc_indexer tl)
| _ -> (hd+1)::tl
| _ -> []

// Uses the indexer to generate a possible expression based on the char_vec.
let rec gen_string indexer =
match indexer with
| hd::tl -> postfix_terms.(hd)::(gen_string tl)
| _ -> []

// Evaluates a postfix expression and returns the resulting number or Invalid.
let rec evaluator expr acc =
match expr with
// Numbers go on the accumulator stack.
| Number hd::tl -> evaluator tl (hd::acc)
// Operators are evaluated with the top two numbers on the stack.
| Operator hd::tl ->
match acc.Length with
// First make sure there are enough elements in the accumulator.
| 0 -> Invalid
| 1 -> Invalid
// Now apply the operator and evaluate recursively.
// When the stack is empty, the accumulator should hold the result.
| _ ->
match acc with
| _ -> Invalid

// Prints a list of integers. This is used to print the indexer list which
// in turn is used to generate the postfix expression.
let rec print_list lst =
match lst with
| hd::tl ->
printf "%i " hd
print_list tl
| [] -> printf "-> "

// Returns true if the list of terms contains two 3's and two 8's and false
// otherwise.
let rec validate terms eights threes =
match terms with
| Number a::tl ->
match (a.ToString()) with
| "3" -> validate tl eights (threes+1)
| "8" -> validate tl (eights+1) threes
| _ -> validate tl eights threes
| [] ->
match eights with
| 2 ->
match threes with
| 2 -> true
| _ -> false
| _ -> false
| _::tl -> validate tl eights threes

// Evaluates all possible postfix expressions and halts if it finds '24'
let rec process index =
let new_index = (inc_indexer index)
let new_strng = (gen_string new_index)
match (validate new_strng 0 0) with
| true ->
match (evaluator new_strng []) with
| Invalid ->
process new_index
match (a.ToString()) with
| "24" ->
print_list new_index
printf "%s\n" (a.ToString())
| _ ->
print_list new_index
printf "%s\n" (a.ToString())
process new_index
| false -> process new_index

process [0;0;0;0;0;0;0]