rotate4

rotate4.py

import itertools,functools,random

@functools.lru_cache(maxsize=None)
def C(n,k):
    """Return the binomial coefficient n!/(k!(n-k)!) for nonnegative integers n,k."""
    if k < 0 or k > n:
        return 0
    c = 1
    for i in range(k):
        c = c*(n-i)//(i+1)
    return c

@functools.lru_cache(maxsize=None)
def factorial(n):
    """Return the factorial of a nonnegative integer."""
    if n < 2:
        return 1
    f = 2
    for i in range(3,n+1):
        f *= i
    return f

@functools.lru_cache(maxsize=16384)
def bits_to_combindex(l):
    """Represent a list of bits (big-endian) as an index among all lists with the same sum."""
    bits = len(l)
    ones = sum(l)
    zeros = bits-ones
    if zeros == 0 or ones == 0 or bits == 1:
        return 0
    b = C(bits-1,ones)
    ind = 0
    while zeros > 0 and ones > 0 and bits > 1:
        bits -= 1
        if l[0] == 0:
            zeros -= 1
            b = b*zeros//bits
        else:
            ind += b
            b = b*ones//bits
            ones -=1
        l = l[1:]
    return ind

def combindex_to_bits(ind,ones,bits=None):
    """Look up an index among all bit lists with the same sum."""
    if ind == 0:
        if bits is None:
            return (1,)*ones
        return (0,)*(bits-ones)+(1,)*ones
    if bits is None:
        bits = ones
        b = C(bits,ones)
        while ind >= b:
            bits += 1
            b = C(bits,ones)
    zeros = bits-ones
    b = C(bits-1,ones)
    l = []
    for i in range(bits-1):
        bits -= 1
        if ind < b:
            l.append(0)
            zeros -= 1
            b = b*zeros//bits
        else:
            l.append(1)
            ind -= b
            b = b*ones//bits
            ones -= 1
    return l+[ones]

def permutation_to_index(perm):
    n = len(perm)
    f = factorial(n-1)
    ind = 0
    while n > 1:
        ind += perm[0]*f
        perm = list(map(lambda x:x-(x>perm[0]),perm[1:]))
        n -= 1
        f //= n
    return ind

