'''
Sokoban solver probeersel

Voor de beschrijving van een sokoban maze gebruiken we twee data
structuren, als eerste een list van strings volgens het gebruikelijke
sokoban formaat en als twee een numpy 2D NumPy array van integers met
de informatie in de individuele bitjes.

                          text           bit

Floor                     (Space)        0
Wall                      #              1
Player                    @              2
Box                       $              4
Goal square               .              8
Player on goal square     +              2 + 8 = 10
Box on goal square        *              4 + 8 = 12

[volgende zijn niet applicable voor het text formaat]

Possible player pos
  without moving boxes                  16


Als conventie gebruiken we  variabelen met ergens 'TM' voor text
based mazes en 'BM' binary mazes.

Voor posities gebruiken we tuples met twee indices.

Een 'move' (van een box) bestaat uit een positie en een richting...

We hebben een aantal 1 regelige functies, maar die houden het wat leesbaar.

We gaan ervan uit dat we met 'correcte' mazes werken, maw dat
ze aan de randen zijn afgebakend, dat er 1 player is, etc, etc... .

Tijdens het oplossen willen we voorkomen dat we dezelfde mazes meerdere
keren onderzoeken, daarom houden we een lijst bij met situaties die we
hebben onderzocht (of bezig zijn te onderzoeken). Kortste vorm hiervoor
lijkt mij een lijst met box posities, en de eerste positie van een 'possible'
player positie. In een cirkeltje rond lopen heeft wel wat, maar het duurt
zo lang...


'''

# mijn imports...
import numpy as np    # uiteraard, want zonder... , dus...


# constants... dingen...
FLOOR    = 0
WALL     = 1
PLAYER   = 2
BOX      = 4
GOAL     = 8
POSSIBLE = 16

# constants... richtingen...
UP       = 1
DOWN     = 2
LEFT     = 3
RIGHT    = 4


# huishoudelijke functies....

def textMazeToBinaryMaze(inTM):
    '''
    Vorm een text based maze om tot een binary maze.
    '''
    heigth    = len(inTM)
    width     = max(len(row) for row in inTM)
    outBM     = np.zeros((heigth, width), dtype=np.int8)

    omzet = { ' ' : FLOOR,
              '#' : WALL,
              '@' : PLAYER,
              '$' : BOX,
              '.' : GOAL,
              '+' : PLAYER | GOAL,
              '*' : BOX | GOAL }
    
    for i,line in enumerate(inTM):
        for j,ch in enumerate(line):
            outBM[i,j] = omzet[ch]
    
    return outBM

def binaryMazeToTextMaze(inBM):
    '''
    Vorm een binary maze om tot een text based maze.
    '''
    heigth, width = inBM.shape
    outTM = []

    omzet = { FLOOR          : ' ',
              WALL           : '#',
              PLAYER         : '@',
              BOX            : '$',
              GOAL           : '.',
              PLAYER | GOAL  : '+',
              BOX | GOAL     : '*' }

    for i in range(heigth):
        line = ''
        for j in range(width):
            line += omzet[inBM[i,j] & (WALL | BOX | GOAL | PLAYER)]
        outTM.append(line) 
		    
    return outTM


# print functies....

def printTextMaze(inTM):
	'''
	Druk een text based maze af.
	'''
	for line in inTM:
		print(line)

def printBinaryMaze(inBM):
    '''
    Druk een binary based maze af.
    '''
    print printTextMaze(binaryMazeToTextMaze(inBM))

def printLegend():

    print '#   Wall'
    print '@   Player'
    print '$   Box'
    print '.   Goal'
    print '+   Player on Goal'
    print '*   Box on Goal'


# business functies

def findFirstOfSomething(inBM, inWhat):
    '''
    Find first occurence of something [PLAYER|BOX|GOAL|POSSIBLE....]
    '''
    heigth, width = inBM.shape
    pos = np.argmax(inBM & inWhat) # pas op: array is flattened
    return (pos / width, pos % width)


def findPlayer(inBM):
    '''
    Vind de positie van de Player.
    (is er maar 1 als het goed is)
    '''
    return findFirstOfSomething(inBM, PLAYER)

