プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q21:排他的論理和で作る三角形。

Q: 「パスカルの三角形」を「右上の数と左上の数の和」ではなく「排他的論理和」で配置した時、2014番目の0が出力される段数を求める。

def makeCol(before:Seq[Int])(n:Int) = (before(n-1) + before(n))%2
def count(n:Int, before:Seq[Int], zero:Int=0):Int = {
  if(zero >= 2014) n-1
  else {
    val next = 1+:(1 until n-1).map(makeCol(before)):+1
    count(n+1, next, zero+next.count(_ == 0))
  }
}
count(3,Seq(1,1))