# (c) SJSU Students 2012
# Solution to CS156 HW1 assigned by Chris Pollett
# Solves an nxm tile game
# Source of A* algorithm pseudocode: http://en.wikipedia.org/wiki/A*_algorithm

import sys
import math

gScore = []  # A list of lists where each element is [state, gscore]
hScore = []  # A list of lists where each element is [state, hscore]
fScore = []  # A list of lists where each element is [state, fVal, tieBreaker]
openList = []  # A list of the frontier states, where each state is a set
closedList = []  # A list of all explored states, where each state is a set
infinity = float('inf')
solution = []

def isNumber(label):
    # Return whether or not label is a numerical digit.
    if(label != "." and label != "#"):
        return True
    return False


def aStar(start, goal):
    # """Uses the A* algorithm to find a solution to the tile game.

    # Keyword arguments:
    # start -- the starting state or initial setup of the tile game
    # goal -- the desired goal state of the tile game

    # """

    tieBreaker = 0
    def hCost(nodeA, nodeB):
    # """Return the Manhattan distance heuristic score

    # Keyword arguments:
    # nodeA -- the current state to find the heuristic score for
    # nodeB -- the desired (goal) state to reach

    # """
        hVal = 0
        for i in range(1, j + 1):
            for tileA in nodeA:
                if(tileA[0] == str(i)):
                    xA = tileA[1]
                    yA = tileA[2]
                    break
            for tileB in nodeB:
                if(tileB[0] == str(i)):
                    xB = tileB[1]
                    yB = tileB[2]
                    break
            h = math.fabs(xB - xA) + math.fabs(yB - yA)
            hVal += h
        return hVal

    def getFval(aNode):
        # Return the f-value of the state aNode.
        return lookUpScore(gScore, aNode) + lookUpScore(hScore, aNode)

    def lookUpScore(aList, aNode):
        # Look up the score of aNode in the score list aList and return it.
        for node in aList:
            if(node[0] == aNode):
                return node[1]  # Return the corresponding score
        return 0

    def getNext():
        # Return the next frontier node in openList.
        fMin = infinity
        tieVal = 0
        for node in openList:
            for fItem in fScore:
                if(node == fItem[0]):
                    if(fItem[1] < fMin):
                        fMin = fItem[1]
                        next = node
                        tieVal = fItem[2]
                        break
                    if(fItem[1] == fMin):
                        if(fItem[2] < tieVal):
                            next = node
                            break
        return next

    def drawPuzzle(aNode):
    # Format the "tiles" of aNode in a puzzle board-like layout.
        printMe = []
        for i in range(1,maxRow + 1):
            for j in range(1, maxCol + 1):
                for tile in aNode:
                    if(tile[1] == i and tile[2] == j):
                        printMe.append(tile[0])
                        if(j == maxCol):
                            printMe.append("\n")
        solution.append(printMe)

    def printSolution(sucList, currentNode):
    # """Output the sequence of states from the start state to the goal state.

    # Keyword arguments:
    # sucList -- the list of parent-child states pairs that have been explored
    # currentNode -- the child state to find the parent of

    # """
        isSet = False
        try:
            ind = [s[0] for s in sucList].index(currentNode)
            nextNode = sucList[ind][1]
            isSet = True
        except ValueError:
            isSet = False
        if(isSet):
            drawPuzzle(currentNode)
            printSolution(sucList, nextNode)
        else:
            drawPuzzle(currentNode)

    def getSuccessors(current):
        # """Return the successors of the current state being expanded."""

        def getNeighborPos(x, y):
            res = []
            if(x - 1 != 0):
                res.append((x - 1, y))
            if(x + 1 <= maxRow):
                res.append((x + 1, y))
            if(y - 1 != 0):
                res.append((x, y - 1))
            if(y + 1 <= maxCol):
                res.append((x, y + 1))
            return res

        def newSuccessor(neighborTile, blankPos):
        # """Construct a successor state and return it.

        # Keyword arguments:
        # neighborTile -- the tile next to the tile located in blankPos
        # blankPos -- the (x, y) location of the current blank tile

        # """
            res = set(current)
            rX = 0
            rY = 0
            for r in res:
                if(r[0] == neighborTile[0]):
                    rX = r[1]
                    rY = r[2]
                    res.remove(r)
                    break
            for q in res:
                if(q[1] == blankPos[0] and q[2] == blankPos[1]):
                    res.remove(q)
                    break
            rTemp = (r[0], blankPos[0], blankPos[1])
            qTemp = (".", rX, rY)
            res.update([rTemp, qTemp])
            return res
        blankTiles = []
        result = []
        for c in current:
            if(c[0] == "."):
                blankTiles.append(c)
        neighborPos = []  # A list of neighboring tiles' positions
        for b in blankTiles:
            x = b[1]
            y = b[2]
            neighborPos = getNeighborPos(x,y)
            for n in neighborPos:
                for c in current:
                    if(c[1:] == n):
                        neighbor = c  # A neighbor tile is found
                        break
                if(isNumber(neighbor[0])):
                    result.append(newSuccessor(neighbor, [x, y]))
        return result

    openList.append(start)
    cameFrom = []  # A list of tuples (y,x) where y is the successor node of x
    gScore.append([start, 0])
    hScore.append([start, hCost(start, goal)])
    fScore.append([start, getFval(start), tieBreaker])
    tieBreaker += 1
    while openList:
        current = getNext()
        if(current == goal):
            depth = 0
            drawPuzzle(current)
            try:
                ind = [a[0] for a in cameFrom].index(goal)
                aNode = cameFrom[ind][1]
                printSolution(cameFrom, aNode)
            except ValueError:
                print 0
            while solution:
                depth += 1
                item = solution.pop()
                for a in item:
                    print a,
                print
            return ""
        openList.remove(current)
        closedList.append(current)
        successors = getSuccessors(current)
        for s in successors:
            if(s in closedList):
                continue
            gScoreTemp = lookUpScore(gScore, s) + 1
            if(s not in openList):
                openList.append(s)
                hScore.append([s, hCost(s, goal)])
                currentPathIsBetter = True
            elif(gScoreTemp < lookUpScore(gScore, s)):
                currentPathIsBetter = True
            else:
                currentPathIsBetter = False
            if(currentPathIsBetter):
                try:  # Update cameFrom
                    ind = [a[0] for a in cameFrom].index(s)
                    removeMe = (s,cameFrom[ind][1])
                    cameFrom.remove(removeMe)
                    cameFrom.append((s,current))
                except ValueError:
                    cameFrom.append((s, current))
                try:  # Update gScore
                    ind = [b[0] for b in gScore].index(s)
                    removeMe = [s,gScore[ind][1]]
                    gScore.remove(removeMe)
                    gScore.append([s,gScoreTemp])
                except ValueError:
                    gScore.append([s, gScoreTemp])
                try:  # Update fScore
                    ind = [c[0] for c in fScore].index(s)
                    removeMe = [s,fScore[ind][1],fScore[ind][2]]
                    fScore.remove(removeMe)
                    fScore.append([s, getFval(s), tieBreaker])
                except ValueError:
                    fScore.append([s, getFval(s), tieBreaker])
                tieBreaker += 1
    return "No solution"

