The Jug Algorithm for Discrete Math - MATH 3310, USU

Jugs.py

# Credit for gcd() method - https://stackoverflow.com/questions/11175131/code-for-greatest-common-divisor-in-python
def gcd(a, b):
    """Calculate the Greatest Common Divisor of a and b.

    Unless b==0, the result will have the same sign as b (so that when
    b is divided by it, the result comes out positive).
    """
    while b:
        a, b = b, a % b
    return a


class Jug(object):

    @property
    def size(self):
        return self.__size

    @property
    def filled_amount(self):
        return self.__filled_amount

    @filled_amount.setter
    def filled_amount(self, amount):
        self.__filled_amount = amount

        if self.__filled_amount < 0:
            raise Exception("jug cannot have a negative amount of water")

        if self.__filled_amount > self.__size:
            raise Exception("jug cannot hold more than %d units of water" % self.__filled_amount)

    def __init__(self, size, name):  # type: (int, str) -> None
        self.__size = size  # type: int
        self.__filled_amount = 0  # type: int
        self.states = []  # type: [int]
        self.actions = []  # type: [str]
        self.name = name

    @staticmethod
    def concat_states(a, b, delimeter=" -> "):  # type: (Jug, Jug, str) -> str
        states = map(lambda x: "(%d, %d)" % (x[0], x[1]), zip(a.states, b.states))
        return delimeter.join(states)

    @staticmethod
    def to_tabular_latex(a, b, columns=4):  # type: (Jug, Jug, int) -> [str]
        states = map(lambda x: "(%d, %d)" % (x[0], x[1]), zip(a.states, b.states))
        states = list(states)  # type: list
        actions = map(lambda x: ", ".join([x[0], x[1]]), zip(a.actions, b.actions))
        actions = list(actions)  # type: list

        pairs = list(zip(states, actions))

        def reduce_(arr, n):
            for i in range(0, len(arr), n):
                yield arr[i:i + n]

        # chunks = int((len(states) + len(actions) / 2) / columns)
        rows = [p for p in reduce_(pairs, columns)]

        tabular_rows = []
        for i in range(0, len(rows)):
            row = rows[i]
            tabular_rows.append([])
            # row[n] = ("(a, b)", "<action>, ")
            for pair in row:
                state = "$%s$" % pair[0]
                action = pair[1].split(',')
                action = list(filter(lambda x: len(x.strip()) > 0, action))
                action = action[0].strip()
                tabular_rows[i].append(action + " & " + state)
            tabular_rows[i] = " & ".join(tabular_rows[i]) + "\\\\"

        # tabular_rows = " \\\\".join(tabular_rows)
        return tabular_rows

    def pour(self, jug):  # type: (Jug, Jug) -> Jug
        while self.filled_amount > 0 and jug.filled_amount < jug.size:
            self.filled_amount -= 1
            jug.filled_amount += 1

        self.update_state("Pour %s into %s" % (self.name, jug.name))
        jug.update_state()

        return jug

    def update_state(self, action=''):
        self.states.append(self.filled_amount)
        self.actions.append(action)

    def empty(self):
        self.filled_amount = 0
        self.update_state("Empty %s" % self.name)

    def fill(self):
        self.filled_amount = self.size
        self.update_state("Fill %s" % self.name)

    def is_full(self):
        return self.filled_amount == self.size

    def is_empty(self):
        return self.filled_amount == 0

    def do_nothing(self):
        self.update_state()


def jugs(jug_size_a, jug_size_b, target):  # type: (int, int, int) -> None
    # Jugs Algorithm: Algorithm for precisely measuring water with A and B.
    # One: Fill A.
    # Two: Pour the contents of A into B and if B ever becomes full, empty it and continue pouring A into B.

    if gcd(jug_size_a, jug_size_b) != 1:
        print("WARNING: Jug sizes have a common divisor greater than 1. This can have the result in never achieving a state where you reach your target.")

    a = Jug(jug_size_a, 'A')
    b = Jug(jug_size_b, 'B')

    a.update_state("-")
    b.update_state()

    count = 0

    while a.filled_amount != target or b.filled_amount != target:
        if a.is_empty():
            a.fill()
            b.do_nothing()
        elif b.is_full():
            b.empty()
            a.do_nothing()
        else:
            a.pour(b)

        if a.filled_amount == target or b.filled_amount == target:
            break

        count += 1

        if count % 100 == 0:
            print("WARNING: Fill-Empty-Pour steps exceeding %d steps" % count)

            print_states = input("Print States [Y/n]? ")
            if print_states.lower().strip() == 'y' or print_states.strip() == '':
                print(Jug.concat_states(a, b))

            continue_ = input("Continue [Y/n]?")
            if not (continue_.lower().strip() == 'y' or continue_.strip() == ''):
                break

    print(Jug.concat_states(a, b))
    # print(Jug.concat_states(a, b, " \\rightarrow "))
    # tabular_latex_rows = Jug.to_tabular_latex(a, b, 4)
    # for row in tabular_latex_rows:
    #     print(row)


if __name__ == "__main__":
    import sys
    args = sys.argv[1:]

    if len(args) != 3:
        print("Error: expected three arguments")
    else:
        args = [int(arg) for arg in args]
        jugs(*args)