Anonymous user
24 game/Solve: Difference between revisions
→{{header|Go}}
(→{{header|C}}: replaced incorrect code.) |
|||
Line 975:
"8383/-/"</lang>
=={{header|Go}}==
<lang C>package main
import (
"fmt"
"rand"
"time"
)
const (
op_num = iota
op_add
op_sub
op_mul
op_div
)
type frac struct {
num, denom int
}
// Expression: can either be a single number, or a result of binary
// operation from left and right node
type Expr struct {
op int
left, right *Expr
value frac
}
var n_cards = 4
var goal = 24
var digit_range = 9
func (x *Expr) String() string {
if x.op == op_num {
return fmt.Sprintf("%d", x.value.num)
}
var bl1, br1, bl2, br2, opstr string
switch {
case x.left.op == op_num:
case x.left.op >= x.op:
case x.left.op == op_add && x.op == op_sub:
bl2, br2 = "(", ")"
default:
bl1, br1 = "(", ")"
}
if x.right.op == op_num || x.op < x.right.op{
bl2, br2 = "", ""
} else {
bl2, br2 = "(", ")"
}
switch {
case x.op == op_add: opstr = " + "
case x.op == op_sub: opstr = " - "
case x.op == op_mul: opstr = " * "
case x.op == op_div: opstr = " / "
}
return bl1 + x.left.String() + br1 + opstr +
bl2 + x.right.String() + br2
}
func expr_eval(x *Expr) (f frac) {
if x.op == op_num { return x.value }
l, r := expr_eval(x.left), expr_eval(x.right)
switch {
case x.op == op_add:
f.num = l.num * r.denom + l.denom * r.num
f.denom = l.denom * r.denom
return
case x.op == op_sub:
f.num = l.num * r.denom - l.denom * r.num
f.denom = l.denom * r.denom
return
case x.op == op_mul:
f.num = l.num * r.num
f.denom = l.denom * r.denom
return
case x.op == op_div:
f.num = l.num * r.denom
f.denom = l.denom * r.num
return
}
return
}
func solve(ex_in []*Expr) bool {
// only one expression left, meaning all numbers are arranged into
// a binary tree, so evaluate and see if we get 24
if len(ex_in) == 1 {
f := expr_eval(ex_in[0])
if f.denom != 0 && f.num == f.denom * goal {
fmt.Println(ex_in[0].String())
return true
}
return false
}
var node Expr
ex := make([]*Expr, len(ex_in) - 1)
// try to combine a pair of expressions into one, thus reduce
// the list length by 1, and recurse down
for i := range ex {
copy(ex[i:len(ex)], ex_in[i + 1:len(ex_in)])
ex[i] = &node
for j := i + 1; j < len(ex_in); j++ {
node.left = ex_in[i]
node.right = ex_in[j]
// try all 4 operators
for o := op_add; o <= op_div; o++ {
node.op = o
if (solve(ex)) { return true }
}
// also - and / are not commutative, so swap arguments
node.left = ex_in[j]
node.right = ex_in[i]
node.op = op_sub
if (solve(ex)) { return true }
node.op = op_div
if (solve(ex)) { return true }
if j < len(ex) {
ex[j] = ex_in[j]
}
}
ex[i] = ex_in[i]
}
return false
}
func main() {
cards := make([]*Expr, n_cards)
rand.Seed(time.Seconds())
for k := 0; k < 10; k++ {
for i := 0; i < n_cards; i++ {
cards[i] = &Expr{ op_num, nil, nil,
frac{rand.Intn(digit_range - 1) + 1, 1}}
fmt.Printf(" %d", cards[i].value.num)
}
fmt.Print(": ")
if ! solve(cards) {
fmt.Println("No solution")
}
}
}</lang>Output:<lang> 8 6 7 6: No solution
7 2 6 6: (7 - 2) * 6 - 6
4 8 7 3: 4 * (7 - 3) + 8
3 8 8 7: 3 * 8 * (8 - 7)
5 7 3 7: No solution
5 7 8 3: 5 * 7 - 8 - 3
3 6 5 2: ((3 + 5) * 6) / 2
8 4 5 4: (8 - 4) * 5 + 4
2 2 8 8: (2 + 2) * 8 - 8
6 8 8 2: 6 + 8 + 8 + 2</lang>
=={{header|Haskell}}==
| |||