小町算 in Scala DouKaku?

小町算

古典的なパズルである小町算を解くプログラムを作成してください。

小町算とは：

1□2□3□4□5□6□7□8□9＝100

四角の中に、空白、＋、－、×、÷のいずれかを一つ入れ、等式が成り立つようにするパズルです。

解答例：

1－2－3＋4×56÷7＋8×9＝100

1＋234×5÷6－7－89＝100

参考：　http://ja.wikipedia.org/wiki/%E5%B0%8F%E7%94%BA%E7%AE%97

evalやそれに類するものを使うか否かは自由です。
割り算の際には小数点以下の切捨てが起こらないのが望ましいです。(必須ではない)
- 切捨てが起こる場合の解答例：1÷2÷3＋4＋5÷6＋7＋89＝100
余裕があれば括弧を含むようにしてもいいかもしれません。

手元で20数行ほどのPythonスクリプトを書いてみたところ、101個の解答が得られました。

post comment

Posted feedbacks - Scala

パーサコンビネータでパーサを作ってナイーブに。解答は101個です。

import scala.util.parsing.combinator.{Parsers, ImplicitConversions, ~, mkTilde}
import scala.util.parsing.combinator.syntactical.StdTokenParsers
import scala.util.parsing.combinator.lexical.StdLexical

object Komachi extends StdTokenParsers with Application{
  type Tokens = StdLexical ; val lexical = new StdLexical
  lexical.delimiters ++= List("+","-", "*", "/")
  def expr = term*("+" ^^ {(x: double, y: double) => x + y}
                 | "-" ^^ {(x: double, y: double) => x - y})
  def term = factor*("*" ^^ {(x: double, y: double) => x * y}
                   | "/" ^^ {(x: double, y: double) => x / y})
  def factor: Parser[double] = numericLit ^^ (_.toDouble)

  ((List(List[String]())) /: List.make(8, List("+", "-", "*", "/", ""))){
    for(i <-_; j <-_) yield j::i
  }.foreach{fs =>
    val s = (new StringBuilder("1") /: (2 to 9)){(s,i) =>
      s.append(fs(i-2)).append(i)
    }.toString
    if(expr(new lexical.Scanner(s)).get == 100.0) println(s)
  }
}

DouKaku?

小町算

Posted feedbacks - Scala

Index

Feed

Other

Link

Pathtraq