Advanced 24 game solver

main.go

package main

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

type Expression interface {
	Value() float64
	Repr() string
}

func CompareExpression(e1, e2 Expression) bool {
	if e1.Value() < e2.Value() {
		return true
	}
	if e1.Value() > e2.Value() {
		return false
	}
	return strings.Compare(e1.Repr(), e2.Repr()) < 0
}

func SortExpression(e []Expression) {
	sort.Slice(e, func(i, j int) bool {
		return CompareExpression(e[i], e[j])
	})
}

type AddGroup struct {
	Pos []Expression
	Neg []Expression
}

type MulGroup struct {
	Pos []Expression
	Neg []Expression
}

type Number struct {
	Val float64
	Str string
}

func (e *AddGroup) Value() float64 {
	var s float64 = 0
	for _, ee := range e.Pos {
		s += ee.Value()
	}
	for _, ee := range e.Neg {
		s -= ee.Value()
	}
	return s
}

func (e *AddGroup) Repr() string {
	SortExpression(e.Pos)
	SortExpression(e.Neg)
	var s strings.Builder
	for _, ee := range e.Pos {
		s.WriteString("+" + ee.Repr())
	}
	for _, ee := range e.Neg {
		s.WriteString("-" + ee.Repr())
	}
	return s.String()[1:]
}

func (e *MulGroup) Value() float64 {
	var s float64 = 1
	for _, ee := range e.Pos {
		s *= ee.Value()
	}
	for _, ee := range e.Neg {
		s /= ee.Value()
	}
	return s
}

func (e *MulGroup) Repr() string {
	SortExpression(e.Pos)
	SortExpression(e.Neg)
	var s strings.Builder
	for _, ee := range e.Pos {
		if _, ok := ee.(*Number); ok {
			s.WriteString("*" + ee.Repr())
		} else {
			s.WriteString("*(" + ee.Repr() + ")")
		}
	}
	for _, ee := range e.Neg {
		if _, ok := ee.(*Number); ok {
			s.WriteString("/" + ee.Repr())
		} else {
			s.WriteString("/(" + ee.Repr() + ")")
		}
	}
	return s.String()[1:]
}

func (n *Number) Value() float64 {
	return n.Val
}

func (n *Number) Repr() string {
	return n.Str
}

func JoinAddGroup(e1, e2 Expression, neg2 bool) *AddGroup {
	e := new(AddGroup)
	if a1, ok := e1.(*AddGroup); ok {
		e.Pos = append(e.Pos, a1.Pos...)
		e.Neg = append(e.Neg, a1.Neg...)
	} else {
		e.Pos = append(e.Pos, e1)
	}
	if a2, ok := e2.(*AddGroup); ok {
		if neg2 {
			e.Pos = append(e.Pos, a2.Neg...)
			e.Neg = append(e.Neg, a2.Pos...)
		} else {
			e.Pos = append(e.Pos, a2.Pos...)
			e.Neg = append(e.Neg, a2.Neg...)
		}
	} else {
		if neg2 {
			e.Neg = append(e.Neg, e2)
		} else {
			e.Pos = append(e.Pos, e2)
		}
	}
	return e
}

func JoinMulGroup(e1, e2 Expression, neg2 bool) *MulGroup {
	e := new(MulGroup)
	if a1, ok := e1.(*MulGroup); ok {
		e.Pos = append(e.Pos, a1.Pos...)
		e.Neg = append(e.Neg, a1.Neg...)
	} else {
		e.Pos = append(e.Pos, e1)
	}
	if a2, ok := e2.(*MulGroup); ok {
		if neg2 {
			e.Pos = append(e.Pos, a2.Neg...)
			e.Neg = append(e.Neg, a2.Pos...)
		} else {
			e.Pos = append(e.Pos, a2.Pos...)
			e.Neg = append(e.Neg, a2.Neg...)
		}
	} else {
		if neg2 {
			e.Neg = append(e.Neg, e2)
		} else {
			e.Pos = append(e.Pos, e2)
		}
	}
	return e
}

var (
	target     float64
	allAnswers bool
	answers    []string
)

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

func EvalResult(e Expression) bool {
	result := CompareFloat(e.Value(), target, 1e-6)
	if result {
		s := e.Repr()
		duplicate := false
		for _, ans := range answers {
			if ans == s {
				duplicate = true
				break
			}
		}
		if !duplicate {
			fmt.Println(s, "=", target)
			answers = append(answers, s)
		}
	}
	return result && !allAnswers
}

func Find24(nodes []Expression) bool {
	if len(nodes) == 1 {
		return EvalResult(nodes[0])
	}
	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, nil)
			if i < j {
				newNodes[len(nodes)-2] = JoinAddGroup(nodes[i], nodes[j], false)
				result = result || Find24(newNodes)
				newNodes[len(nodes)-2] = JoinMulGroup(nodes[i], nodes[j], false)
				result = result || Find24(newNodes)
			}
			newNodes[len(nodes)-2] = JoinAddGroup(nodes[i], nodes[j], true)
			result = result || Find24(newNodes)
			newNodes[len(nodes)-2] = JoinMulGroup(nodes[i], nodes[j], true)
			result = result || Find24(newNodes)
		}
	}
	return result && !allAnswers
}

func main() {
	flag.Float64Var(&target, "t", 24.0, "target value")
	flag.BoolVar(&allAnswers, "a", false, "find all solutions")
	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] = &Number{Val: value, Str: arg}
	}

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

	Find24(nums)
	if len(answers) == 0 {
		fmt.Println("No solution")
	}
}