# -*- Mode: Python -*-

import random

# 8 colors:
# red
# yellow
# green
# blue
# purple
# indigo (pink)
# orange
# chartreuse (light green)
# 
# grouped in fours:
# ropi
# gybc
# 
# 12 pieces:
# co,cr, cp
# yi, yo, yr
# gp, gi, go
# bp, bi, br
# 
# 0 co
# 1 cr
# 2 cp
# 3 yi
# 4 yo
# 5 yr
# 6 gp
# 7 gi
# 8 go
# 9 bp
# a bi
# b br

# layout:
# from above, 0-1-2 on top, 9-a-b on bottom.
#
#         8    0   3
#
#       7    A   B    4
#
#          2       1
#              9
#
#            6   5

#            0     1     2     3     4     5     6     7     8     9    10    11
solved  = ['br', 'cr', 'yr', 'bp', 'cp', 'co', 'yo', 'yi', 'bi', 'go', 'gi', 'gp']

def score (p):
    # just count the number of pieces in place.
    r = 0
    for i in range (12):
        if p[i] == solved[i]:
            r += 1
    return r

# there are 8 possible moves.

# what should we name them?
# T  Top
# RF Right Front
# LF Left Front
# F  Front
# B  Back
# RB Right Back
# LB Left Back
# B  Bottom

#    (0,1,2,3,4,5,6,7,8,9,10,11)  layout
# <move>: <new-orientation>
op_dict = {
    # top
    'TP':  (2,0,1,3,4,5,6,7,8,9,10,11),
    # right front
    'RF': (0,5,2,3,1,4,6,7,8,9,10,11),
    # left front
    'LF': (0,1,7,3,4,5,2,6,8,9,10,11),
    # front
    'FT':  (0,1,2,3,4,6,9,7,8,5,10,11),
    # back
    'BA': (3,1,2,8,4,5,6,7,0,9,10,11),
    # left back
    'LB': (0,1,2,3,4,5,6,8,10,9,7,11),
    # bottom
    'BO': (0,1,2,3,4,5,6,7,8,10,11,9),
    }

ops = [ (v, k) for (k, v) in op_dict.items() ]

class Stop (Exception):
    pass

def check (p):
    p = list(p[:])
    p.sort()
    s = solved[:]
    s.sort()
    if p != s:
        raise ValueError, 'invalid board'

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

def flat_path (path):
    r = []
    while path is not None:
        name, path = path
        r.append (name)
    r.reverse()
    return r

def _search (p, d, seen, limit, last, best, path):
    moves = []
    for op, name in ops:
        p2 = move (p, op)
        if not seen.has_key (p2):
            moves.append ((score (p2), (p2, name)))
    # try to sort by closest-to-solved
    moves.sort (reverse=True)
    for s, (p2, name) in moves:
        #print '%s %s %s' % ('  '*d, p2, name)
        if d < limit:
            if s > best[0][2]:
                best[0] = flat_path ((name, path)), p2, s
                if s == 12:
                    raise Stop
            seen[p2] = s
            _search (p2, d+1, seen, limit, s, best, (name, path))
        else:
            break

def search (p0, limit=12):
    global seen
    seen = {}
    best = [([], p0, score(p0))]
    path = None
    check (p0)
    s0 = score (p0)
    print 'initial score=', s0
    try:
        _search (p0, 0, seen, limit, s0, best, path)
    except Stop:
        print 'Got it!'
    except KeyboardInterrupt:
        print 'Halted Search.'
    print 'best:'
    print '   ', p0, score (p0)
    path, p, s = best[0]
    p2 = p0
    for name in path:
        p2 = move (p2, op_dict[name])
        print name, score (p2), p2
    print '-' * 80
    print s, p
    print 'positions searched: %d' % (len(seen))

def randomize (n=20):
    p = tuple (solved)
    keys = op_dict.keys()
    name = '  '
    for x in range (n):
        print name, score (p), p
        name = random.choice (keys)
        p = move (p, op_dict[name])
    print name, score (p), p
        
def move (p, op):
    return tuple ([p[i] for i in op])


if __name__ == '__main__':
    import sys

    t0 = ('br','yo','cr','gp','cp','yi','bp','go','co','yr','gi','bi')

    if '-r' in sys.argv:
        randomize()
    else:
        if len(sys.argv) > 1:
            depth = int(sys.argv[1])
        else:
            depth = 20

        search (t0, depth)