2つのバケツ問題(Ruby)

反復深化/アルゴリズム講座
おもしろそうな問題を見つけました。

8リットルと5リットルのふたつのバケツを使って1リットルの水を最短手順で川からくみあげて下さい。

http://www.ic-net.or.jp/home/takaken/pz/index3.html

 
Ruby で解いてみました。それぞれのバケツには、空にするかいっぱいに水を入れるか、もう一方に移し替えるかの 3通りの場合があります。すべての手順に 0~5 の番号を振ります。

8リットル: 空(0), 入れる(1), 8→5に移す(2)
5リットル: 空(3), 入れる(4), 5→8に移す(5)

 
最短手順なので、幅優先探索を使います。
bucket_problem.rb

def move(mass, f, t)
  if (a = mass - t) >= f
    t += f
    f = 0
  else
    t = mass
    f -= a
  end
  [f, t]
end


procedures = [[[1], 0, 0], [[4], 0, 0]]
loop do
  pr = procedures.shift
  
  case pr[0][-1]
  when 1 then pr[1] = 8
  when 4 then pr[2] = 5
  when 0 then pr[1] = 0
  when 3 then pr[2] = 0
  when 2
    pr[1], pr[2] = move(5, pr[1], pr[2])
  when 5
    pr[2], pr[1] = move(8, pr[2], pr[1])
  end
  
  if pr[1] == 1 or pr[2] == 1
    p pr[0]
    exit
  end
  
  6.times do |i|
    a = pr[0].dup
    next if a[-1] == i    #高速化用
    a << i
    procedures.push([a, pr[1], pr[2]])
  end
end

実行してみます。

$ time ruby bucket_problem.rb
[1, 2, 3, 2, 1, 2, 3, 2]

real	0m0.384s
user	0m0.364s
sys	0m0.016s

 
上の手順は翻訳するとこうなります。

手順 8L 5L
8Lに入れる 8 0
8→5 3 5
5Lを空 3 0
8→5 0 3
8Lに入れる 8 3
8→5 6 5
5Lを空 6 0
8→5 1 5

これで確かに 8L のバケツに 1L 残りました!
 
ちなみに、意味ある最長手順は [4, 5, 4, 5, 0, 5, 4, 5, 4, 5, 0, 5, 4, 5] です。また、8リットルと5リットルのバケツで4リットルを作るのにも挑戦してみて下さい。


汎用性のあるバージョンに書き換えてみました。コードはこちらです。バケツの大きさと計る値を指定することができます。可能なすべての場合を出力し、無意味な解はできるだけ除きますが、一部冗長な解も出力してしまいますので注意して下さい。