四則演算で10を作るプログラムをScalaで書いてみました。

algorithm scala

前にTwitter友達であり、実は同期の @sandnyx さんから急に以下のような問題が出されました。

https://twitter.com/sandnyx/status/173412065329942529:twitter:detail:left

少し悩んで以下のように回答しました。

https://twitter.com/yosuke_furukawa/status/173607748326539265:twitter:detail:left

そしたら、さらに難しい問題が・・・。

https://twitter.com/sandnyx/status/173664480864112641:twitter:detail:left

こんなやり取りしてたんですが、この四則演算で10を作るクイズ、昔電車の切符使ってやってましたよね。
行き交う道路の車のナンバーとかでもやった気がします。
懐かしくなったので、Scalaの勉強も兼ねて作ってみました、四則演算で10を作るプログラム。

コレを使えば、10を出せる全部の回答をもらえます。例えば最初の 2, 4, 7, 7の例だとコレくらい回答があります。

  1. (2-(4/7))*7 = 10
  2. 2*(4+(7/7)) = 10
  3. 2*((7/7)+4) = 10
  4. (4+(7/7))*2 = 10
  5. 7*(2-(4/7)) = 10
  6. ((7/7)+4)*2 = 10

こうやって見ると、自分の (2-4/7)*7よりも簡単な回答があるんですよね。
(7/7+4)*2 なんか一番簡単ですよね。

次に出された1, 1, 5, 8は 8/(1-(1/5)) しか回答がありません。難易度の高い問題だったことがわかります。

この問題、実は10puzzleといってアルゴリズムとかプログラムを学ぶ人が最初に取っ掛かりとして作ることがあります。
それでは、ソースコード紹介行ってみます。

■Make10.scala

import scala.collection.mutable.Set
import scala.collection.mutable.HashSet
import scala.collection.mutable.ListBuffer

/**
 * 四則演算(+, -, *, /)を使って10を作るプログラム
 */
object Make10 {
  /**
   * メモ化用集合
   */
  private val answerSet = new HashSet[String]()
  
  private val ANSWER_NUM = 10

  /**
   * メモ化
   */
  def memorize(answer: String) {
    answerSet.add(answer);
  }

  /**
   * 四則演算で10を作るメソッドです。
   */
  def make10(nums: List[Int]) {
    val opList = Array("+", "-", "*", "/");
    val numList = new NumberList(nums).list
    val range = 0 to 3
    val ansList = new ListBuffer[Tuple2[Rational, String]]();
    for (nums <- numList) {
      for (op1 <- opList) {
        for (op2 <- opList) {
          for (op3 <- opList) {
            pattern1(nums._1, nums._2, nums._3, nums._4, op1, op2, op3).foreach { value => ansList += value}
            pattern2(nums._1, nums._2, nums._3, nums._4, op1, op2, op3).foreach { value => ansList += value}
            pattern3(nums._1, nums._2, nums._3, nums._4, op1, op2, op3).foreach { value => ansList += value}
            pattern4(nums._1, nums._2, nums._3, nums._4, op1, op2, op3).foreach { value => ansList += value}
            pattern5(nums._1, nums._2, nums._3, nums._4, op1, op2, op3).foreach { value => ansList += value}
          }
        }
      }
    }
    val filteredList = ansList.filter(_._1 == ANSWER_NUM)
    filteredList.foreach(ans => println(ans._2 + " = " + ans._1))
  }

  /**
   * ((a op1 b) op2 c) op3 d の計算。
   */
  def pattern1(
    first: Rational,
    second: Rational,
    third: Rational,
    fourth: Rational,
    op1: String,
    op2: String,
    op3: String): Option[(Rational, String)] = {
    val exp = "((" + first + op1 + second + ")" + op2 + third + ")" + op3 + fourth
    var result: Option[(Rational, String)] = None;
    if (!answerSet.contains(exp)) {
      memorize(exp)
      calculate(op1, first, second).foreach {
        ans1 =>
          calculate(op2, ans1, third).foreach {
            ans2 =>
              calculate(op3, ans2, fourth).foreach {
                ans3 => result = Some(ans3, exp)
              }
          }
      }
    }
    result
  }
  
