Basic 24 game solver

main.go

package main

import (
	"flag"
	"fmt"
	"math"
	"math/rand"
	"strconv"
	"time"
)

type Expression struct {
	value float64
	op    rune
	repr  string
}

var target float64

func CompareFloat(a, b, threshold float64) bool {
	return math.Abs(a-b) < threshold
}

func JoinExpression(e1, e2 *Expression, op rune) *Expression {
	var value float64
	var repr string
	switch op {
	case '+':
		value = e1.value + e2.value
		repr = fmt.Sprintf("%s+%s", e1.repr, e2.repr)
	case '-':
		value = e1.value - e2.value
		rhs := e2.repr
		if e2.op == '+' || e2.op == '-' {
			rhs = fmt.Sprintf("(%s)", e2.repr)
		}
		repr = fmt.Sprintf("%s-%s", e1.repr, rhs)
	case '*':
		value = e1.value * e2.value
		lhs := e1.repr
		if e1.op == '+' || e1.op == '-' {
			lhs = fmt.Sprintf("(%s)", e1.repr)
		}
		rhs := e2.repr
		if e2.op == '+' || e2.op == '-' {
			rhs = fmt.Sprintf("(%s)", e2.repr)
		}
		repr = fmt.Sprintf("%s*%s", lhs, rhs)
	case '/':
		value = e1.value / e2.value
		lhs := e1.repr
		if e1.op == '+' || e1.op == '-' {
			lhs = fmt.Sprintf("(%s)", e1.repr)
		}
		rhs := e2.repr
		if e2.op == '+' || e2.op == '-' || e2.op == '*' || e2.op == '/' {
			rhs = fmt.Sprintf("(%s)", e2.repr)
		}
		repr = fmt.Sprintf("%s/%s", lhs, rhs)
	}
	return &Expression{value: value, op: op, repr: repr}
}

func Find24(nodes []*Expression) bool {
	if len(nodes) == 1 {
		result := CompareFloat(nodes[0].value, target, 1e-6)
		if result {
			fmt.Println(nodes[0].repr, "=", target)
		}
		return result
	}
	result := false
	for i := 0; i < len(nodes); i++ {
		for j := 0; j < len(nodes); j++ {
			if i == j {
				continue
			}
			newNodes := make([]*Expression, 0, len(nodes)-1)
			for k := 0; k < len(nodes); k++ {
				if k == i || k == j {
					continue
				}
				newNodes = append(newNodes, nodes[k])
			}
			newNodes = append(newNodes, new(Expression))
			if i < j {
				newNodes[len(nodes)-2] = JoinExpression(nodes[i], nodes[j], '+')
				result = result || Find24(newNodes)
				newNodes[len(nodes)-2] = JoinExpression(nodes[i], nodes[j], '*')
				result = result || Find24(newNodes)
			}
			newNodes[len(nodes)-2] = JoinExpression(nodes[i], nodes[j], '-')
			result = result || Find24(newNodes)
			newNodes[len(nodes)-2] = JoinExpression(nodes[i], nodes[j], '/')
			result = result || Find24(newNodes)
		}
	}
	return result
}

func main() {
	flag.Float64Var(&target, "t", 24.0, "target value")
	flag.Parse()

	nums := make([]*Expression, len(flag.Args()))
	for i, arg := range flag.Args() {
		value, err := strconv.ParseFloat(arg, 64)
		if err != nil {
			panic(err)
		}
		nums[i] = &Expression{value: value, op: '.', repr: arg}
	}

	rand.Seed(time.Now().UnixNano())
	for i := range nums {
		j := rand.Intn(i + 1)
		nums[i], nums[j] = nums[j], nums[i]
	}

	if !Find24(nums) {
		fmt.Println("No solution")
	}
}