'''
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...

btw.: ik maak van de source vrolijke html met de volgende toverspreuk:
      pygmentize -f html -O full -o sokoban_solv_01.html sokoban_solv.py

'''

# mijn imports...
import numpy as np    # uiteraard, want zonder... , dus...
import shlex          # voor shlex.split
from copy import copy, deepcopy

import sys
import cProfile
import pstats


# 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

def fancyHtmlOutput(inMoveList):
    '''
    Maak een fancy HTML file van een oplossing.
    Kan later nog luxer nu doen we een text maze met het laatste
    verplaatste box in bold (blink mag niet meer schijnt het...)
    '''
    global startBM, numberOfSolutions

    myBM = startBM.copy() # we trekken een kopie
    heigth, width = myBM.shape

    omzet = { FLOOR          : ' ',
              WALL           : '#',
              PLAYER         : '<font color="red">@</font>',
              BOX            : '$',
              GOAL           : '.',
              PLAYER | GOAL  : '<font color="red">+</font>',
              BOX | GOAL     : '*' }

    numberOfSolutions += 1
    fileName = 'sol_%d_%d.html' % (numberOfSolutions, len(inMoveList))

    print "Wrote solution file %d : %s" % (numberOfSolutions, fileName)

    f = open(fileName, 'w')
    f.write('<html><head></head><body text="grey"><pre>')

    for move in (inMoveList):
        myBM = applyMove(myBM, move)
        lastBox = movedPosition(move['pos'], move['dir'])
        for i in range(heigth):
            for j in range(width):
                if lastBox == (i,j) : f.write('<font color="black"><b>')
                f.write(omzet[myBM[i,j] & (WALL | BOX | GOAL | PLAYER)])
                if lastBox == (i,j) : f.write('</b></font>')
            f.write('<br>')
        f.write('<br>')

    f.write('</pre></body><html>')
    f.close()


    


def loadMazeFromFile(inFile, inLevel = 1):
    '''
    Laad een level uit een standaard(?) sokoban file
    (vind het een stom file formaat maar vooruit....)

    deze functie 'slikt' de levels van David W. Skinner
    ( http://users.bentonrea.com/~sasquatch/sokoban/ )

    '''
    f = open(inFile, 'r')
    whole = f.read(9999999999L)
    f.close()
    levels = whole.split(';')[1:]
    for level in levels:
        bah = level.split('\r\r')
        if int(bah[0])==inLevel:
            return bah[1].split('\r')
    return False

# 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 = None):
    '''
    Vind alle mogelijke posities beginnende bij inPos zonder
    boxes te verplaatsen. Als inPos niet gegeven is beginnen
    we bij de player positie.
    (we gaan er van uit dat de maze 'netjes' is afgebakend)
    (pas op: orginele inkomende maze wordt ook veranderdt)
    '''
    myBM = inBM.copy() # We trekken een kopie.

    # Als er geen inPos gegeven is starten we bij de player.
    if inPos == None:
        myBM = unsetPossiblePlayerPos(myBM) # voor de zekerheid
        inPos = findPlayer(myBM)

    # Zet het begin punt.
    myBM[inPos] |= POSSIBLE

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

    return myBM

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, preferredFirst = None):
    '''
    vind de mogelijke verplaatsing van boxes en geef een
    lijst terug van box posities met mogelijke verplaats
    richtingen.
    Indien gewenst wordt een bepaald blok vooraan in de lijst
    gezet (schijnt beter te zijn...).
    '''
    myBM = inBM.copy() # we trekken een kopie

    myBM = setPossiblePlayerPos(myBM)

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

    # Handle 'preferredFirst', eerst even stom, moet beter kunnen (met sort)
    if preferredFirst != None:
        unsorted_moves = copy(moves)
        moves = []
        for move in unsorted_moves:
            if move['pos'] == preferredFirst:
                # print 'yes', preferredFirst, move['pos']
                moves.append(move)
        for move in unsorted_moves:
            if move['pos'] != preferredFirst:
                # print 'no', preferredFirst, move['pos']
                moves.append(move)

    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 compactState(inBM):
    '''
    Maak een korte omschrijving van de 'maze state', een
    tuple met als eerste de eerst mogelijk player positie en
    vervolgend de box posities.
    '''
    myBM = inBM.copy() # we trekken een kopie

    myBM = setPossiblePlayerPos(myBM)
    firstPossiblePlayerPos = findFirstOfSomething(inBM, POSSIBLE)

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


def setBeenThereDoneThat(inBM):
    '''
    We slaan de huidige state zo compact mogelijk op.
    '''
    global beenThereDoneThat
    beenThereDoneThat.append(compactState(inBM))

def checkBeenThereDoneThat(inBM):
    '''
    Check of we deze maze situation al 'gehad' hebben.
    '''
    global beenThereDoneThat
    return compactState(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 niets meer kunnen bewegen zijn we stuk
    if not len(findMoves(inBM)): 
        return True

    # weet het eerst niet zeker...
    return False

def tooDeep(inDepth):
    '''
    Check of we al een oplossing hebben gevonden in minder stappen
    '''
    global minSolvedDepth
    return inDepth > minSolvedDepth 

def setSolvedDepth(inDepth):
    global minSolvedDepth
    if (inDepth < minSolvedDepth):
        minSolvedDepth = inDepth



# constants... solve results
SOLVED            = 1
STUCK             = 2
SHOULD_NOT_HAPPEN = 3
LESS_DEPTH_SOLVED = 4
BEEN_THERE        = 5

def solveMaze(inBM, inDepth, inMoveList = [], lastMoved = None):
    '''
    de one and only solve 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):
        fancyHtmlOutput(inMoveList)
        setSolvedDepth(inDepth)
        return SOLVED

    # moeilijke check
    if isZekerStuk(inBM):
        return STUCK

    # als we er al geweest zijn
    if checkBeenThereDoneThat(inBM):
        return BEEN_THERE

    # hebben we al een kortere oplossing...
    if tooDeep(inDepth):
        return LESS_DEPTH_SOLVED

    # sla toestand op in beenThereDoneThat
    setBeenThereDoneThat(inBM)

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

    for move in moves:
        #result = solveMaze(applyMove(inBM, move), inDepth+1)
        result = solveMaze(applyMove(inBM, move), 
                           inDepth+1,
                           copy(inMoveList) + [move],
                           movedPosition(move['pos'], move['dir']))

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

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


# my globals
beenThereDoneThat = None
minSolvedDepth    = None
startBM           = None
numberOfSolutions = None

def main(inFile, inLevel):

    global startBM, beenThereDoneThat, minSolvedDepth, numberOfSolutions;

    theTM = loadMazeFromFile(inFile, inLevel)

    theBM = textMazeToBinaryMaze(theTM)

    # set some globals
    beenThereDoneThat = []
    minSolvedDepth = 9999
    startBM = theBM.copy()
    numberOfSolutions = 0

    solveMaze(theBM, 1)

if __name__ == '__main__':

    if len(sys.argv) == 3:

        sokobanFile = str(sys.argv[1])
        level       = int(sys.argv[2])

        command = 'main(\'%s\', %d)' % (sokobanFile, level)

        cProfile.run(command, 'profile.out')

        p = pstats.Stats('profile.out')
        p.strip_dirs().sort_stats('time').print_stats()

    else:

        print '\nUsage: sokoban_solv.py sokoban_file level_no\n'