公平に分けられたケーキ（アルゴリズム・パズル）

書籍「プログラマ脳を鍛える数学パズル」からの問題を解いてみます。

問題

16cm × 12cm の長方形のケーキがあります。二人で交互にケーキを切るのですが、ケーキを切った人が小さい方のケーキを取り（同じ大きさならどちらでもよい）、交代して残りをさらに切るというようにします。（ただし切り方は、辺に平行に直線的に切り、しかも切ってできたケーキの辺の長さは cm 単位になるようにします。）これを最小が 1cm × 1cm になるまで続けます。
さて、切り終えたとき二人の取ったケーキのそれぞれの総量が等しくなるとします。このような切り方は何とおりもありますが、その中で切った「切り口」の長さの総和を出すとき、その最小値を求めなさい。

コード例

Rubyで解いてみました。

q56.rb

#(x, y)のケーキを切ってできる全ての (面積, 切った長さの合計) のペアを返す
#ただし面積はここでカットした人の総計
def cut(x, y)
  x, y = y, x if x < y
  return @memo[[x, y]] if @memo.has_key?([x, y])
  return {1 => 1} if x == 2 and y == 1

  result = {}

  #前の人がカットしたところから自分の分を求める
  #「if result[square] > length」は効果の大きい枝刈り（切り口の長さの総和が最小になるものだけ残す）
  calc = proc do |s, t|
    cut(s, t).each do |sqar, ln|
      square = x * y - sqar
      length = ln + s
      result[square] = length if !result[square] or result[square] > length
    end
  end

  #可能なあらゆる場合でケーキを切る
  (x / 2).times {|i| calc.(y, x - i - 1)}
  (y / 2).times {|i| calc.(x, y - i - 1)}

  @memo[[x, y]] = result
end

X, Y = 16, 12
@memo = {}

result = cut(X, Y)
p result.select {|sqar, _| sqar == X * Y / 2}    #=>{96=>47}

計算した結果は「メモ化」して高速化しています。

結果

答えは47cmです。かかった時間は自分の環境（Core i5-4210U 1.70GHz×2）で0.1秒ほどです。ちなみにX, Y = 30, 30の場合で0.4秒ほどになります。いろいろな言語で解いてみるとおもしろいかもしれませんね。

なお、以上はブログ記事が元になっています。