# -*- coding: utf-8 -*-
# ENGG 2440A Lecture 4 -- python code
# Requires: python3

# 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
    

# State machine for the jugs game
class Jugs:
    def __init__(self, a, b, verbose = False):
        self.capacity = {}
        self.capacity['A'] = a
        self.capacity['B'] = b
        self.water = {}
        self.water['A'] = 0
        self.water['B'] = 0
        self.verbose = verbose
        
        if self.verbose:
            self._print_state("Start")
        
    def is_empty(self, jug):
        return self.water[jug] == 0
        
    def is_full(self, jug):
        return self.water[jug] == self.capacity[jug]        
    
    def contents(self, jug):
        return self.water[jug]                
                                                    
    def spill(self, jug):
        self.water[jug] = 0

        if self.verbose:
            self._print_state("Spill " + jug)
                            
    def fill(self, jug):
        self.water[jug] = self.capacity[jug]

        if self.verbose:
            self._print_state("Fill " + jug)
                                        
    def pour(self, fromjug, tojug):
        slack = self.capacity[tojug] - self.water[tojug]
        if self.water[fromjug] <= slack:
            self.water[tojug] += self.water[fromjug]
            self.water[fromjug] = 0
        else:
            self.water[tojug] += slack
            self.water[fromjug] -= slack
            
        if self.verbose:
            self._print_state(fromjug + " - " + str(slack) + " l -> " + tojug)
                                                                                        
    def _draw(self, jar):
        return '=' * self.water[jar] + '.' * (self.capacity[jar] - self.water[jar])
        
    def _print_state(self, last_transition):
           print('{:<25}'.format(last_transition), 'A:', self._draw('A'), '  B:', self._draw('B'))
         
# Play the jugs game interactively
def play_jugs(a, b, v):
    game = Jugs(a, b, True)

    while game.contents('A') != v and game.contents('B') != v:
        move = input("Your move: ").upper()
        
        if move not in ('FA', 'FB', 'SA', 'SB', 'AB', 'BA', 'Q'):
            print("Invalid move!")
        elif move == 'q':
            return
        elif move[0] == 'F':
            game.fill(move[1])
        elif move[0] == 'S':
            game.spill(move[1])
        else:
            game.pour(move[0], move[1])

    print("You win!")

# Play the jugs game with the zigzag strategy
def zigzag_jugs(a, b, v):
    game = Jugs(a, b, True)
    
    while game.contents('A') != v:
        game.fill('B')
        game.pour('B', 'A')
        if game.is_full('A'):
            game.spill('A')
            game.pour('B', 'A')