State-space search: the water jug problem
Many AI problems can be framed as search. A problem is defined by an initial state, the actions available in each state, a transition model that says which state an action leads to, a goal test, and a path cost. Search explores the graph of reachable states to find a sequence of actions from the initial state to a goal.
Python
from collections import deque
def solve(cap_a, cap_b, goal):
start = (0, 0)
parents = {start: None}
queue = deque([start])
while queue:
state = queue.popleft()
a, b = state
if goal in state:
path = []
while state is not None:
path.append(state)
state = parents[state]
return path[::-1]
pour_ab = min(a, cap_b - b)
pour_ba = min(b, cap_a - a)
moves = ((cap_a, b), (a, cap_b), (0, b), (a, 0), (a - pour_ab, b + pour_ab), (a + pour_ba, b - pour_ba))
for following in moves:
if following not in parents:
parents[following] = state
queue.append(following)
return None
path = solve(3, 5, 4)
print(len(path) - 1)
print(path)
print(solve(2, 4, 3))