1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
#!/usr/bin/env python3
import sys
from collections import deque
def build_jug_graph(cap1, cap2):
from collections import defaultdict
G = defaultdict(list)
for a in range(cap1+1):
for b in range(cap2+1):
ops = [
((cap1, b), 'fill left'),
((a, cap2), 'fill right'),
((0, b), 'empty left'),
((a, 0), 'empty right'),
((max(0, a - (cap2-b)), min(cap2, a+b)), 'transfer left to right'),
((min(cap1, a + b), max(0, b-(cap1-a))), 'transfer right to left'),
]
G[(a,b)] = ops
return G
def measure_one(cap1, cap2):
G = build_jug_graph(cap1, cap2)
start = (0,0)
q = deque([ (start, []) ])
seen = {start}
while q:
(a,b), path = q.popleft()
if a == 1 or b == 1:
return path + [(a,b)]
for (nxt, op) in G[(a,b)]:
if nxt not in seen:
seen.add(nxt)
q.append((nxt, path + [(a, b, op)]))
return None
if __name__ == "__main__":
# parse command line arguments
if len(sys.argv) != 3:
print(f"Usage: python {sys.argv[0]} <jug1-capacity> <jug2-capacity>", file=sys.stderr)
sys.exit(1)
try:
x = int(sys.argv[1])
y = int(sys.argv[2])
except ValueError:
print("Error: capacities must be integers", file=sys.stderr)
sys.exit(1)
# --- run the search ---
solution = measure_one(x, y)
if solution is None:
print("No solution.")
sys.exit(0)
for step in solution:
if len(step) == 2:
a, b = step
print(f"[{a}|{b}], goal reached")
else:
a, b, op = step
print(f"[{a}|{b}], {op}")
|