def index_to_permutation(ind,n):
    perm = []
    p = list(range(n))
    f = factorial(n-1)
    for i in range(n-1):
        perm += [p.pop(ind//f)]
        ind %= f
        f //= n-1-i
    return tuple(perm+p)

def permute(l,perm):
    """
    Permute the elements of a specified listlike with the specified permutation.
    Can also be used for composing permutations (though note that the argument
    order is reversed).
    """
    return tuple(map(l.__getitem__,perm))

@functools.lru_cache()
def invert(perm):
    """Invert a permutation."""
    inv = [None]*len(perm)
    for (i,e) in enumerate(perm):
        inv[e] = i
    return tuple(inv)

def m(x,y,n=4):
    """
    Generate a permutation corresponding to a move at the specified locations on
    a board of the specified size.
    """
    p = list(range(n*n))
    a = x+n*y
    b,c,d = a+n,a+n+1,a+1
    p[a] = b
    p[b] = c
    p[c] = d
    p[d] = a
    return tuple(p)

@functools.lru_cache()
def gen_moves(n=4,qtm=True):
    """
    Generate a list of moves:
    m(0,0), m(1,0), ..., m(n-2,n-2), 
    m(0,0)^2, m(1,0)^2, ..., m(n-2,n-2)^2, (if qtm is false)
    m(0,0)^3, m(1,0)^3, ..., m(n-2,n-2)^3
    qtm specifies if a quarter-turn metric should be used (default true).
    """
    locations = [(i,j,4) for j in range(n-1) for i in range(n-1)]
    moves_cw = tuple(itertools.starmap(m,locations))
    moves = moves_cw
    if not qtm:
        moves += tuple(map(lambda p:permute(p,p),moves_cw)) 
    moves += tuple(map(lambda p:invert(p),moves_cw))
    return moves

@functools.lru_cache()
def gen_phase1_transition(moves=gen_moves()):
    """Generate the transition table for phase 1."""
    transition = [None]*C(16,8)
    for i in range(C(16,8)):
        state = combindex_to_bits(i,ones=8,bits=16)
        transition[i] = tuple([bits_to_combindex(permute(state,move)) for move in moves])
    return tuple(transition)

@functools.lru_cache()
def gen_phase1t_transition(moves=gen_moves()):
    """Generate the transition table for the transpose of phase 1."""
    transition = [None]*C(16,8)
    for i in range(C(16,8)):
        state = combindex_to_bits((i+2228)%C(16,8),ones=8,bits=16)
        transition[i] = tuple([(bits_to_combindex(permute(state,move))-2228)%C(16,8) for move in moves])
    return tuple(transition)

@functools.lru_cache()
def gen_phase2_transition(moves=gen_moves()):
    """Generate the transition table for phase 2."""
    if len(moves[0]) == 16:
        moves = tuple(map(lambda m:m[:8],filter(lambda m:m[8:]==tuple(range(8,16)),moves)))
    # get rid of the moves that affect the bottom half
    # and store only the top half
    transition = [None]*factorial(8)
    i = 0
    for state in itertools.permutations(range(8)):
        transition[i] = tuple([permutation_to_index(permute(state,move)) for move in moves])
        i += 1
    return tuple(transition)

@functools.lru_cache()
def gen_lookup(transition):
    """
    Generate a God's algorithm lookup table given a transition table using
    breadth-first search. State 0 is assumed to be the solved state.
    """
    lookup = [None]*len(transition)
    lookup[0] = 0
    entries = 1
    depth = 0
    last_states = [0]
    while len(last_states) > 0:
        depth += 1
        states = []
        for state in last_states:
            for new_state in transition[state]:
                if lookup[new_state] is None:
                    lookup[new_state] = depth
                    states.append(new_state)
        last_states = states
        entries += len(states)
    return tuple(lookup)

def gen_phase1_lookup(moves=gen_moves()):
    return gen_lookup(gen_phase1_transition(moves=moves))

def gen_phase2_lookup(moves=gen_moves()):
    return gen_lookup(gen_phase2_transition(moves=moves))

def phase1_solve(state,moves=gen_moves()):
    """Return a list of moves for a phase 1 solve."""
    state = bits_to_combindex(tuple(map(lambda x:x//8,state)))
    # reduce the state from a fully specified grid to one that only specifies
    # which half pieces belong to, since that's all we need here.
    transition = gen_phase1_transition(moves=moves)
    lookup = gen_phase1_lookup(moves=moves)
    m = []
    for i in itertools.cycle(range(len(moves))):
        if lookup[state] == 0:
            break
        if lookup[state] > lookup[transition[state][i]]:
            m.append(i)
            state = transition[state][i]
    return tuple(m)

def phase2_solve(state,moves=gen_moves()):
    """Return a list of moves for a phase 2 solve."""
    allmoves = moves
    moves = tuple(map(lambda m:m[:8],filter(lambda m:m[8:]==tuple(range(8,16)),moves)))
    transition = gen_phase2_transition(moves=moves)
    lookup = gen_phase2_lookup(moves=moves)
    top = permutation_to_index(state[:8])
    bot = permutation_to_index(tuple(map(lambda x:x-8,state[8:])))
    mtop = []
    mbot = []
    for i in itertools.cycle(range(len(moves))):
        if lookup[top] == 0:
            break
        if lookup[top] > lookup[transition[top][i]]:
            mtop.append(i)
            top = transition[top][i]
    for i in itertools.cycle(range(len(moves))):
        if lookup[bot] == 0:
            break
        if lookup[bot] > lookup[transition[bot][i]]:
            mbot.append(i)
            bot = transition[bot][i]
    # expand the range of moves
    mtop = tuple(map(lambda x:x%3+x//3*9,mtop))
    mbot = tuple(map(lambda x:x%3+x//3*9+6,mbot))
    return mtop+mbot

def twophase_solve(state,moves=gen_moves()):
    phase1 = phase1_solve(state,moves=moves)
    for m in phase1:
        state = permute(state,moves[m])
    phase2 = phase2_solve(state,moves=moves)
    return phase1+phase2

def ida_solve(state,moves=gen_moves(),maxdepth=20,prune=True,verbose=True):
    """Solve a state with IDA*. Code adapted from http://www.jaapsch.net/puzzles/compcube.htm ."""
    if state == tuple(range(16)):
        return ()
    if prune:
        index_v = bits_to_combindex(tuple(map(lambda x:x//8,state)))
        index_h = (bits_to_combindex(tuple(map(lambda x:x%4//2,state)))-2228)%C(16,8)
        transition_v = gen_phase1_transition(moves=moves)
        transition_h = gen_phase1t_transition(moves=moves)
        lookup_v = gen_lookup(transition_v)
        lookup_h = gen_lookup(transition_h)
    else:
        index_v = 0
        index_h = 0
        transition_v = ((0,)*len(moves),)
        transition_h = ((0,)*len(moves),)
        lookup_v = (0,)
        lookup_h = (0,)
    start = max(lookup_v[index_v],lookup_h[index_h])
    for depth in range(start,maxdepth+1):
        if verbose:
            print('starting search at depth %d'%depth)
        result = treesearch(state,index_v,index_h,depth,moves=moves,tv=transition_v,th=transition_h,lv=lookup_v,lh=lookup_h)
        if result is not None:
            return result
    return None

def treesearch(state,iv,ih,depth,moves,tv,th,lv,lh):
    if state == tuple(range(16)):
        return ()
    elif depth < 1:
        return None
    dist = max(lv[iv],lh[ih])
    if dist > depth:
        return None
    for (i,move) in enumerate(moves):
        result = treesearch(permute(state,move),tv[iv][i],th[ih][i],depth-1,moves,tv,th,lv,lh)
        if result is not None:
            return (i,)+result
    return None

#[10, 1, 4, 13, 5, 11, 14, 2, 0, 8, 12, 15, 9, 3, 7, 6]

def limitedscramble(n=4,maxmoves=10):
    """Provide a scrambled state solvable within the specified number of moves."""
    m = maxmoves-random.randrange(2) # avoid parity effects
    state = tuple(range(n*n))
    moves = gen_moves(n=n)
    for i in range(m):
        move = random.choice(moves)
        state = permute(state,move)
    return state

'''
the two-phase solve performs relatively badly; swapping two adjacent pieces only
requires 5q*, but restricting the moves to a 4x2 subgrid increases this to at
least 9q*, depending on where the two pieces are.

instead we could try a different set of phases. first reduce from
<...>
to
<m(1,0),m(0,1),m(1,1),m(2,1),m(1,2)> (solving the four corners)
then to
<m(1,0),m(0,1),m(1,1)> (solving the bottom and right edges)
then finally to
<> ~= {I} (solving the rest)

the coset spaces have sizes 43680, 11880 and 40320 respectively, so once again
we may store all of it in memory. (possible modification: instead of storing
both phase 2 and 3, we can just use IDA* with phase 2 as a heuristic.)
'''

def get_threephase_phase1_index(state):
    for m in range(16):
        if state[m] == 0:
            i = m
        elif state[m] == 3:
            j = m
        elif state[m] == 12:
            k = m
        elif state[m] == 15:
            l = m
    return (i<<12)|(((j-3)%16)<<8)|(((k-12)%16)<<4)|((l-15)%16)
    # not the most compact way of generating an index, but being slightly
    # wasteful here is all right

@functools.lru_cache()
def gen_threephase_phase1_transition(moves=gen_moves()):
    """Generate the transition table for phase 1 of a three-phase solve."""
    transition = [None]*65536
    for i,j,k,l in itertools.permutations(range(16),4):
        state = [-1]*16
        state[i] = 0
        state[j] = 3
        state[k] = 12
        state[l] = 15
        transition[get_threephase_phase1_index(state)] = tuple((get_threephase_phase1_index(permute(state,move)) for move in moves))
    return tuple(transition)

'''
qtm antipode at:
p . . m
. . . .
. . . .
d . . a
'''

def get_threephase_phase2_index(state):
    for m in range(16):
        if state[m] == 7:
            i = (m-7)%16
        elif state[m] == 11:
            j = (m-11)%16
        elif state[m] == 13:
            k = (m-13)%16
        elif state[m] == 14:
            l = (m-14)%16
    return (i<<12)|(j<<8)|(k<<4)|(l)
    # again, wasteful, and even more so this time, but I'm lazy

@functools.lru_cache()
def gen_threephase_phase2_transition(moves=gen_moves()):
    moves = list(moves)
    for i in range(0,len(moves),9):
        moves[i] = moves[i+2] = moves[i+6] = moves[i+8] = tuple(range(16))
        # replace the non-generator moves with identity so we don't mess up move indexing
    transition = [None]*65536
    for i,j,k,l in itertools.permutations((1,2,4,5,6,7,8,9,10,11,13,14),4):
        state = [-1]*16
        state[i] = 7
        state[j] = 11
        state[k] = 13
        state[l] = 14
        transition[get_threephase_phase2_index(state)] = tuple((get_threephase_phase2_index(permute(state,move)) for move in moves))
    return tuple(transition)

def get_threephase_phase3_index(state):
    reduce = ((None,0,1,None,2,3,4,None,5,6,7)+(None,)*5).__getitem__
    return permutation_to_index(tuple(filter(lambda x:x is not None,map(reduce,state))))

@functools.lru_cache()
def gen_threephase_phase3_transition(moves=gen_moves()):
    moves = list(moves)
    for i in range(0,len(moves),9):
        moves[i] = moves[i+2] = moves[i+5] = moves[i+6] = moves[i+7] = moves[i+8] = tuple(range(16))
    reduce = ((None,0,1,None,2,3,4,None,5,6,7)+(None,)*5).__getitem__
    moves = tuple( (tuple(filter(lambda x:x is not None,map(reduce,move))) for move in moves) )
    transition = [None]*40320
    i = 0
    for state in itertools.permutations(range(8)):
        transition[i] = tuple([permutation_to_index(permute(state,move)) for move in moves])
        i += 1
    return tuple(transition)

def threephase_phase1_solve(state,moves=gen_moves()):
    """Return a list of moves for a phase 1 solve."""
    state = get_threephase_phase1_index(state)
    transition = gen_threephase_phase1_transition(moves=moves)
    lookup = gen_lookup(transition)
    m = []
    for i in itertools.cycle(range(len(moves))):
        if lookup[state] == 0:
            break
        if lookup[state] > lookup[transition[state][i]]:
            m.append(i)
            state = transition[state][i]
    return tuple(m)

def threephase_phase1_solve(state,moves=gen_moves()):
    """Return a list of moves for a phase 1 solve."""
    state = get_threephase_phase1_index(state)
    transition = gen_threephase_phase1_transition(moves=moves)
    lookup = gen_lookup(transition)
    m = []
    for i in itertools.cycle(range(len(moves))):
        if lookup[state] == 0:
            break
        if lookup[state] > lookup[transition[state][i]]:
            m.append(i)
            state = transition[state][i]
    return tuple(m)

def threephase_phase1_solve(state,moves=gen_moves()):
    """Return a list of moves for a phase 1 solve."""
    state = get_threephase_phase1_index(state)
    transition = gen_threephase_phase1_transition(moves=moves)
    lookup = gen_lookup(transition)
    m = []
    for i in itertools.cycle(range(len(moves))):
        if lookup[state] == 0:
            break
        if lookup[state] > lookup[transition[state][i]]:
            m.append(i)
            state = transition[state][i]
    return tuple(m)

def threephase_phase2_solve(state,moves=gen_moves()):
    """Return a list of moves for a phase 2 solve."""
    state = get_threephase_phase2_index(state)
    transition = gen_threephase_phase2_transition(moves=moves)
    lookup = gen_lookup(transition)
    m = []
    for i in itertools.cycle(range(len(moves))):
        if lookup[state] == 0:
            break
        if lookup[state] > lookup[transition[state][i]]:
            m.append(i)
            state = transition[state][i]
    return tuple(m)

def threephase_phase3_solve(state,moves=gen_moves()):
    """Return a list of moves for a phase 3 solve."""
    state = get_threephase_phase3_index(state)
    transition = gen_threephase_phase3_transition(moves=moves)
    lookup = gen_lookup(transition)
    m = []
    for i in itertools.cycle(range(len(moves))):
        if lookup[state] == 0:
            break
        if lookup[state] > lookup[transition[state][i]]:
            m.append(i)
            state = transition[state][i]
    return tuple(m)

def threephase_solve(state,moves=gen_moves()):
    phase1 = threephase_phase1_solve(state,moves=moves)
    for m in phase1:
        state = permute(state,moves[m])
    phase2 = threephase_phase2_solve(state,moves=moves)
    for m in phase2:
        state = permute(state,moves[m])
    phase3 = threephase_phase3_solve(state,moves=moves)
    return phase1+phase2+phase3