綜合前面的介紹,這里我們給出最終的 24 點(diǎn)游戲的代碼:
import scala.collection.mutable.Stack
trait BinaryOp{
val op:String
def apply(expr1:String,expr2:String) = expr1 + op + expr2
def unapply(str:String) :Option[(String,String)] ={
val index=str indexOf (op)
if(index>0)
Some(str substring(0,index),str substring(index+1))
else None
}
}
class Rational (n:Int, d:Int) {
require(d!=0)
private val g =gcd (n.abs,d.abs)
val numer =n/g
val denom =d/g
override def toString = numer + "\\" +denom
def +(that:Rational) =
new Rational(
numer * that.denom + that.numer* denom,
denom * that.denom
)
def -(that:Rational) =
new Rational(
numer * that.denom - that.numer* denom,
denom * that.denom
)
def * (that:Rational) =
new Rational( numer * that.numer, denom * that.denom)
def / (that:Rational) =
new Rational( numer * that.denom, denom * that.numer)
def this(n:Int) = this(n,1)
private def gcd(a:Int,b:Int):Int =
if(b==0) a else gcd(b, a % b)
}
object Bracket{
def matchBracket(str:String):Option[(Int,Int)] ={
val left = str.indexOf('(')
if(left >=0) {
val stack = Stack[Char]()
val remaining = str substring (left+1)
var index=0
var right=0
for(c <-remaining if right==0){
index=index + 1
c match{
case '(' => stack push c
case ')' => if (stack isEmpty) right= left+index else stack pop
case _ =>
}
}
Some(left,right)
}else None
}
def apply(part1:String,expr:String,part2:String) =part1+ "(" + expr + ")"+ part2
def unapply(str:String) :Option[(String,String,String)] ={
Bracket.matchBracket(str) match{
case Some((left:Int,right:Int)) =>{
val part1 = if (left == 0) "" else str substring(0, left )
val expr = str substring(left + 1, right)
val part2 = if (right == (str length)-1) "" else str substring (right+1)
Some(part1, expr, part2)
}
case _ => None
}
}
}
object Multiply extends {val op="*"} with BinaryOp
object Divide extends {val op="/"} with BinaryOp
object Add extends {val op="+"} with BinaryOp
object Subtract extends {val op="-"} with BinaryOp
object Rational extends {val op="\\"} with BinaryOp
object Test extends App{
val templates=List(
"N*N-N+N",
"(N-N)*N*N",
"N*N+N*N",
"(N+N)*N*N",
"N*N*N*N",
"(N+N*N)*N",
"(N*N-N)*N",
"N*N+N+N",
"(N/N-N)*N",
"(N-(N-N))*N",
"N-(N-N-N)",
"N+N-(N-N)",
"N*(N/N-N)",
"(N-N*N)*N",
"N*(N-N)+N",
"N+N+N/N",
"(N-N)*(N-N)",
"N+N*N/N",
"N*N/(N-N)",
"(N+N)*(N+N)",
"(N-N)*N/N",
"N+(N+N)/N",
"N*N/(N+N)",
"(N+N)*N/N",
"(N*N+N)*N",
"(N*N-N)/N",
"(N/N+N)*N",
"N*N/N/N",
"N+N+N-N",
"N-(N-N)+N",
"N/(N-N/N)",
"N+(N-N)*N",
"(N+N+N)*N",
"N+N*N-N",
"N*N-N/N",
"(N+N)*N-N",
"(N+N)*(N-N)",
"(N-N/N)*N",
"N*(N+N)+N",
"N*N+N/N",
"N*N/N-N",
"(N+N/N)*N",
"N*N*N/N",
"(N+N*N)/N",
"N+N*N+N",
"N-(N-N)*N",
"(N-(N+N))*N",
"N*N-N-N",
"N+N/N+N",
"(N-N)*N-N",
"(N+N)/N+N",
"N*N+N-N",
"N/N+N+N",
"N*N*N-N",
"(N*N+N)/N",
"N+N+N*N",
"N*(N-N)/N",
"N/N*N+N",
"N+N*N*N",
"N+N+N+N",
"N*N/(N*N)",
"N+(N+N)*N",
"(N-N)*N+N",
"(N+N+N)/N",
"(N+N)*N+N",
"N*N*N+N",
"N*N-(N-N)",
"N*N-(N+N)",
"(N-N-N)*N",
"N*N/N+N",
"(N+N-N)*N",
"N/(N/N-N)",
"N*N-N*N"
)
def eval(str:String):Rational = {
str match {
case Bracket(part1, expr, part2) => eval(part1 + eval(expr) + part2)
case Add(expr1, expr2) => eval(expr1) + eval(expr2)
case Subtract(expr1, expr2) => eval(expr1) - eval(expr2)
case Multiply(expr1, expr2) => eval(expr1) * eval(expr2)
case Divide(expr1, expr2) => eval(expr1) / eval(expr2)
case "" => new Rational(0, 1)
case Rational(expr1, expr2) => new Rational(expr1.trim toInt, expr2.trim toInt)
case _ => new Rational(str.trim toInt, 1)
}
}
def calculate(template:String,numbers:List[Int])={
val values=template.split('N')
var expression=""
for(i <- 0 to 3) expression=expression+values(i) + numbers(i)
if (values.length==5) expression=expression+values(4)
(expression,template,eval(expression))
}
def cal24(input:List[Int])={
var found = false
for (template <- templates; list <- input.permutations ) {
try {
val (expression, tp, result) = calculate(template, list)
if (result.numer == 24 && result.denom == 1) {
println(input + ":" + tp + ":" + expression)
found = true
}
} catch {
case e:Throwable=>
}
}
if (!found) {
println(input+":"+"no result")
}
}
def cal24once(input:List[Int])={
var found = false
for (template <- templates; list <- input.permutations if(!found)) {
try {
val (expression, tp, result) = calculate(template, list)
if (result.numer == 24 && result.denom == 1) {
println(input + ":" + tp + ":" + expression)
found = true
}
} catch {
case e:Throwable=>
}
}
if (!found) {
println(input+":"+"no result")
}
}
println(cal24once(List(5,5,5,1)))
}
下面給出所有從1到10的四個(gè)數(shù)字有解的結(jié)果:
輸入 | 模板 | 結(jié)果 |
---|---|---|
List(1,1,1,8) | (N+N+N)*N | (1+1+1)*8 |
List(1,1,2,10) | (N+N)*(N+N) | (1+1)*(2+10) |
List(1,1,2,6) | (N+N)NN | (1+1)26 |
List(1,1,2,7) | (N+N)*(N+N) | (1+2)*(1+7) |
List(1,1,2,8) | (N+N)NN | (1+2)18 |
List(1,1,2,9) | (N+N)*(N-N) | (1+2)*(9-1) |
List(1,1,3,10) | (N-(N+N))*N | (10-(1+1))*3 |
List(1,1,3,4) | (N+N)NN | (1+1)34 |
List(1,1,3,5) | (N+N)*(N+N) | (1+3)*(1+5) |
List(1,1,3,6) | (N+N)NN | (1+3)16 |
List(1,1,3,7) | (N+N)NN | (1+7)13 |
List(1,1,3,8) | N*N-N+N | 3*8-1+1 |
List(1,1,3,9) | (N-N)NN | (9-1)13 |
List(1,1,4,10) | N*(N+N)+N | 10*(1+1)+4 |
List(1,1,4,4) | (N+N+N)*N | (1+1+4)*4 |
List(1,1,4,5) | (N+N)NN | (1+5)14 |
List(1,1,4,6) | N*N-N+N | 4*6-1+1 |
List(1,1,4,7) | (N-N)NN | (7-1)14 |
List(1,1,4,8) | (N-N)NN | (4-1)18 |
List(1,1,4,9) | (N-N)*(N-N) | (1-4)*(1-9) |
List(1,1,5,5) | (NN-N)N | (55-1)1 |
List(1,1,5,6) | (N-N)NN | (5-1)16 |
List(1,1,5,7) | (N-N)*(N-N) | (1-5)*(1-7) |
List(1,1,5,8) | (N-(N+N))*N | (5-(1+1))*8 |
List(1,1,6,6) | (N+N)*(N+N) | (1+1)*(6+6) |
List(1,1,6,8) | N*N/(N+N) | 6*8/(1+1) |
List(1,1,6,9) | N*(N+N)+N | 9*(1+1)+6 |
List(1,1,7,10) | N*(N+N)+N | 7*(1+1)+10 |
List(1,1,8,8) | N*(N+N)+N | 8*(1+1)+8 |
List(1,2,2,10) | (N+N)NN | (2+10)12 |
List(1,2,2,4) | (N+N)NN | (1+2)24 |
List(1,2,2,5) | (N+N)NN | (1+5)22 |
List(1,2,2,6) | (N+N)NN | (2+2)16 |
List(1,2,2,7) | (N-N)NN | (7-1)22 |
List(1,2,2,8) | (NN-N)N | (22-1)8 |
List(1,2,2,9) | (N+N+N)*N | (1+2+9)*2 |
List(1,2,3,10) | (N-N)NN | (10-2)13 |
List(1,2,3,3) | (N+N)NN | (1+3)23 |
List(1,2,3,4) | NNN*N | 123*4 |
List(1,2,3,5) | (N-N)NN | (5-1)23 |
List(1,2,3,6) | (N-N)NN | (3-1)26 |
List(1,2,3,7) | N*N+N+N | 3*7+1+2 |
List(1,2,3,8) | (N-N)NN | (2-1)38 |
List(1,2,3,9) | (N+N)NN | (3+9)12 |
List(1,2,4,10) | NN+NN | 14+210 |
List(1,2,4,4) | (N-N)NN | (4-1)24 |
List(1,2,4,5) | (N-(N-N))*N | (2-(1-5))*4 |
List(1,2,4,6) | (N-N)NN | (2-1)46 |
List(1,2,4,7) | (N-(N-N))*N | (1-(2-7))*4 |
List(1,2,4,8) | (N-N)NN | (8-2)14 |
List(1,2,4,9) | (N-(N-N))*N | (4-(1-9))*2 |
List(1,2,5,10) | N*N-N+N | 2*10-1+5 |
List(1,2,5,5) | N*N-N+N | 5*5-2+1 |
List(1,2,5,6) | (N-(N-N))*N | (1-(2-5))*6 |
List(1,2,5,7) | (N+N)NN | (5+7)12 |
List(1,2,5,8) | (N-N)NN | (5-2)18 |
List(1,2,5,9) | N*N+N+N | 2*9+1+5 |
List(1,2,6,10) | (N/N-N)*N | (10/2-1)*6 |
List(1,2,6,6) | (N-N)NN | (6-2)16 |
List(1,2,6,7) | (N-(N-N))*N | (6-(1-7))*2 |
List(1,2,6,8) | N*N/N/N | 1*6/2/8 |
List(1,2,6,9) | NN+NN | 16+29 |
List(1,2,7,10) | NN+NN | 110+27 |
List(1,2,7,7) | (N*N-N)/N | (7*7-1)/2 |
List(1,2,7,8) | N*N+N+N | 2*8+1+7 |
List(1,2,7,9) | N*N-N+N | 2*9-1+7 |
List(1,2,8,10) | N*(N-N)+N | 2*(8-1)+10 |
List(1,2,8,8) | NN+NN | 18+28 |
List(1,2,8,9) | N*N-N+N | 2*8-1+9 |
List(1,3,10,10) | N+N+N+N | 1+3+10+10 |
List(1,3,3,10) | (N-(N-N))*N | (1-(3-10))*3 |
List(1,3,3,3) | (NN-N)N | (33-1)3 |
List(1,3,3,4) | (N-N)NN | (3-1)34 |
List(1,3,3,5) | (N+N)NN | (3+5)13 |
List(1,3,3,6) | (N-(N-N))*N | (3-(1-6))*3 |
List(1,3,3,7) | NN+NN | 13+37 |
List(1,3,3,8) | N*(N-N)+N | 3*(8-1)+3 |
List(1,3,3,9) | (NN-N)N | (39-3)1 |
List(1,3,4,10) | N*(N-N)+N | 10*(3-1)+4 |
List(1,3,4,4) | (N+N)NN | (4+4)13 |
List(1,3,4,5) | N*N+N+N | 4*5+1+3 |
List(1,3,4,6) | N/(N-N/N) | 6/(1-3/4) |
List(1,3,4,7) | N*N-N+N | 3*7-1+4 |
List(1,3,4,8) | (N-(N-N))*N | (1-(3-8))*4 |
List(1,3,4,9) | N*N-N+N | 3*9-4+1 |
List(1,3,5,10) | N*N-N+N | 3*5-1+10 |
List(1,3,5,6) | N*N+N+N | 3*6+1+5 |
List(1,3,5,7) | (N+N)*(N-N) | (1+5)*(7-3) |
List(1,3,5,8) | N*N+N+N | 3*5+1+8 |
List(1,3,5,9) | NN+NN | 19+35 |
List(1,3,6,10) | (NN-N)N | (310-6)1 |
List(1,3,6,6) | NN+NN | 16+36 |
List(1,3,6,7) | N*N-N+N | 3*6-1+7 |
List(1,3,6,8) | (N-N)NN | (6-3)18 |
List(1,3,6,9) | N*(N-N)+N | 3*(6-1)+9 |
List(1,3,7,10) | N*N-N+N | 3*10-7+1 |
List(1,3,7,7) | (N-N)*(N-N) | (1-7)*(3-7) |
List(1,3,7,8) | N/(N-N/N) | 3/(1-7/8) |
List(1,3,7,9) | (N+N)*N/N | (1+7)*9/3 |
List(1,3,8,10) | (N-N)*N/N | (10-1)*8/3 |
List(1,3,8,8) | N*(N-N)+N | 8*(3-1)+8 |
List(1,3,8,9) | N*N/N/N | 1*8/3/9 |
List(1,3,9,10) | (N+N)*N-N | (1+10)*3-9 |
List(1,3,9,9) | (N-N)*N/N | (9-1)*9/3 |
List(1,4,10,10) | N*N+N+N | 1*4+10+10 |
List(1,4,4,10) | (N-N)NN | (10-4)14 |
List(1,4,4,4) | (N+N)*(N-N) | (4+4)*(4-1) |
List(1,4,4,5) | NN+NN | 14+45 |
List(1,4,4,6) | N*(N-N)+N | 4*(6-1)+4 |
List(1,4,4,7) | (NN-N)N | (47-4)1 |
List(1,4,4,8) | NN+NN | 18+44 |
List(1,4,4,9) | N*N-N+N | 4*4-1+9 |
List(1,4,5,10) | (N-(N-N))*N | (1-(5-10))*4 |
List(1,4,5,5) | N*N-N+N | 4*5-1+5 |
List(1,4,5,6) | N/(N-N/N) | 4/(1-5/6) |
List(1,4,5,7) | N*N-N+N | 4*7-5+1 |
List(1,4,5,8) | N*(N-N)+N | 4*(5-1)+8 |
List(1,4,5,9) | N*(N-N)+N | 5*(4-1)+9 |
List(1,4,6,10) | (N-N)*N-N | (4-1)*10-6 |
List(1,4,6,6) | N*(N-N)+N | 6*(4-1)+6 |
List(1,4,6,7) | (N-(N-N))*N | (1-(4-7))*6 |
List(1,4,6,8) | (N-N)NN | (8-4)16 |
List(1,4,6,9) | (N-(N+N))*N | (9-(1+4))*6 |
List(1,4,7,7) | (N+N)*(N-N) | (1+7)*(7-4) |
List(1,4,7,8) | (N-N)NN | (7-4)18 |
List(1,4,7,9) | (N-N)*(N-N) | (1-9)*(4-7) |
List(1,4,8,8) | (NN-N)N | (48-8)1 |
List(1,4,8,9) | N*N-N+N | 4*8-9+1 |
List(1,4,9,10) | N+N+N+N | 1+4+9+10 |
List(1,5,10,10) | N+N-(N-N) | 5+10-(1-10) |
List(1,5,5,10) | (N-N)*N-N | (10-5)*5-1 |
List(1,5,5,5) | (N-N/N)*N | (5-1/5)*5 |
List(1,5,5,6) | (N+N)*N-N | (1+5)*5-6 |
List(1,5,5,9) | (N+N)*(N-N) | (1+5)*(9-5) |
List(1,5,6,10) | (N+N)*(N-N) | (1+5)*(10-6) |
List(1,5,6,6) | (NN-N)N | (56-6)1 |
List(1,5,6,7) | N*N-N+N | 5*6-7+1 |
List(1,5,6,8) | (N-(N-N))*N | (1-(5-8))*6 |
List(1,5,6,9) | (N-N)NN | (9-5)16 |
List(1,5,7,10) | (N/N+N)*N | (7/5+1)*10 |
List(1,5,7,8) | (N-(N-N))*N | (1-(5-7))*8 |
List(1,5,7,9) | (N-N)*(N-N) | (1-7)*(5-9) |
List(1,5,8,10) | (N/N+N)*N | (10/5+1)*8 |
List(1,5,8,8) | (N-N)NN | (8-5)18 |
List(1,5,8,9) | (N-N)*(N-N) | (1-9)*(5-8) |
List(1,5,9,10) | N*N+N+N | 1*5+9+10 |
List(1,5,9,9) | N+N+N+N | 1+5+9+9 |
List(1,6,6,10) | (N-N)NN | (10-6)16 |
List(1,6,6,6) | (N-N)*N-N | (6-1)*6-6 |
List(1,6,6,8) | N/(N-N/N) | 6/(1-6/8) |
List(1,6,6,9) | (N-(N-N))*N | (1-(6-9))*6 |
List(1,6,7,10) | (N-(N-N))*N | (1-(7-10))*6 |
List(1,6,7,9) | (N+N)*(N-N) | (1+7)*(9-6) |
List(1,6,8,10) | N*N+N+N | 1*6+8+10 |
List(1,6,8,8) | (N-(N-N))*N | (1-(6-8))*8 |
List(1,6,8,9) | (N-N)NN | (9-6)18 |
List(1,6,9,10) | N+N-(N-N) | 6+9-(1-10) |
List(1,6,9,9) | N*N+N+N | 1*6+9+9 |
List(1,7,7,10) | N*N+N+N | 1*7+7+10 |
List(1,7,7,9) | N+N+N+N | 1+7+7+9 |
List(1,7,8,10) | (N-N)NN | (10-7)18 |
List(1,7,8,8) | N+N+N+N | 1+7+8+8 |
List(1,7,8,9) | N*N+N+N | 1*7+8+9 |
List(1,7,9,10) | (N-N)*(N-N) | (1-9)*(7-10) |
List(1,7,9,9) | N+N-(N-N) | 7+9-(1-9) |
List(1,8,8,10) | (N-(N-N))*N | (1-(8-10))*8 |
List(1,8,8,8) | N*N+N+N | 1*8+8+8 |
List(1,8,8,9) | N+N-(N-N) | 8+8-(1-9) |
List(2,2,10,10) | N*N+N+N | 2*2+10+10 |
List(2,2,2,10) | NN+NN | 22+210 |
List(2,2,2,3) | (N+N)NN | (2+2)23 |
List(2,2,2,4) | (N+N)NN | (2+4)22 |
List(2,2,2,5) | (N+NN)N | (2+25)2 |
List(2,2,2,7) | (NN-N)N | (27-2)2 |
List(2,2,2,8) | (N-N)NN |