Solution To Water Pouring Problem with BFS Search

bfs_solution_water_pouring_problem.py

"""
    BFS Solutiontion to the Water Pouring Problem
    e.g. Given two glasses 1 with capacity 9 ozs and the other with capacity 4 ozs fill the 9 oz glass to capacity 6 ounces
"""

def fill(glasses, glass_idx):
    results = []
    for idx, glass in enumerate(glasses):
        if idx == glass_idx:
            capacity, vol = glass
            results.append((capacity, capacity))
        else:
            results.append(glass)
    return tuple(results)

def empty(glasses, glass_idx):
    results = []
    for idx, glass in enumerate(glasses):
        if idx == glass_idx:
            capacity, vol = glass
            results.append((capacity, 0))
        else:
            results.append(glass)
    return tuple(results)


def trxsfr(glasses, from_idx, to_idx):
    results = []

    capacity_from, vol_from = glasses[from_idx]
    capacity_to, vol_to = glasses[to_idx]
    new_vol_to = min(capacity_to, vol_to + vol_from)
    volume_moved = new_vol_to - vol_to
    new_vol_from = vol_from - volume_moved

    for idx, glass in enumerate(glasses):
        if idx == from_idx:
            capacity, vol = glass
            results.append((capacity, new_vol_from))
        elif idx == to_idx:
            capacity, vol = glass
            results.append((capacity, new_vol_to))
        else:
            results.append(glass)
    return tuple(results)

def reached_goal(glasses):
    return 6 in [vol for cap, vol in glasses]

#quick implementation of bfs
import Queue


if __name__ == "__main__":

    init_glasses = ((9, 0 ), (4, 0))
    no_glasses = len(init_glasses)

    seen_nodes = set([])
    frontier = Queue.deque()
    frontier.append([init_glasses])

    i = 0
    while frontier:
        current_path = frontier.popleft() #switch to .pop() for DFS
        current_state = current_path[-1]
        print i, current_state, frontier, seen_nodes
        if reached_goal(current_state):
            print 'SOLUTION', current_path
            break

        fill_children = [fill(current_state, n) for n in range(no_glasses)]
        empty_children = [empty(current_state, n) for n in range(no_glasses)]
        trxsfr_children = [trxsfr(current_state, from_idx, to_idx)
                                for from_idx in range(no_glasses)
                                for to_idx in range(no_glasses)
                                if from_idx != to_idx]

        children = fill_children + empty_children + trxsfr_children
        seen_nodes.add(current_state)

        for child in children:
            if child not in seen_nodes:
                new_path = current_path[:]
                new_path.append(child)
                frontier.append(new_path)
        
        i += 1