# -*- coding: utf-8 -*-
# ENGG 2440A / ESTR 2004 Lecture 4 -- python code

# Extended Euclid's algorithm
def xgcd(n, d):
    if d == 0:
        return (1, 0)
    else:
        (s, t) = xgcd(d, n % d)
        return (t, s - t * (n / d))
        
# Euclid's algorithm    
def gcd(n, d):
    (s, t) = xgcd(n, d)
    return s * n + t * d
    
# Prints a solution to the jugs problem with jug sizes a and b and target v
# Assume a <= b 
def jugs(a, b, v):
    if v % gcd(a, b) != 0 or v < 0 or v > b:
        print "The jugs problem has no solution"
    else:
        x = 0    # amount of water in jug A
        y = 0    # amount of water in jug B
        while y != v:
            # jug A is empty, fill it
            x = a
            print "Filling up jug A --> (", x, ", ", y, ")"
            
            # empty jug A into jug B
            if x > b - y:  # jug B must be filled then emptied
                x = x - b + y
                y = b
                print "Pouring from jug A to jug B --> (", x, ", ", y, ")"

                y = 0
                print "Emptying jug B --> (", x, ", ", y, ")" 
            y = y + x      # jug B has space, pour from jug A
            x = 0
            print "Pouring from jug A to jug B --> (", x, ", ", y, ")"