fork download
copy 
  1. from collections import deque
  2. from itertools import count
  3.  
  4.  
  5. def new_states(state, jug1, jug2):
  6.     j1, j2 = state
  7.     states = [(jug1, j2), (j1, jug2), (j1, 0), (0, j2)]
  8.     fill = min(jug1 - j1, j2)
  9.     states.append((j1 + fill, j2 - fill))  # fill 1 from 2
  10.     fill = min(jug2 - j2, j1)
  11.     states.append((j1 - fill, j2 + fill))  # fill 2 from 1
  12.     return [s for s in states if s != state]
  13.  
  14.  
  15. def solve(jug1, jug2, target):
  16.     Q = deque([(0, 0)])  # BFS
  17.     parent = {}
  18.     while Q:
  19.         state = Q.popleft()
  20.         states = new_states(state, jug1, jug2)
  21.         for s in states:
  22.             if s in parent:
  23.                 continue
  24.             parent[s] = state
  25.             if target in s or target == sum(s):
  26.                 return s, parent
  27.             Q.append(s)
  28.  
  29.  
  30. def path(state, parents):
  31.     path = [state]
  32.     while True:
  33.         state = parents[state]
  34.         path.append(state)
  35.         if state == (0, 0):
  36.             break
  37.     return path[::-1]
  38.  
  39.  
  40. def description(statea, stateb):
  41.     sa1, sa2 = statea
  42.     sb1, sb2 = stateb
  43.     if sa1 == sb1:
  44.         return "fill 2 from tap" if sb2 else "empty 2"
  45.     elif sa2 == sb2:
  46.         return "fill 1 from tap" if sb1 else "empty 1"
  47.     else:
  48.         return "fill 1 from 2" if sa1 < sb1 else "fill 2 from 1"
  49.  
  50.  
  51. jug1, jug2 = 13, 23
  52. target = 4
  53. solution = solve(jug1, jug2, target)
  54. print("jug1: {}  jug2: {}     target: {}".format(jug1, jug2, target))
  55. if solution:
  56.     s, parent = solution
  57.     pat = path(s, parent)
  58.     for step, s1, s2 in zip(count(1), pat, pat[1:]):
  59.         print(step, s2, description(s1, s2))
  60. else:
  61.     print("No solution")
  62.  
Success #stdin #stdout 0.01s 10248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
jug1: 13  jug2: 23     target: 4
1 (0, 23) fill 2 from tap
2 (13, 10) fill 1 from 2
3 (0, 10) empty 1
4 (10, 0) fill 1 from 2
5 (10, 23) fill 2 from tap
6 (13, 20) fill 1 from 2
7 (0, 20) empty 1
8 (13, 7) fill 1 from 2
9 (0, 7) empty 1
10 (7, 0) fill 1 from 2
11 (7, 23) fill 2 from tap
12 (13, 17) fill 1 from 2
13 (0, 17) empty 1
14 (13, 4) fill 1 from 2
https://ideone.com/NQ3DKw
BFS solution for Water Jugs Puzzle
language:
Python 3 (python  3.9.5)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!