  /**
   * (a op1 b) op2 (c op3 d) の計算。
   */
  def pattern2(
    first: Rational,
    second: Rational,
    third: Rational,
    fourth: Rational,
    op1: String,
    op2: String,
    op3: String): Option[(Rational, String)] = {
    val exp = "(" + first + op1 + second + ")" + op2 + "(" + third + op3 + fourth + ")"
    var result: Option[(Rational, String)] = None;
    if (!answerSet.contains(exp)) {
      memorize(exp)
      calculate(op1, first, second).foreach {
        ans1 =>
          calculate(op3, third, fourth).foreach {
            ans2 =>
              calculate(op2, ans1, ans2).foreach {
                ans3 => result = Some(ans3, exp)
              }
          }
      }
    }
    result
  }

  /**
   * (a op1 (b op2 c)) op3 d の計算。
   */
  def pattern3(
    first: Rational,
    second: Rational,
    third: Rational,
    fourth: Rational,
    op1: String,
    op2: String,
    op3: String): Option[(Rational, String)] = {
    val exp = "(" + first + op1 + "(" + second + op2 + third + "))" + op3 + fourth
    var result: Option[(Rational, String)] = None;
    if (!answerSet.contains(exp)) {
      memorize(exp)
      calculate(op2, second, third).foreach {
        ans1 =>
          calculate(op1, first, ans1).foreach {
            ans2 =>
              calculate(op3, ans2, fourth).foreach {
                ans3 => result = Some(ans3, exp)
              }
          }
      }
    }
    result
  }
  
  /**
   * a op1 ((b op2 c) op3 d) の計算。
   */
  def pattern4(
    first: Rational,
    second: Rational,
    third: Rational,
    fourth: Rational,
    op1: String,
    op2: String,
    op3: String): Option[(Rational, String)] = {
    val exp = first + op1 + "((" + second + op2 + third + ")" + op3 + fourth + ")"
    var result: Option[(Rational, String)] = None;
    if (!answerSet.contains(exp)) {
      memorize(exp)
      calculate(op2, second, third).foreach {
        ans1 =>
          calculate(op3, ans1, fourth).foreach {
            ans2 =>
              calculate(op1, first, ans2).foreach {
                ans3 => result = Some(ans3, exp)
              }
          }
      }
    }
    result
  }
  
  /**
   * a op1 (b op2 (c op3 d)) の計算。
   */
  def pattern5(
    first: Rational,
    second: Rational,
    third: Rational,
    fourth: Rational,
    op1: String,
    op2: String,
    op3: String): Option[(Rational, String)] = {
    val exp = first + op1 + "(" + second + op2 + "(" + third + op3 + fourth + "))"
    var result: Option[(Rational, String)] = None;
    if (!answerSet.contains(exp)) {
      memorize(exp)
      calculate(op3, third, fourth).foreach {
        ans1 =>
          calculate(op2, second, ans1).foreach {
            ans2 =>
              calculate(op1, first, ans2).foreach {
                ans3 => result = Some(ans3, exp)
              }
          }
      }
    }
    result
  }
  
  /**
   * 演算子と2つの数を受け取って値を返すメソッド。
   * 0除算や定義されていない演算子を使った場合、Noneが返る。
   */
  private def calculate(op: String, num1: Rational, num2: Rational): Option[Rational] = {
    try {
      val ans: Option[Rational] = op match {
        case "+" => Some(num1 + num2)
        case "-" => Some(num1 - num2)
        case "*" => Some(num1 * num2)
        case "/" => Some(num1 / num2)
        case _ => None
      }
      ans
    } catch {
      case _ => None
    }
  }
}

流れとしては以下の通り。

  • 全ての数字の組み合わせを最初に作ります。(1,2,3,4) => (2,3,4,1) => (3,4,1,2) ...
  • 全ての演算子と数字の組み合わせを以下のパターンに対して適用します。

*1 op3 d
a op1 *2

  • 最終的に出た全ての解答の中から解答が10のもののみフィルタして返します。

