プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q08:優秀な掃除ロボット。

Q: 同じ場所を通らない前後左右にのみ移動できる掃除ロボットを考える。このロボットが12回移動するときに考えられる経路のパターンは何通りあるか。

val RLUD = Seq((1,0),(-1,0),(0,1),(0,-1))

def move(count:Int, history:(Int, Int)*):Int = {
  if(history.length > count) 1
  else {
    RLUD.foldLeft(0){(sum, to) =>
      val next = (history.head._1 + to._1, history.head._2 + to._2)
      if(history.exists(_ == next)) sum
      else move(count, next+:history:_*) + sum
    }
  }
}
move(12,(0,0))

畳み込みって和な響きするよね。 コンボリューションっていうとトランスフォーマーな響きだなぁ。