# -*- Mode: Python -*-

solved = (0,1,2,3,4,5,6,7)

# both are viewed from above,
# with 'square-1' logo in front!
#  2
# 1 3
#  0
#  6
# 5 7
#  4

# 0 wy
# 1 wr
# 2 wb
# 3 wo
# 4 gy
# 5 gr
# 6 gb
# 7 go

ops = [
    ((6,1,4,3,2,5,0,7), 't1+*t1-b1-*b1+'),
    ((4,1,2,5,0,3,6,7), 'b1-*b3-*b1+t1+*t6+*t1-b1-*b3+*b1+t1+*t6*t1-'),
    # these are from a web site, but I think one of them messes up corners
    #((3,1,2,0,7,5,6,4), 'b2+*b3-*t1+b1+*t1-b2+*b2-'),
    #((2,1,0,7,4,5,6,3), 't1+*b3-*b3-*t1-b1-*t1+b4+*b3+*t1-'),
    ((3,0,1,2,4,5,6,7), 't3+'),
    ((1,2,3,0,4,5,6,7), 't3-'),
    ((0,1,2,3,5,6,7,4), 'b3+'),
    ((0,1,2,3,7,4,5,6), 'b3-'),
    ]

class GotIt (Exception):
    pass

def move (p, op):
    return tuple ([p[i] for i in op])

def _search (p, d, seen, limit, best):
    moves = []
    for op, name in ops:
        p2 = move (p, op)
        if not seen.has_key (p2):
            moves.append ((p2, name))
    # try to sort by closest-to-solved
    moves.sort()
    #print '%s%s [%d]' % (' '*d, p, len(moves))
    for p2, name in moves:
        if p2 == solved:
            print p2, name
            raise GotIt
        elif d < limit:
            if moves < best[0]:
                best[0] = moves, p2
            try:
                seen[p2] = None
                _search (p2, d+1, seen, limit, best)
            except GotIt:
                print p2, name
                raise GotIt

def search (p, limit=12):
    seen = {}
    best = [p]
    try:
        _search (p, 0, seen, limit, best)
    except GotIt, why:
        print 'len(seen)==%d' % len(seen)
    else:
        print 'best=%r' % (best,)
    print 'positions searched: %d' % (len(seen))

if __name__ == '__main__':
    import sys
    #t0 = (5,1,6,0,2,3,4,7)
    t0 = (2,3,0,1,7,4,5,6)

    if len(sys.argv) > 1:
        depth = int(sys.argv[1])
    else:
        depth = 20
    search (t0, depth)