[HaBo]

#!/usr/bin/python
import time
import sys
sokofield = []
f = open(sys.argv[1])
for line in f:
    l = []
    for c in line[:-1]:
        l.append(c)
    sokofield.append(l)
f.close()

def printField(field):
    for line in field:
        for cell in line:
            print(cell, sep="", end="")
        print()

'''def isWalkable(field, x, y):
    if y < len(field) and x < len(field[0]) and field[y][x] != '#':
        return True
    else:
        return False'''
    
def isFree(field, x, y):
    if y < len(field) and x < len(field[0]) and (field[y][x] == ' ' or field[y][x] == '.' or field[y][x] == '@'):
        return True
    else:
        return False

def isWallFree(field, x, y):
    if y < len(field) and x < len(field[0]) and (field[y][x] == ' ' or field[y][x] == '.' or field[y][x] == '@' or field[y][x] == '$'):
        return True
    else:
        return False

def isTarget(field, x, y):
    if y < len(field) and x < len(field[0]) and field[y][x] == '.':
        return True
    else:
        return False
        
def getValidPos(field, lastPos):
    validPos = []
    for y in range(len(field)):
        for x in range(len(field[y])):
            cell = field[y][x]
            if cell == '$':
                if isFree(field, x, y-1) and isFree(field, x, y+1):
                    if isTarget(field, x, y+1) or not isBlocked(field, x, y+1):
                        validPos.append(((x, y-1), (x, y)))
                    if isTarget(field, x, y-1) or not isBlocked(field, x, y-1):
                        validPos.append(((x, y+1), (x, y)))
                if isFree(field, x-1, y) and isFree(field, x+1, y):
                    if isTarget(field, x+1, y) or not isBlocked(field, x+1, y):
                        validPos.append(((x-1, y), (x, y)))
                    if isTarget(field, x-1, y) or not isBlocked(field, x-1, y):
                        validPos.append(((x+1, y), (x, y)))
    return validPos

def isBlocked(field, x, y):
    return False
    if ((isWallFree(field, x-1, y) and isWallFree(field, x+1, y)) or
        (isWallFree(field, x, y-1) and isWallFree(field, x, y+1))):
        print(x, y, "free")
        return False
    else:
        print(x, y, "not free")
        return True

def getNeighbors(field, x, y):
    nb = []
    if isFree(field, x-1, y):
        nb.append((x-1, y))
    if isFree(field, x, y-1):
        nb.append((x, y-1))
    if isFree(field, x+1, y):
        nb.append((x+1, y))
    if isFree(field, x, y+1):
        nb.append((x, y+1))
    return nb

def aStar(field, startPos, targetPos):
    openlist = [startPos]
    ratings = {startPos: 0}
    pre = {startPos: None}
    closedlist = []
    while len(openlist) > 0:
        b = dict(map(lambda item: (item[1],item[0]),ratings.items()))
        currentNode = b[min(b.keys())]
        currentRating = ratings[currentNode]
        openlist.remove(currentNode)
        ratings.pop(currentNode)
        if (currentNode == targetPos):
            break
        for nb in getNeighbors(field, currentNode[0], currentNode[1]):
            if nb in closedlist:
                continue
            f = currentRating + abs(currentNode[0] - nb[0]) + abs(currentNode[1] - nb[1])
            if nb in openlist:
                if ratings[nb] <= f:
                    continue
            else:
                openlist.append(nb)
            ratings[nb] = f
            pre[nb] = currentNode
        closedlist.append(currentNode)
        
    currentNode = targetPos
    path = [currentNode]
    try:
        while (currentNode != startPos):
            currentNode = pre[currentNode]
            path.append(currentNode)
        path.reverse()
        return path
    except KeyError:
        return None

def doMove(myField, f, t):
    (x, y) = f
    (nx, ny) = t
    if (sokofield[y][x] != '@' and sokofield[y][x] != '$'):
        myField[y][x] = sokofield[y][x]
    else:
        myField[y][x] = ' '
    if (myField[ny][nx] == '$'):
        myField[ny + (ny - y)][nx + (nx - x)] = '$'
    myField[ny][nx] = '@'
    return myField

def getPlayerPos(field):
    for y in range(len(field)):
        for x in range(len(field[y])):
            cell = field[y][x]
            if (cell == '@'):
                return (x, y)
    return None

def getNumTargets(field):
    numTargets = 0 
    for y in range(len(field)):
        for x in range(len(field[y])):
            cell = field[y][x]
            if (cell == '.'):
                numTargets += 1
            elif (cell == '@' and sokofield[y][x] == '.'):
                numTargets += 1
    return numTargets
    
def positionsToPath(pos):
    path = ''
    for i in range(len(pos)-1):
        (fx, fy) = pos[i]
        (tx, ty) = pos[i+1]
        if (tx < fx): path += 'l'
        elif (tx > fx): path += 'r'
        elif (ty < fy): path += 'u'
        elif (ty > fy): path += 'd'
    return path

def breitensuche(field):
    moves = [(0, getPlayerPos(field), field, [])]
    minMoves = 0
    while (len(moves) > 0):
        minMove = min(moves)
        moves.remove(minMove)
        if minMove[0] > minMoves:
            print("Kein Weg unter %s Schritten" % minMove[0])
            minMoves = minMove[0]
        #print(minMove[0], minMove[3])
        #printField(minMove[2])
        if getNumTargets(minMove[2]) == 0:
            print("Loesung gefunden:")
            printField(minMove[2])
            print("Weg:", positionsToPath(minMove[3]))
            break

        pos = getValidPos(minMove[2], 0)
        for pt in pos:
            (p, t) = pt
            #print(p)
            path = aStar(minMove[2], minMove[1], p)
            if (path == None): continue
            path.append(t)
            myField = [[a for a in b] for b in minMove[2]]
            for pid in range(len(path)-1):
                myField = doMove(myField, path[pid], path[pid+1])
            newMove = (minMove[0] + len(path), t, myField, minMove[3] + path)
            #print(newMove)
            #printField(myField)
            #printField(minMove[2])
            moves.append(newMove)
        #time.sleep(1)
            
print("Ausgangslage:")
printField(sokofield)
print("Suche Loesung...")
breitensuche(sokofield)

Ausgangslage:
########
#  #.  #
# $#   #
#  # @##
#  # $##
#    .##
########
Suche Loesung...
Kein Weg unter 2 Schritten
Kein Weg unter 6 Schritten
Kein Weg unter 8 Schritten
Kein Weg unter 9 Schritten
[...]
Kein Weg unter 40 Schritten
Loesung gefunden:
########
#  #$@ #
#  #   #
#  #  ##
#  #  ##
#    $##
########
Weg: lddrudllluuluurdddldrrruruurul