jug_problem.py

#
# Solves the 'Jug Problem' from RMIT AI Sem 1 2018 Tutorial 1
#
# The state space graph for this problem contains multiple cycles, so we
# can't rely on a naive search fully exploring the graph without getting stuck in a cycle
#
# In order to combat the cycles, I introduce some randomness into operation choices and
# set a maximum search depth that well exceeds the known depth of the most efficient solution

# NOTE: This is rough code. It's hashed out and it's ugly.

from random import random, shuffle

MAX_SEARCH_DEPTH = 100
capacity_map = {
    0: 3,
    1: 5
}
initial_state = (0, 0)


def is_goal_state(state): return state[0] == 1 or state[1] == 1


class Operator():
    def __init__(self, title, action, preconditions=None):
        self.title = title
        self.action = action
        self.preconds = preconditions

    def is_available(self, state, jug_pos):
        for precondition in self.preconds:
            if not precondition(state, jug_pos):
                return False
        return True

    def apply(self, state, jug_pos):
        return self.action(state, jug_pos)

    def __repr__(self):
        return self.title


def transfer_liquid(state, jug_pos):
    left_to_fill = capacity_map[0] - state[0] if jug_pos == 1 else capacity_map[1] - state[1]
    available_to_pour = state[jug_pos]
    able_to_fill = min(left_to_fill, available_to_pour)

    if jug_pos == 0:
        return (state[0] - able_to_fill, state[1] + able_to_fill)
    else:
        return (state[0] + able_to_fill, state[1] - able_to_fill)


operators = [
    Operator(
        title='fill jug X',
        action=lambda state, jug_pos: (capacity_map[jug_pos], state[1]) if jug_pos is 0 else (state[0], capacity_map[jug_pos]),
        preconditions=[
            lambda state, jug_pos: state[jug_pos] < capacity_map[jug_pos]
        ]
    ),
    Operator(
        title='pour jug X into other',
        action=transfer_liquid,
        preconditions=[
            lambda state, jug_pos: state[jug_pos] != 0,
            lambda state, jug_pos: (state[0] < capacity_map[0]) if jug_pos == 1 else (state[1] < capacity_map[1])
        ]
    ),
    Operator(
        title='empty jug X',
        action=lambda state, jug_pos: (0, state[1]) if jug_pos == 0 else (state[0], 0),
        preconditions=[
            lambda state, jug_pos: state[jug_pos] > 0
        ]
    )
]


def solve_problem(state, operation_history):
    if is_goal_state(state):
        return True, operation_history

    if len(operation_history) == MAX_SEARCH_DEPTH:
        return False, operation_history

    jugs = [0, 1] if random() > 0.5 else [1, 0]
    for jug_pos in jugs:
        available_operators = [o for o in operators if o.is_available(state, jug_pos)]
        shuffle(available_operators)
        for operator in available_operators:
                new_state = operator.apply(state, jug_pos)
                # print("Applying '{}' to get from {} to {}".format(operator, state, new_state))
                search_success, history = solve_problem(
                    new_state,
                    operation_history + [(operator, new_state)]
                )
                if search_success:
                    return True, history

    return False, operation_history


if __name__ == '__main__':
    _, history = solve_problem(initial_state, [(None, initial_state)])
    print("Full Search: ")
    print(history)
    print("\nPruned Search: ")
    num_operations = len(history)
    for i in range(num_operations-1, -1, -1):
        operator, state = history[i]
        if state == (0, 0):
            print(history[i:])
            break