# Read in the file name and retrieve the file
if(len(sys.argv)) != 2:
    print "Please supply a filename"
    raise SystemExit(1)
filename = sys.argv[1]
f = open(filename)
line = f.readline()
m = len(line)-1
row = 1
col=1
j = 0  # The amount of numbered tiles in the puzzle board
nonmovable = []  # Store the nonmovable tiles' positions

# Construct the start state
start = set()
while line:
    col = 1
    while col <= m:
        j += 1
        label = line[col-1]
        if(not isNumber(label)):
            j -= 1
        if(label == "#"):
            nonmovable.append((row, col))
        start.add((label, row, col))
        col+=1
    line = f.readline()
    row += 1
f.close()

maxRow = row - 1
maxCol = m
row = 1
col = 1
index = 0

#Construct the goal state
goal = set()
num = 1
for row in range(1, maxRow+1):
    for col in range (1, maxCol+1):
        #Construct numbered tiles
        if(num <= j):
            goal.add((str(num), row, col))
            num += 1
        #Construct nonmovable tiles if applicable
        elif(index < len(nonmovable) and nonmovable[index] == (row, col)):
            goal.add(("#", row, col))
            index += 1
        #Construct blank tiles
        else:
            goal.add((".", row, col))

test = aStar(start,goal)
if(test != ""):
    print test