2つのバケツを使って水の量を測るっていう
古典的なパズル問題ありますよね
今回はそれをプログラムで解いてみました。
解説動画はこちら
5リットル入るバケツと3リットル入るバケツがある
ヒント : 水は捨てたり移動したりして良い
バケツをA, B、測りたい水量をXとし
A,Bの水量を記録していきます
途中、以下の6つの状態でうまく切り替えて手順を記録し
どこかが水量Xになったら終了になります。
プログラム上ではキューというデータ構造のものを使って
手順を記録していく形になります。
手順を解くコード
手順を算出するコードは次のようになります。
早速実行して見てみましょう。
バケツA,Bの値と
ターゲットの水量Xを指定すると
その手順が表示されます。
古典的なパズル問題ありますよね
今回はそれをプログラムで解いてみました。
解説動画はこちら
二つのバケツで指定の水量を測るやつ
問題
5リットル入るバケツと3リットル入るバケツがある
この2つだけを使って4リットルの水を測りたい
どうすれば良いでしょうか
ヒント : 水は捨てたり移動したりして良い
プログラムでの解法
幅優先探索(breadth-first search, BFS)を
用いて手順の探索を行っていきます。
用いて手順の探索を行っていきます。
バケツをA, B、測りたい水量をXとし
A,Bの水量を記録していきます
途中、以下の6つの状態でうまく切り替えて手順を記録し
どこかが水量Xになったら終了になります。
1. Aを満たす
2. Bを満たす
3. Aを空にする
4. Bを空にする
5. AからBに移す
6. BからAに移す
プログラム上ではキューというデータ構造のものを使って
手順を記録していく形になります。
手順を解くコード
手順を算出するコードは次のようになります。
from collections import deque from math import gcd # 幅優先探索(breadth-first search, BFS)を用いて手順の探索を行う def min_steps_to_measure(A, B, X): # 目標の水量がAとBの最大公約数で割り切れない場合は終了 if X > max(A, B) or X % gcd(A, B) != 0: return [] # キューとSETと状態の親を初期化 queue, visited, parent = deque(), set(), {} # 初期状態をキューに追加 queue.append((0, 0)) # (容器Aの水量, 容器Bの水量) parent[(0, 0)] = None # 初期状態の親はNone while queue: a, b = queue.popleft() # 目標の水量に達した場合 if a == X or b == X: # 結果を表示 steps = [] while (a, b) is not None: steps.append((a, b)) # 親が存在する場合のみアンパック if parent[(a, b)] is not None: a, b = parent[(a, b)] else: break steps.reverse() return steps # 訪れた状態を記録 if (a, b) in visited: continue visited.add((a, b)) # 次の状態をキューに追加 # 1. 容器Aを満たす if (A, b) not in visited: queue.append((A, b)) parent[(A, b)] = (a, b) # 2. 容器Bを満たす if (a, B) not in visited: queue.append((a, B)) parent[(a, B)] = (a, b) # 3. 容器Aを空にする if (0, b) not in visited: queue.append((0, b)) parent[(0, b)] = (a, b) # 4. 容器Bを空にする if (a, 0) not in visited: queue.append((a, 0)) parent[(a, 0)] = (a, b) # 5. 容器Aから容器Bに移す transfer_to_B = min(a, B - b) if (a - transfer_to_B, b + transfer_to_B) not in visited: queue.append((a - transfer_to_B, b + transfer_to_B)) parent[(a - transfer_to_B, b + transfer_to_B)] = (a, b) # 6. 容器Bから容器Aに移す transfer_to_A = min(b, A - a) if (a + transfer_to_A, b - transfer_to_A) not in visited: queue.append((a + transfer_to_A, b - transfer_to_A)) parent[(a + transfer_to_A, b - transfer_to_A)] = (a, b) return [] # 目標の水量を測ることができない場合
早速実行して見てみましょう。
バケツA,Bの値と
ターゲットの水量Xを指定すると
その手順が表示されます。
# 容器の容量と目標の水量を指定 A = 5 # 容器Aの容量 B = 3 # 容器Bの容量 X = 4 # 測りたい水量 # 最小手数を計算 steps = min_steps_to_measure(A, B, X) # 結果を表示 if steps: print("途中の過程:") for step in steps: print(f"容器A: {step[0]}L, 容器B: {step[1]}L") else: print("目標の水量を測ることができませんでした。")
途中の過程:
容器A: 0L, 容器B: 0L
容器A: 5L, 容器B: 0L
容器A: 2L, 容器B: 3L
容器A: 2L, 容器B: 0L
容器A: 0L, 容器B: 2L
容器A: 5L, 容器B: 2L
容器A: 4L, 容器B: 3L
このように探索の結果が表示されます。
文字だけだと分かりづらいので
描画してみることにしましょう。
手順を描画するコード
ipywidgetsでスライダーを作り
stepを可変で描画できます。
A,B,Xを色々な設定に変えて
色々遊んでみてください。

今回は2つのバケツを使って水量を測るやつを
プログラムにしてみました。
動画ではもう少し手順のかかるやつもやっているので
興味がある場合は見てみてください。
今回はここまでです
それでは
このように探索の結果が表示されます。
文字だけだと分かりづらいので
描画してみることにしましょう。
手順を描画するコード
ipywidgetsでスライダーを作り
stepを可変で描画できます。
A,B,Xを色々な設定に変えて
色々遊んでみてください。
import matplotlib.pyplot as plt import matplotlib.patches as patches import numpy as np import ipywidgets as widgets from IPython.display import display %matplotlib inline A = 5 # 容器Aの容量 B = 3 # 容器Bの容量 X = 4 # 測りたい水量 steps = min_steps_to_measure(A, B, X) # 描画関数 def draw_graph(step): a_value = steps[step][0] b_value = steps[step][1] a_frame_height = A - a_value b_frame_height = B - b_value # 描画 fig, ax = plt.subplots(figsize=(8, 4)) ax.bar(0, a_value, width=0.4, label='Container A Volume (L)', color='blue', linewidth=2, edgecolor='black') rect_a = patches.Rectangle((-0.2, a_value), 0.4, a_frame_height, linewidth=2, edgecolor='black', facecolor='none') ax.add_patch(rect_a) ax.text(0, max(A,B)+1, str(a_value), ha='center', va='bottom', fontsize=12, color='green') ax.bar(1, b_value, width=0.4, label='Container B Volume (L)', color='red', linewidth=2, edgecolor='black') rect_b = patches.Rectangle((0.8, b_value), 0.4, b_frame_height, linewidth=2, edgecolor='black', facecolor='none') ax.add_patch(rect_b) ax.text(1, max(A,B)+1, str(b_value), ha='center', va='bottom', fontsize=12, color='green') # タイトルとラベルの設定 ax.set_title(f'Container A : {A} and B: {B} Target Volume : {X} with Frames step : {step}') ax.set_xlabel('Containers') ax.set_ylabel('Volume (L)') ax.set_xticks([0, 1]) ax.set_xticklabels(['Container A', 'Container B']) ax.set_ylim(0, max(A,B)+3) plt.show() # スライダーの作成 step_slider = widgets.IntSlider(value=0, min=0, max=len(steps)-1, step=1, description='Step:') interactive_plot = widgets.interactive(draw_graph, step=step_slider) display(interactive_plot)

今回は2つのバケツを使って水量を測るやつを
プログラムにしてみました。
動画ではもう少し手順のかかるやつもやっているので
興味がある場合は見てみてください。
今回はここまでです
それでは
コメントする