Skip to content

Instantly share code, notes, and snippets.

@iBug
Last active April 29, 2022 11:57
Show Gist options
  • Save iBug/62610c759f7702071baaf884301ae067 to your computer and use it in GitHub Desktop.
Save iBug/62610c759f7702071baaf884301ae067 to your computer and use it in GitHub Desktop.
Basic 24 game solver
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")
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment