プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q18:ショートケーキの日。

Q: ホールケーキを切り分けるとき、ケーキに乗っているイチゴの数がすべて異なるような切り方を考える(N個に切り分けるとき、1~N個のイチゴがそれぞれ乗っている)。ただし、隣り合う２つのケーキに乗っているイチゴの数の和がいずれも平方数にならなければならない。これらの条件を満たす最小のNを求める。

def num(n:Int):Stream[Int] = n #:: num(n+1)
def check(n:Int, sqr:Seq[Int], before:Int = 1, acc:Set[Int] = Set(1)):Boolean = {
  if(acc.size == n) sqr.contains(1+before)
  else {
    (1 to n).diff(acc.toSeq).find{ next =>
      sqr.contains(before+next) && check(n, sqr, next, acc + before)
    }.isDefined
  }
}
num(2).find{n => check(n, (2 to scala.math.sqrt(2*n).toInt).map(a => a*a))}.get