あと工夫したポイントは以下の通り：

  • 通常のDouble型だと割り算の時に丸め誤差が出るかもしれなかったので、Rational型という有理数を表すクラスを作成し、なるべく割り算は分数の形で保存するようにしています。
  • せっかくなので、プログラミングコンテスト チャレンジブックでやっていたメモ化を使ってみました。それで一度計算した結果は演算しないようにしています。
  • Effective Scalaにも書いてあったOption型とパターンマッチングを多用して、なるべくScalaっぽく書いてみようとしてみました。

せっかく書いたのですが、プログラム的にパターンのところが冗長だなぁという気がします。
こんな解き方もあります。やっぱり文字列化して、それをevalして結果を得る方法がアルゴリズム的にもプログラム的にもスマートな気がしますね。
10puzzleを解くプログラム(python) - Rainbow U - livedoor Wiki（ウィキ）
せっかくPlay! 2.0がリリースされたことなので、このプログラムをwebアプリにでもしてみようかなと思います。

残りのコードも晒しておきます。githubにも上げてみました。
yosuke-furukawa/Make10 · GitHub

最後に @sandnyx さんに問題 9, 9, 9, 9と8,8,8,8も割りと難しかったよ。

■Rational.scala

class Rational(n: Int, d: Int) {
  require(d != 0)
  private val g = gcd(n.abs, d.abs)
  val numer: Int = n/g
  val denom: Int = d/g
  def this(n: Int) = this(n, 1)
  def + (that: Rational): Rational =
    new Rational(
      numer * that.denom + that.numer * denom,
      denom * that.denom
   )
  def + (i: Int): Rational =
    new Rational(numer + i * denom, denom)
  def * (that: Rational): Rational =
    new Rational(
     numer * that.numer, denom * that.denom)
  def * (i: Int): Rational = new Rational(numer *i, denom)
  def - (that: Rational): Rational =
    new Rational(
      numer * that.denom - that.numer * denom,
      denom * that.denom
   )
  def - (i: Int): Rational =
    new Rational(numer - i * denom, denom)
  def / (that: Rational): Rational =
    new Rational(
     numer * that.denom, denom * that.numer)
  def / (i: Int): Rational = new Rational(numer, denom * i)
  
  def == (i: Int): Boolean = 
    this.numer == new Rational(i).numer && this.denom == new Rational(i).denom;
  
  override def toString = 
    if (denom == 1) ""+numer
    else numer + "/" + denom
  def lessThan(that: Rational) =
    this.numer * that.denom < that.numer * this.denom
  def max(that: Rational) =
    if (this.lessThan(that)) that else this
  private def gcd(a: Int, b: Int): Int =
    if (b==0) a else gcd(b, a%b)
}

■NumberList.scala

import scala.collection.mutable.ListBuffer

/**
 * 4つの数を受け取り、全ての組み合わせの数を返すクラス
 */
class NumberList(list: List[Int]) {
  private val numList = new ListBuffer[Tuple4[Rational, Rational, Rational, Rational]]()
  private val nums: List[Int] = list.toList
  private val range = 0 to nums.length - 1
  for (firstIndex <- range) {
    val first = new Rational(nums(firstIndex))
    for (
      secondIndex <- range if firstIndex != secondIndex
    ) {
      val second = new Rational(nums(secondIndex))
      for (
        thirdIndex <- range if firstIndex != thirdIndex && secondIndex != thirdIndex
      ) {
        val third = new Rational(nums(thirdIndex))
        for (
          fourthIndex <- range if firstIndex != fourthIndex &&
            secondIndex != fourthIndex &&
            thirdIndex != fourthIndex
        ) {
          val fourth = new Rational(nums(fourthIndex))
          val numbers = (first, second, third, fourth)
          if (!numList.contains(numbers))
            numList += numbers
        }
      }
    }
  }
  
  def list(): List[Tuple4[Rational, Rational, Rational, Rational]] = numList.toList
}

*1:a op1 b) op2 c) op3 d (a op1 b) op2 (c op3 d) (a op1 (b op2 c

*2:b op2 c) op3 d) a op1 (b op2 (c op3 d