import time

print = (lambda p: lambda *args, **kwargs: [p(*args, **kwargs), time.sleep(.01)])(print)


class Tower:
    def __init__(self, name, state):
        self.data = state
        self.name = name

    def append(self, el):
        self.data.append(el)

    def pop(self):
        return self.data.pop()

    def can_put_on_top(self, el):
        if len(self.data) == 0:
            return True
        if self.data[-1] > el:
            return True
        return False

    def __str__(self):
        return self.name + str(self.data)

    def __len__(self):
        return len(self.data)


from itertools import tee, permutations, product
from copy import copy
from random import shuffle


def pprint(towers, tower_order):
    s = {tower.name: tower for tower in towers}
    ans = []
    for tower in tower_order:
        ans.append('{}'.format(s[tower]))
    print('\t\t'.join(ans))


tower_a = Tower('left', [4,2,1,5])
tower_b = Tower('middle', [])
tower_c = Tower('right', [])

iteration = 0


def hanoi(source, dest, storage, moves, level):
    global iteration

    # print('moves:')
    # for move in moves:
    #     print(':', move)

    if len(source) == 0:
        # print('Its empty')
        return False
    mov = '{} {} {}'.format(tower_a, tower_b, tower_c)
    el = source.pop()

    if dest.can_put_on_top(el):

        dest.append(el)
        # check if won
        if '{} {} {}'.format(tower_a, tower_b, tower_c) in moves:
            source.append(dest.pop())
            # print('Already moved')
            return False

        if len(tower_a) == 0 and len(tower_b) == 0:

            print('-> ' * level, '{} -> {}'.format(source, dest))
            print('- WON -' * 10)
            print(tower_a, tower_b, tower_c)
            source.append(dest.pop())
            return True
    else:
        # move back
        source.append(el)
        # print('Cant put')
        return False

    # if level == 20:
    #     return True

    moves.add(mov)
    print('-> ' * level, '{} -> {}'.format(source, dest))
    # print('Adding move:', mov)
    for s, d, st in permutations([source, dest, storage], 3):
        if '{} {} {}'.format(tower_a, tower_b, tower_c) in moves:
            continue

        if hanoi(s, d, st, moves, level + 1):

            source.append(dest.pop())
            print(tower_a, tower_b, tower_c)
            return True
        else:
            pass
            # print(False)

    moves.remove(mov)
    source.append(dest.pop())
    return False


hanoi(tower_a, tower_b, tower_c, set(), 0)