計算 24 的算法

有了前面的準備工作，我們現(xiàn)在可以給出二十四游戲的算法，首先我們合并表示式模板和輸入的四個數(shù)字，計算出結(jié)果：

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))
  }

做些簡單的測試如下：

scala> calculate("N/N*N+N",List(6,9,9,10))
res0: (String, String, Rational) = (6/9*9+10,N/N*N+N,16\1)

scala> calculate("N/N*N+N",List(9,6,10,9))
res1: (String, String, Rational) = (9/6*10+9,N/N*N+N,24\1)

scala> calculate("(N-N/N)*N",List(5,1,5,5))
res2: (String, String, Rational) = ((5-1/5)*5,(N-N/N)*N,24\1)

我們讓函數(shù) calculate 返回三個值，合成的表達式，使用的模板，計算的結(jié)果（分數(shù)形式），我們使用一個三元組作為返回結(jié)果，這里也可以看到 Scala 函數(shù)返回，無需使用 return，函數(shù)體的最后一條語句的值作為返回結(jié)果。

說到這里，在之前的 Rational 的實現(xiàn)和 eval 函數(shù)的實現(xiàn)有一個小錯誤（表達式出現(xiàn)中的歧義），之前 Rational 的字符表現(xiàn)形式為

override def toString = numer + "/" +denom

使用到的“/”和 我們使用的四則運算的除號一樣,這樣對于這樣的表達式 8/1/3,就有兩種解釋 (8/1)/3 其中8/1 為計算的中間結(jié)果（Rational 對象，“/”為 Rational 字符串形式中的/），計算結(jié)果為８／３。

另外一種解釋為 8/（1/3）其中1/3為輸入時的除號。 為避免這種歧義，我們將 Rational 的“/”改為”\”，修改之前的相關(guān)定義：

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
  ...
 }

object Rational  extends {val op="\\"} with BinaryOp

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)

    }
} 

我們有了 calculate 函數(shù)之后，就可以根據(jù)數(shù)字的全排列，和可能的表達式模板，設(shè)計出 24 游戲的窮舉算法：

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")
    }
}

這個算法列出所有可能的算法，比如：

scala> cal24(List(5,5,5,1))
List(5, 5, 5, 1):(N-N/N)*N:(5-1/5)*5

scala> cal24(List(3,3,8,8))
List(3, 3, 8, 8):N/(N-N/N):8/(3-8/3)

scala> cal24(List(5,6,7,8))
List(5, 6, 7, 8):(N-(N-N))*N:(5-(8-7))*6
List(5, 6, 7, 8):(N-(N-N))*N:(7-(8-5))*6
List(5, 6, 7, 8):N*N/(N-N):6*8/(7-5)
List(5, 6, 7, 8):N*N/(N-N):8*6/(7-5)
List(5, 6, 7, 8):(N+N)*(N-N):(5+7)*(8-6)
List(5, 6, 7, 8):(N+N)*(N-N):(7+5)*(8-6)
List(5, 6, 7, 8):(N-N-N)*N:(5-8-7)*6
List(5, 6, 7, 8):(N-N-N)*N:(7-8-5)*6
List(5, 6, 7, 8):(N+N-N)*N:(5+7-8)*6
List(5, 6, 7, 8):(N+N-N)*N:(7+5-8)*6

對于5，6，7，8 由于加法和乘法的交互律，某些算法是等價的，我們可以根據(jù)使用的模板是否相同去掉這些等價的算法。

如果只需要計算一種算法，可以為 for 表達式加上條件：

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")
    }
  }

測試如下：

scala> cal24once(List(5,6,7,8))
List(5, 6, 7, 8):(N-(N-N))*N:(5-(8-7))*6

scala> cal24once(List(1,2,3,4))
List(1, 2, 3, 4):N*N*N*N:1*2*3*4

scala> cal24once(List(1,1,1,1))
List(1, 1, 1, 1):no result