Go program to solve 1989 problem, http://gaz-v-pol.livejournal.com/146153.html

digits.go

package main

import (
	"fmt"
	"math"
	"os"
	"strconv"
)

type Op int64 // Operators

const (
	OpNull Op = iota
	// Binomial ops start here
	OpAdd
	OpSub
	OpMul
	OpDiv
	OpPow
	// Single Ops start here
	OpFact // factorial
	OpSqrt // square root
)

var opNames = map[Op]string{
	OpNull: "NULL",
	OpAdd:  "+",
	OpSub:  "-",
	OpMul:  "*",
	OpDiv:  "/",
	OpPow:  "^",
	OpFact: "!",
	OpSqrt: "sqrt",
}

type Node struct {
	left, right *Node // Left and right subnode
	num         int64 // Number stored in this node
	op          Op    // Operation to be performed on this node. Requirs at least one or two subnodes to be defined.
}

// Eval returns the value of this node's expression
func (n *Node) Eval() (int64, error) {
	if n.op == OpNull {
		if n.left == nil && n.right == nil {
			return n.num, nil
		} else {
			return 0, fmt.Errorf("Undefined operation")
		}
	}
	if n.op < OpFact { // Binomial operator
		if n.left == nil || n.right == nil {
			return 0, fmt.Errorf("Not enough arguments for %s", opNames[n.op])
		}
		left, err := n.left.Eval()
		if err != nil {
			return 0, err
		}
		right, err := n.right.Eval()
		if err != nil {
			return 0, err
		}
		switch n.op {
		case OpAdd:
			return left + right, nil
		case OpSub:
			return left - right, nil
		case OpMul:
			return left * right, nil
		case OpDiv:
			if right == 0 {
				return 0, fmt.Errorf("Division by 0")
			}
			div := left / right
			if div*right == left { // whole division
				return div, nil
			} else {
				return 0, fmt.Errorf("Cannot wholy divide %d by %d", left, right)
			}
		case OpPow:
			return int64(math.Pow(float64(left), float64(right))), nil
		}
	} else { // Single operator
		if n.right != nil {
			return 0, fmt.Errorf("Right operand for %s should be empty", opNames[n.op])
		}
		if n.left == nil {
			return 0, fmt.Errorf("Left operand for %s should NOT be empty", opNames[n.op])
		}
		left, err := n.left.Eval()
		if err != nil {
			return 0, err
		}
		switch n.op {
		case OpFact:
			if left < 0 {
				return 0, fmt.Errorf("Cannot calculate %d!", left)
			}
			return factorial(left)
		case OpSqrt:
			if left < 0 {
				return 0, fmt.Errorf("Cannot extract square root from %d", left)
			}
			f := math.Floor(math.Sqrt(float64(left)))
			if int64(f*f) != left {
				return 0, fmt.Errorf("sqrt(%d) is not an int64eger", left)
			}
			return int64(f), nil
		}
	}
	// should not be reached
	return 0, fmt.Errorf("Unreachable state")
}

// String print64s representation of a node
func (n *Node) String() string {
	var left, right string
	if n.left != nil {
		left = n.left.String()
	}
	if n.right != nil {
		right = n.right.String()
	}
	if left == "" && right == "" {
		return strconv.FormatInt(n.num, 10)
	} else {
		switch n.op {
		case OpAdd:
			return fmt.Sprintf("%s + %s", left, right)
		case OpSub:
			return fmt.Sprintf("%s - (%s)", left, right)
		case OpMul, OpDiv, OpPow:
			return fmt.Sprintf("(%s) %s (%s)", left, opNames[n.op], right)
		case OpFact:
			return fmt.Sprintf("(%s)!", left)
		case OpSqrt:
			return fmt.Sprintf("sqrt(%s)", left)
		default:
			return "<UNDEFINED>" // Unreachable
		}
	}
}

// Copy creates a deep copy
func (n *Node) Copy() *Node {
	var left, right *Node
	if n.left != nil {
		left = n.left.Copy()
	}
	if n.right != nil {
		right = n.right.Copy()
	}
	return &Node{
		num:   n.num,
		left:  left,
		right: right,
		op:    n.op,
	}
}

func factorial(n int64) (int64, error) {
	if n < 0 || n > 20 {
		return 0, fmt.Errorf("%d is outside of factorial bounds", n)
	}
	f := n
	for i := n - 1; i > 0; i-- {
		f *= i
	}
	return f, nil
}

// Generate generates all trees with given depth and leaves.
// It just generates the structure, leaving ops and nums blank
func Generate(depth int, leaves []int64) []*Node {
	if len(leaves) <= 0 || depth < 0 || (depth == 0 && len(leaves) > 1) {
		return nil
	}
	if depth == 0 {
		return []*Node{&Node{num: leaves[0]}}
	}
	var nodes []*Node
	for d := 0; d <= depth-1; d++ {
		for _, c := range Generate(d, leaves) {
			nodes = append(nodes, &Node{
				left: c,
			})
		}
	}
	for l := 1; l < len(leaves); l++ {
		for d1 := 0; d1 <= depth-1; d1++ {
			for _, c := range Generate(d1, leaves[:l]) {
				for d2 := 0; d2 <= depth-1; d2++ {
					for _, c1 := range Generate(d2, leaves[l:]) {
						nodes = append(nodes, &Node{
							left:  c.Copy(),
							right: c1.Copy(),
						})
					}
				}
			}
		}
	}
	return nodes
}

// Generate all possible formulas with int64eger results
func (n *Node) IntegerResults() []*Node {
	if n.left == nil && n.right == nil {
		return []*Node{
			n.Copy(),
		}
	}
	var results []*Node
	if n.right == nil {
		for _, n1 := range n.left.IntegerResults() {
			for _, op := range []Op{OpFact, OpSqrt} {
				n2 := &Node{op: op, left: n1.Copy()}
				if _, err := n2.Eval(); err == nil {
					results = append(results, n2)
				}
			}
		}
	} else {
		for _, n1 := range n.left.IntegerResults() {
			for _, n2 := range n.right.IntegerResults() {
				for op := OpAdd; op <= OpPow; op++ {
					n3 := &Node{op: op, left: n1.Copy(), right: n2.Copy()}
					if _, err := n3.Eval(); err == nil {
						results = append(results, n3)
					}
				}
			}
		}
	}
	return results
}

func main() {
	max, _ := strconv.Atoi(os.Args[1])
	results := make(map[int64]*Node)
	for _, a := range [][]int64{
		{1, 9, 8, 9},
		{19, 8, 9},
		{1, 98, 9},
		{1, 9, 89},
		{1, 989},
		{19, 89},
		{198, 9},
		{1989},
	} {
		for level := 1; level <= max; level++ {
			for _, n := range Generate(level, a) {
				for _, n1 := range n.IntegerResults() {
					if v, err := n1.Eval(); err == nil {
						if results[v] == nil {
							results[v] = n1
						}
					}
				}
			}
		}
	}
	for v, n := range results {
		if v < 1000 && v > -1000 {
			fmt.Printf("%d\t= %s\n", v, n)
		}
	}
}