プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q24:完璧に撃ち抜くストラックアウト。

Q: 9枚の的を打ち抜く順番を考える。周囲にフレームのある5番の的以外は、隣り合う的を2枚抜きできる。この時、9枚の的を打ち抜く順番が何通りあるか求める。

val single = (1 to 9).map(Seq(_))
val double = Seq((1,2),(2,3),(1,4),(3,6),(4,7),(6,9),(7,8),(8,9)).map{i => Seq(i._1,i._2)}
val memo = scala.collection.mutable.Map(Seq.empty[Seq[Int]]-> 1)

def count(remain:Seq[Seq[Int]]):Int = {
  memo.getOrElse(remain, {
    val result = remain.foldLeft(0){(z,t) =>
      z + count(remain.filterNot(_.exists(t.contains)))
    }
    memo + (remain -> result)
    result
  })
}
count(single ++ double)