グラスの水を半分に（Ruby）

アルゴリズム・パズルです。

問題：
すべて大きさのちがう３つのグラス 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 にはすべての状態が格納されていて、同じものが与えられればその手順は捨てます。

クロージャとても便利。
　