# -*- Mode: Python -*-

# 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']

# these will flip, depending on which way
# the puzzle is oriented...
a, b = 1, 0

# this scores the harder version of the puzzle.
def score_hard (p):
    s = 0
    if p[0][a] == p[1][a] == p[2][a]:
        s += 1
    if p[1][b] == p[4][b] == p[5][b]:
        s += 1
    if p[5][a] == p[6][a] == p[9][a]:
        s += 1
    if p[2][b] == p[6][b] == p[7][b]:
        s += 1
    if p[7][a] == p[8][a] == p[10][a]:
        s += 1
    if p[0][b] == p[8][b] == p[3][b]:
        s += 1
    if p[9][b] == p[10][b] == p[11][b]:
        s += 1
    return s

# scores the easier.
# Note: always start with the ropi side on top,
# otherwise these are reversed?
def score_easy (p):
    s = 0
    if p[0][a] == p[1][a] == p[2][a]:
        s += 1
    if p[1][b] == p[4][b] == p[5][b]:
        s += 1
    if p[5][a] == p[6][a] == p[9][a]:
        s += 1
    if p[2][b] == p[6][b] == p[7][b]:
        s += 1
    if p[7][a] == p[8][a] == p[10][a]:
        s += 1
    if p[0][b] == p[8][b] == p[3][b]:
        s += 1
    if p[9][b] == p[10][b] == p[11][b]:
        s += 1
    return s

# absolute doesn't work very well.  I think this is because it
# requires a particular orientation, and since our moves are described
# in a way that requires 'disorienting' the puzzle, it can't easily
# find a solution that way...

# ok, now I changed it to 'rotate' the puzzle, but since the 'walk'
# created by 0..12 is arbitrary, 'close' solutions are actually not
# very close in any sense that is satisfying to humans.

score_table = {}
for p in range (12):
    score_table[solved[p]] = p
    
def score_absolute (p):
    # first, rotate around the 'br' piece.
    r = range (12)
    l = list (p)
    i = l.index ('br')
    for x in range (12):
        r[x] = p[(x + i) % 12]
    # now, compute deltas...
    delta = 0
    for i in range (12):
        j = score_table[r[i]]
        delta += abs (j-i)
    return -delta

# moves cannot put the 'other' side's color on the top,
# otherwise the score() function gets broken. [you can't
# solve both versions of the puzzle simultaneously!]

#    (0,1,2,3,4,5,6,7,8,9,10,11)  layout
# <move>: (<new-orientation>, <changes-score>)
op_dict = {
    # cw rotation
    '+': ((2,0,1,7,8,3,4,5,6,11,9,10), 0),
    # cw rotate top
    'T': ((2,0,1,3,4,5,6,7,8,9,10,11), 1),
    # flip puzzle (i.e., grab <6> and put it at <0>)
    'F': ((6,5,9,2,1,4,11,10,7,3,8,0), 0),
    # cw rotate right front 'flower'
    'R': ((0,5,2,3,1,4,6,7,8,9,10,11), 1),
    }

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, rescore), name in ops:
        p2 = move (p, op)
        if not seen.has_key (p2):
            if rescore:
                moves.append ((score (p2), (p2, name)))
            else:
                moves.append ((last, (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 == 7:
                    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!'
    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))

if __name__ == '__main__':
    import sys

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

    if '-e' in sys.argv:
        sys.argv.remove ('-e')
        score = score_easy
        print 'scoring for easy version [corners, not faces]...'
    elif '-a' in sys.argv:
        sys.argv.remove ('-a')
        score = score_absolute
    else:
        score = score_hard
        print 'scoring for hard version [faces, not corners]...'

    a, b = 1, 0

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

    search (t0, depth)