avva glass water problem

glass_water_avva.py

# -*- encoding: UTF-8 -*-

# http://avva.livejournal.com/2827068.html
# run as:
# ( echo шир. узк. ; python glass_water_avva.py | tac )   | column -t

# v1 - широкий стакан
# v2 - узкий стакан

from fractions import Fraction

def variants(var):
    (v1, v2) = var
    return [(v1_new, v2_new) for v1_new, v2_new in [
            (9*v2/4, v2), # наливаем в широкий первый до уровня воды во втором узком
            (v1, 4*v1/9), # наливаем в узкий второй до уровня воды в первом широком
            (v1, Fraction(4)/9), # наливаем в узкий второй до высоты первого широкого
            (0, v2), #выливаем стакан
            (v1, 0),
            (1, v2), #наливаем до краёв
            (v1, 1),
            (v1+v2, 0), #выливаем один в другой
            (0, v1+v2),
            (v1+v2-1, 1), #доливаем из одного в другой, пока помещается
            (1, v1+v2-1),

            #(1-v2, v2), #ставим один стакан в другой, так что бы объёмом второго слить лишнюю воду из полного первого
            #(Fraction(5)/9, v2), #ставим один стакан в другой на дно
            
            #(Fraction(1)/2, v2), #наливаем половину стакана при помощи наклона
            #(v1, Fraction(1)/2),
        ]
        if 0 <= v1_new <= 1 and 0 <= v2_new <= 1
    ]


def main():
    vars = {(Fraction(0), Fraction(0)) : None}
    def breadth_search():
        while 1:
            for var, prev in vars.items():
                if Fraction(2)/3 in var: 
                    return var
                for var2 in variants(var):
                    if var2 not in vars:
                        vars[var2] = var
        
    waypoint = breadth_search()
    while waypoint != None:
        v1, v2 = waypoint
        print v1, v2, '->'
        waypoint = vars[waypoint]

main()