一个 Scala 的凑 24 程序
source link: https://blog.henix.info/blog/scala-program-solve-24-game/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
一个 Scala 的凑 24 程序
最后更新日期：2014-08-09
闲来翻以前的关于“凑24”的文章和程序，我发现“凑24”是个很有意思的问题，因为它涉及一个问题：程序生成。你能否用一些操作数，生成一个程序，使得该程序满足一条性质？你能否提供较好的性能？
几年过去，我又学会了更多的编程技巧，能否把“凑24”这个问题解决得更完美呢？程序能否更容易扩展？
- 能否很容易地添加单目或双目运算符，比如阶乘、乘方？
- 能否很容易地扩充到用任意多个数字凑 x ？
用这两条标准看我以前的 Lua 和 Prolog 程序，恐怕都不合格：程序中充斥着大量手算出来的表格和 Magic Number 。所以我重新思考了这个问题，给出下面这个 Scala 程序，希望这次没那么多 Magic Number 。
先定义一种栈语言，这种栈语言有两种元素：操作数和运算符。运算符的“类型”可以表为一个整数，即它让栈减少（为负则是增加）多少。先以类型生成合法的抽象栈程序（合法即 type check ，而这里 type check 的定义是 所有运算符在求值时都有足够的操作数，或者说栈在任意时刻非空），然后将某个类型的具体的运算符填充进去，最后填充操作数（的所有排列）。
import scala.annotation.tailrec
def genAbstractProgram(stack: List[Int], sum: Int, typeCounts: Array[Int]): Iterator[List[Int]] = {
if (typeCounts.forall(_ == 0)) {
Iterator(stack.reverse)
} else {
Iterator.range(0, typeCounts.length)
.filter(i => typeCounts(i) > 0 && sum >= i - 1)
.flatMap { i =>
val newsum = sum - (i - 1)
val newCounts = typeCounts.clone()
newCounts(i) -= 1
genAbstractProgram(-(i-1) :: stack, newsum, newCounts)
}
}
}
type Value = Double
sealed trait StackElem
case class Operand(value: Value = 0) extends StackElem
case class Operator(arity: Int, invoke: List[Value] => Value, print: List[String] => String) extends StackElem
@tailrec
def eval(prog: List[StackElem], stack: List[Value]): Value = prog match {
case List() => stack.head
case Operand(x) :: rest => eval(rest, x :: stack)
case (op: Operator) :: rest => eval(rest, op.invoke(stack) :: stack.drop(op.arity))
}
@tailrec
def prettyPrint(prog: List[StackElem], stack: List[String]): String = prog match {
case List() => stack.head
case Operand(x) :: rest => prettyPrint(rest, x.toString :: stack)
case (op: Operator) :: rest => prettyPrint(rest, op.print(stack) :: stack.drop(op.arity))
}
val add = Operator(2, { case b :: a :: _ => a + b }, { case b :: a :: _ => s"($a + $b)" })
val sub = Operator(2, { case b :: a :: _ => a - b }, { case b :: a :: _ => s"($a - $b)" })
val mul = Operator(2, { case b :: a :: _ => a * b }, { case b :: a :: _ => s"($a * $b)" })
val div = Operator(2, { case b :: a :: _ => a / b }, { case b :: a :: _ => s"($a / $b)" })
val sqr = Operator(1, { case a :: _ => a * a }, { case a :: _ => s"($a^2)" })
val availableOps: Array[List[Operator]] = Array(
List(),
List(sqr),
List(add, sub, mul, div)
)
def selectEach[A](list: List[List[A]]): Iterator[List[A]] = list match {
case List() => Iterator(List())
case head :: others => selectEach(others).flatMap(c => head.map(_ :: c))
}
val numbers = Array(3, 3, 8, 8)
val absPrograms = genAbstractProgram(List(1), 0, Array(numbers.size - 1, 1, 3))
val programs = absPrograms
.map(_.map(d => if (d == 1) List(Operand()) else availableOps(-d+1)))
.flatMap(selectEach)
val solutions = programs.flatMap(prog => {
numbers.permutations.map { arguments =>
var i = -1
prog.map(_ match {
case Operand(_) =>
i += 1
Operand(arguments(i))
case op: Operator => op
})
}
})
.filter(prog => try {
Math.abs(eval(prog, List()) - 24.0) < 0.00001
} catch {
case e: ArithmeticException => false
})
println(solutions.map(prog => prettyPrint(prog, List())).mkString("\n"))运行结果（用 + - * / 和一次平方运算凑 24）：
(3.0 * (8.0 * ((3.0^2) - 8.0)))
(8.0 * (3.0 * ((3.0^2) - 8.0)))
(3.0 * (8.0 / ((3.0^2) - 8.0)))
(8.0 * (3.0 / ((3.0^2) - 8.0)))
以下省略...其中的 genAbstractProgram 相当于我在逆波兰式与卡塔兰数一文中所说的生成所有 n 个 1 和 n 个 -1 的排列的程序，不过这里排列的是 a0 个 1 和 a1 个 0 和 a2 个 -1 和 … 和 ai 个 -(i-1) 。
性能：程序的运行时间肯定是指数级的，这没办法减少，但是可以实现成 lazy 的：使用 Iterator ，整个过程可以在任意位置中断，可以在找到第一个答案后中止。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK