アルゴリズム・パズルです。
問題:
すべて大きさのちがう3つのグラス A, B, C があります。その容積は A = B + C, B > C(ただしすべて自然数)で、かつ B と C の値は互いに素とします。
まず、A のグラスに水をいっぱいに入れます。ここから水をどんどん移していきますが、水の移動は一方が空になるか、あるいは一方が満タンになるかのいずれかしか可能でないとします。そして、最終的に A のグラスに残る量がちょうど半分にできるかどうかを考えます。
A の容積が 10 以上 100 以下の偶数のとき、上のようにして A のグラスの水が半分にできるような A, B, C の組み合わせの総数を求めなさい。
Ruby で解いてみました。
q44.rb
def check(quantity) queue = [[quantity[0], 0, 0]] memo = [] while (x = queue.shift) next if memo.include?(x) memo << x move = lambda do |from, to| result = x.dup return false if x[from].zero? return false if x[to] == quantity[to] i = quantity[to] - x[to] if i >= x[from] result[from] = 0 result[to] = x[from] + x[to] else result[to] = quantity[to] result[from] -= i end result end [*0..2].permutation(2) do |from, to| y = move.call(from, to) next unless y return true if y[0] == quantity[0] / 2 queue.push(y) end end false end memo = [] 10.step(100, 2) do |a| (a / 2 + 1).upto(a - 1) do |b| c = a - b next if b.gcd(c) != 1 x = [a, b, c] memo << x if check(x) end end puts memo.size #=>514
答えは 514 とおりです。かかった時間は自分の環境でほぼ 3秒ほどでした。
メソッド check によって与えられたグラスで水を半分にできるかチェックしています。メソッド check 内では幅優先で探索します。水が半分にできれば true を、そうでなければ false を返します。check 内の memo にはすべての状態が格納されていて、同じものが与えられればその手順は捨てます。
クロージャとても便利。
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問
- 作者: 増井敏克
- 出版社/メーカー: 翔泳社
- 発売日: 2015/10/16
- メディア: Kindle版
- この商品を含むブログ (8件) を見る