一个 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 ，整个过程可以在任意位置中断，可以在找到第一个答案后中止。