Water Jars (Ice Base) - 水瓶問題

どんな問題？

Water Jars
http://www.checkio.org/mission/water-jars/

2つのビン（水瓶）を持っている。

1. 湖からビンに水を汲む
2. 片方のビンからもう片方に水を注ぐ
3. ビンの水を湖に捨てる

この3種類の操作を繰り返して、指定した量の水を計測するための、最短の手順を求めよ。

引数は、ビン1の容量、ビン2の容量、求める水の量、の3つ。いずれも10未満の整数値。
戻り値は、手順を文字列のリストで返す。1つ1つの手順は文字列で、

• '01'なら、湖からビン1に水を汲む
• '12'なら、ビン1からビン2に注ぐ
• '10'なら、ビン1の水を湖に捨てる

を意味する。

すべてのテストで、必ず解は存在する。

例題：

checkio(5, 7, 6) == ['02', '21', '10', '21', '02', '21', '10', '21', '02', '21']
checkio(3, 4, 1) == ["02", "21"]

どうやって解く？

最短というので、BFSを使ってみる。
ビン1とビン2の水の量をグラフの頂点として考えた。

手順は、01,02,10,20,12,21の6通りなので、それぞれ条件を満たせば次の頂点としてキューに追加する。条件とは、例えば、

• 湖からビン1に水を汲む(01)ことができるのは、ビン1が満杯でないとき
• ビン1の水を湖に捨てる(10)ことができるのは、ビン1が空でないとき

など。

ビン1からビン2に注ぐ(12)の場合は、移動できる水の量は、ビン1の残量と、ビン2の空き容量のいずれか少ない量となる。まず移動できる水の量を求め、それが0でないときだけ、'12'を追加する。

water = min(jar1, second - jar2)  # 移動できる水の量を求める
if water != 0:  # 移動できる水の量が0でなければ
    queue.append((jar1 - water, jar2 + water, action + ['12']))  # キューに追加

まとめ

from collections import deque
 
def checkio(first, second, goal):
    queue = deque([(0, 0, [])])  # (jar1, jar2, action)
    while queue:
        jar1, jar2, action = queue.popleft()
        if jar1 == goal or jar2 == goal:
            return action
        # lake to jar1
        if jar1 != first:
            queue.append((first, jar2, action + ['01']))
        # lake to jar2
        if jar2 != second:
            queue.append((jar1, second, action + ['02']))
        # jar1 to lake
        if jar1 != 0:
            queue.append((0, jar2, action + ['10']))
        # jar2 to lake
        if jar2 != 0:
            queue.append((jar1, 0, action + ['20']))
        # jar1 to jar2
        water = min(jar1, second - jar2)
        if water != 0:
            queue.append((jar1 - water, jar2 + water, action + ['12']))
        # jar2 to jar1
        water = min(jar2, first - jar1)
        if water != 0:
            queue.append((jar1 + water, jar2 - water, action + ['21']))

http://www.checkio.org/mission/water-jars/publications/natsuki/python-3/first/

無事にクリア～。