Scala で解く「プログラマ脳を鍛える数学パズル」

病院行ったついでに待ち時間暇すぎて書店で見かけたやつ。

www.amazon.co.jp

これの問２ 1000 - 9999 の中で、「351 , 3 * 51 = 153」（計算結果が元の逆順になる）みたいな数字を見つけ出せ。
使っていいのは四則演算のみで、必ず１回は計算すること。

これ、JavaScript/Ruby/Python だと瞬殺できる。
こいつらには eval があるので、四則演算「+-*/(何もなし)」を適当に埋め込んで eval すればいい。

しかしコンパイル言語でそんなファジーな事は残念ながらできない。
なので、真面目に考えた。

基本的に +-/ を入れた時点で、４桁の結果を出すことが不可能である（厳密には可能だが、組み合わせが存在しない）事を考えると、どこに掛け算の演算子を入れるかの世界になってくる。

演算子を入れれるパターンは、４桁という点で下記 7 パターンしか存在しない。

X XXX (1, 3)
XX XX (2, 2)
XXX X (3, 1)
X X XX (1, 1, 2)
X XX X (1, 2, 1)
XX X X (2, 1, 1)
X X X X (1, 1, 1, 1)

の７通りのみ。

っつー事で、substring で分解して、掛け算走らせればOK

object Main extends App {
  val splitPatterns = Seq(
    Seq(1, 3), Seq(2, 2), Seq(3, 1), 
    Seq(1, 1, 2), Seq(1, 2, 1), Seq(2, 1, 1), 
    Seq(1, 1, 1, 1)
  )

  def split(s: String, p: Seq[Int]): Seq[String] =
    s.substring(0, p.head) +: (if (p.tail.isEmpty) Seq.empty else split(s.substring(p.head), p.tail))

  (1000 to 9999).foreach(v => {
    splitPatterns.foreach(p => {
      val origin = v.toString
      val seq = split(origin, p).map(_.toInt)
      if(seq.product == origin.reverse.toInt) {
        println(s"Found Answer: $v ($seq)")
      }
    })
  })
}

結果

[info] Running Main 
Found Answer: 5931 (List(5, 9, 31))
[success] Total time: 4 s, completed 2016/01/17 19:10:21

最初に掛け算以外考えなくて済むというところに気づくと、上記みたいな解になるが、後から四足演算を計算しようと考えた時に、下記みたいな配列作って、計算で再起すべきかとか考えてしまった…。
何かスッキリ実装できる方法がないのかと思わなくはない。

  val operatorFunc: Seq[Function2[Int, Int, Int]] = Seq(
    (a, b) => a * b, (a, b) => a - b, (a, b) => a / b
  )

split を tail call にするのもまだ慣れていないせいかなかなか上手く行ってない…。
別に深くなるわけでもないので、気にしなかったのだが。

というか、他の言語は「逆ポーランド記法使う」ってそれむしろどうやるのかわからなかった…。