Permuting Aces into the Dealer's Hand

# Place four aces from the top of the deck into the dealer's hand
# by Mark Gritter, June 6 2012

from Queue import deque

def inShuffleSource( p, numCards ):
    if p % 2 == 0:
        return numCards / 2 + p / 2
    else:
        return ( p - 1 ) / 2

def outShuffleSource( p, numCards ):
    if p % 2 == 0:
        return p / 2
    else:
        return numCards / 2 + ( p - 1 ) / 2

inShuffleIdx = [ inShuffleSource( p, 52 ) for p in xrange( 52 ) ]
outShuffleIdx = [ outShuffleSource( p, 52 ) for p in xrange( 52 ) ]

def inShuffle( deck ):
    return ''.join( deck[inShuffleIdx[p]] for p in xrange( 52 ) )

def outShuffle( deck ):
    return ''.join( deck[outShuffleIdx[p]] for p in xrange( 52 ) )

def search( deck, goal ):
    visited = { deck : ( 'origin', None ) }
    queue = deque( [deck] )
    while len( queue ) > 0:
        parent = queue.popleft()

        left = inShuffle( parent )
        if left == goal:
            visited[left] = ( 'out', parent )
            return visited
        elif left in visited:
            continue
        else:
            visited[left] = ( 'in', parent )
            queue.append( left )

        right = outShuffle( parent )
        if right == goal:
            visited[right] = ( 'out', parent )
            return visited
        elif right in visited:
            continue
        else:
            visited[right] = ( 'out', parent )
            queue.append( right )

    raise Exception, "No path found."

def path( goal, visited ):
    lastMove = None
    curr = goal
    moves = []
    while lastMove != 'origin':
        ( move, prev ) = visited[ curr ]
        moves.append( (move, curr) )
        lastMove = move
        curr = prev

    moves.reverse()
    return moves

def solveAces( ):
    current = "AAAA" + "x" * 48
    #goal = "xxxxA" * 4 + "x" * 32
    goal = "xxxxA" * 1 + "xxxxx" + "xxxxA" * 3 + "x" * 27
    visit = search( current, goal )
    moves = path( goal, visit )
    for ( s, d ) in moves:
        print s, d
    print len( moves ) - 1, "moves"
    print len( visit ), "nodes generated"