def findBoxes(inBM):
    '''
    Vind de posities van de Boxes en geef een lijst van posities
    '''
    myBM = inBM.copy() # we trekken een kopie

    poss = []
    while (numberOfBoxes(myBM)):
        pos = findFirstOfSomething(myBM, BOX)
        poss.append(pos)
        myBM[pos] = 0 # hmm, beetje stom maar oke...

    return poss

def neighbours(inPos):
    '''
    geeft een lijst van buren posities terug
    '''
    i = inPos[0]
    j = inPos[1]
    return [ (i-1,j), (i+1,j), (i,j-1), (i,j+1) ]

def neighboursAndOpposites(inPos):
    '''
    geeft een lijst met dicts met richtingen, buur, en tegenovergestelden terug
    '''
    i = inPos[0]
    j = inPos[1]
    return [ { 'dir' : UP,    'neighbour' : (i-1,j), 'opposite' : (i+1,j) },
             { 'dir' : DOWN,  'neighbour' : (i+1,j), 'opposite' : (i-1,j) },
             { 'dir' : LEFT,  'neighbour' : (i,j-1), 'opposite' : (i,j+1) },
             { 'dir' : RIGHT, 'neighbour' : (i,j+1), 'opposite' : (i,j-1) } ]

def movedPosition(inPos, inDir):
    '''
    geeft de positie van een verplaatsing
    '''
    i = inPos[0]
    j = inPos[1]
    if (inDir == UP)    : return (i-1,j)
    if (inDir == DOWN)  : return (i+1,j)
    if (inDir == LEFT)  : return (i,j-1)
    if (inDir == RIGHT) : return (i,j+1)

def setPossiblePlayerPos(inBM, inPos):
    '''
    Vind alle mogelijke posities beginnende bij inPos zonder
    boxes te verplaatsen.
    (we gaan er van uit dat de maze 'netjes' is afgebakend)
    (pas op: orginele inkomende maze wordt ook veranderdt)
    '''

    # set het begin punt
    inBM[inPos] |= POSSIBLE

    # set indien noodzakelijk de buren en recursief hunnie buren
    for pos in neighbours(inPos):
        if not (inBM[pos] & (POSSIBLE | WALL | BOX)):
            inBM = setPossiblePlayerPos(inBM, pos)

    return inBM

def unsetPossiblePlayerPos(inBM):
    return inBM & ~POSSIBLE
    
def movePlayer(inBM, inPos):
    '''
    Verplaats de player, negeer het af te leggen pad completely
    '''
    myBM = inBM.copy() # we trekken een kopie

    myBM = myBM & ~PLAYER
    myBM[inPos] |= PLAYER
    return myBM

def numberOfBoxes(inBM):
    return np.sum((inBM & BOX) == BOX)

def numberOfGoals(inBM):
    return np.sum((inBM & GOAL) == GOAL)

def numberOfBoxesOnGoals(inBM):
    return np.sum((inBM & (GOAL | BOX) == (BOX | GOAL)))

def isSolved(inBM):
    return numberOfBoxesOnGoals(inBM) == numberOfBoxes(inBM)


def findMoves(inBM):
    '''
    vind de mogelijke verplaatsing van boxes en geef een
    lijst terug van box posities met mogelijke verplaats
    richtingen.
    '''

    inBM = unsetPossiblePlayerPos(inBM) # voor de zekerheid
    inBM = setPossiblePlayerPos(inBM, findPlayer(inBM))

    moves = []
    for pos in findBoxes(inBM):
        for nao in neighboursAndOpposites(pos):
            if ( inBM[nao['opposite']]  &  POSSIBLE
                 and
       	         not inBM[nao['neighbour']] & (WALL | BOX) ):
       	         
                moves.append({ 'pos' : pos, 'dir' : nao['dir']})

    inBM = unsetPossiblePlayerPos(inBM)

    return moves        

def applyMove(inBM, inMove):
    '''
    Verplaats een box, we gaan er van uit dat het kan en
    verzetten ook de Player
    '''
    myBM = inBM.copy() # we trekken een kopie

	# box weghalen van de huidige positie en terug zetten op de nieuwe
    myBM[inMove['pos']] &= ~BOX
    myBM[movedPosition(inMove['pos'], inMove['dir'])] |= BOX

    # player komt per definitie op de oude box positie
    myBM = movePlayer(myBM, inMove['pos'])

    return myBM


def compactSituation(inBM):
    '''
    Maak een korte omschrijving van de maze situation
    '''
    inBM = unsetPossiblePlayerPos(inBM) # voor de zekerheid
    inBM = setPossiblePlayerPos(inBM, findPlayer(inBM))
    firstPossiblePlayerPos = findFirstOfSomething(inBM, POSSIBLE)
    inBM = unsetPossiblePlayerPos(inBM)

    return tuple([firstPossiblePlayerPos] + findBoxes(inBM))


def storeMaze(inBM):
    '''
    We slaan de huidige maze zo compact mogelijk op, namelijk een
    tuple met als eerste de eerst mogelijk player positie en
    vervolgend de box posities.
    '''
    global beenThereDoneThat
    beenThereDoneThat.append(compactSituation(inBM))

def beenThere(inBM):
    '''
    check of we deze maze situation al 'gehad' hebben
    '''
    global beenThereDoneThat
    return compactSituation(inBM) in beenThereDoneThat

def isZekerStuk(inBM):
    '''
    Deze functie checkt of een maze 'stuk' is doordat een box
    bijvoorbeeld 'vast' tegen een wand staat of vier boxes in
    een 'blokje' vast staan, en wellicht nog meer...
    Lastige functie, maar waarschijnlijk de key voor een
    goede solver....

    wellicht moeten we beginnen met een maze met verboden posities..
    '''

    # als we er al geweest zijn
    if beenThere(inBM):
        return True

    # als we niets meer kunnen bewegen zijn we stuk
    if not len(findMoves(inBM)): 
        return True

    # weet het eerst niet zeker...
    return False



# constants... solve results
SOLVED            = 1
STUCK             = 2
SHOULD_NOT_HAPPEN = 3

def solveMaze(inBM, inDepth):
    '''
    de 1 en enige	oplos functie...
    De functie geeft SOLVED of STUCK terug, als dat niet in 1 keer
    lukt gaan we de recursiviteit in.
    '''
    
    # basale check
    if isSolved(inBM):
        print("\nDepth : %d\n" % (inDepth))
        printBinaryMaze(inBM)
        return SOLVED

    # moeilijke check
    if (isZekerStuk(inBM)):
        return STUCK

    # sla toestand op in beenThereDoneThat
    storeMaze(inBM)

    # hmm, we moeten verder zoeken
    moves = findMoves(inBM)

    for move in moves:
        result = solveMaze(applyMove(inBM, move), inDepth+1)

        if result == SOLVED:
            print("\nDepth : %d \n" % (inDepth))
            printBinaryMaze(inBM)
            return SOLVED

    # hier zouden we niet moeten komen...
    print "SHOULD NOT HAPPEN"
    return SHOULD_NOT_HAPPEN




# het voorlopige 'main' programma

print("Hello Sokoba_solv World!") # ff goeiesmorgens zegge

# test levels van David W. Skinner
# ( http://users.bentonrea.com/~sasquatch/sokoban/ )

# level 1, Microban II
theTM = ['####',
         '#  #',
         '#  #',
         '#  ###',
         '#.$$@#',
         '#  . #',
         '#  ###',
         '####'    ]


# level 2, Microban II
theTM = [' #####',
         ' #   #',
         '##.# #',
         '#  @ #',
         '#  $ #',
         '# #*##',
         '#   #',
         '#####'   ]


# level 3, Microban II
theTM = ['   ####',
         '####  #',
         '#  #  #',
         '# . . #',
         '# @$$ #',
         '# # ###',
         '#   #',
         '#####'    ]


theBM = textMazeToBinaryMaze(theTM)

printLegend()

beenThereDoneThat = []
solveMaze(theBM, 1)