Module pacai.bin.eightpuzzle

import random

from pacai.core.search import search
from pacai.core.search.problem import SearchProblem
from pacai.util.logs import initLogging

class EightPuzzleState:
    """
    The Eight Puzzle is described in the course textbook on page 64.

    This class defines the mechanics of the puzzle itself.
    The task of recasting this puzzle as a search problem is left to
    the EightPuzzleSearchProblem class.
    """

    def __init__(self, numbers):
        """
        Constructs a new eight puzzle from an ordering of numbers.

        numbers: a list of integers from 0 to 8 representing an instance of the eight puzzle.
        0 represents the blank space.
        Thus, the list:
        [1, 0, 2, 3, 4, 5, 6, 7, 8]

        Represents the eight puzzle:
        -------------
        | 1 |   | 2 |
        -------------
        | 3 | 4 | 5 |
        -------------
        | 6 | 7 | 8 |
        ------------

        The state of the puzzle is stored in a 2-dimensional list (a list of lists) 'cells'.
        """

        self.cells = []
        numbers = numbers[:]  # Make a copy so as not to cause side-effects.
        numbers.reverse()
        for row in range(3):
            self.cells.append([])
            for col in range(3):
                self.cells[row].append(numbers.pop())
                if self.cells[row][col] == 0:
                    self.blankLocation = row, col

    def isGoal(self):
        """
        Checks to see if the puzzle is in its goal state.

        -------------
        |   | 1 | 2 |
        -------------
        | 3 | 4 | 5 |
        -------------
        | 6 | 7 | 8 |
        -------------

        >>> EightPuzzleState([0, 1, 2, 3, 4, 5, 6, 7, 8]).isGoal()
        True

        >>> EightPuzzleState([1, 0, 2, 3, 4, 5, 6, 7, 8]).isGoal()
        False
        """

        current = 0
        for row in range(3):
            for col in range(3):
                if current != self.cells[row][col]:
                    return False
                current += 1
        return True

    def legalMoves(self):
        """
            Returns a list of legal moves from the current state.

        Moves consist of moving the blank space up, down, left or right.
        These are encoded as 'up', 'down', 'left' and 'right' respectively.

        >>> EightPuzzleState([0, 1, 2, 3, 4, 5, 6, 7, 8]).legalMoves()
        ['down', 'right']
        """

        moves = []
        row, col = self.blankLocation
        if(row != 0):
            moves.append('up')

        if(row != 2):
            moves.append('down')

        if(col != 0):
            moves.append('left')

        if(col != 2):
            moves.append('right')

        return moves

    def result(self, move):
        """
        Returns a new eightPuzzle with the current state and blankLocation
        updated based on the provided move.

        The move should be a string drawn from a list returned by legalMoves.
        Illegal moves will raise an exception, which may be an array bounds
        exception.

        NOTE: This function *does not* change the current object.
        Instead, it returns a new object.
        """

        row, col = self.blankLocation
        if (move == 'up'):
            newrow = row - 1
            newcol = col
        elif (move == 'down'):
            newrow = row + 1
            newcol = col
        elif (move == 'left'):
            newrow = row
            newcol = col - 1
        elif (move == 'right'):
            newrow = row
            newcol = col + 1
        else:
            raise Exception('Illegal Move')

        # Create a copy of the current eightPuzzle
        newPuzzle = EightPuzzleState([0, 0, 0, 0, 0, 0, 0, 0, 0])
        newPuzzle.cells = [values[:] for values in self.cells]
        # And update it to reflect the move
        newPuzzle.cells[row][col] = self.cells[newrow][newcol]
        newPuzzle.cells[newrow][newcol] = self.cells[row][col]
        newPuzzle.blankLocation = newrow, newcol

        return newPuzzle

    # Utilities for comparison and display
    def __eq__(self, other):
        """
        Overloads '==' such that two eightPuzzles with the same state are equal.

        >>> EightPuzzleState([0, 1, 2, 3, 4, 5, 6, 7, 8]) == \
            EightPuzzleState([1, 0, 2, 3, 4, 5, 6, 7, 8]).result('left')
        True
        """

        for row in range(3):
            if self.cells[row] != other.cells[row]:
                return False

        return True

    def __hash__(self):
        return hash(str(self.cells))

    def __getAsciiString(self):
        """
            Returns a display string for the maze
        """

        lines = []
        horizontalLine = ('-' * (13))
        lines.append(horizontalLine)

        for row in self.cells:
            rowLine = '|'
            for col in row:
                if col == 0:
                    col = ' '
                rowLine = rowLine + ' ' + col.__str__() + ' |'
            lines.append(rowLine)
            lines.append(horizontalLine)

        return '\n'.join(lines)

    def __str__(self):
        return self.__getAsciiString()

class EightPuzzleSearchProblem(SearchProblem):
    """
    Implementation of a SearchProblem for the Eight Puzzle domain

    Each state is represented by an instance of an eightPuzzle.
    """

    def __init__(self, puzzle):
        """
        Creates a new EightPuzzleSearchProblem which stores search information.
        """

        super().__init__()

        self.puzzle = puzzle

    def startingState(self):
        return self.puzzle

    def isGoal(self, state):
        return state.isGoal()

    def successorStates(self, state):
        """
        Returns list of (successor, action, stepCost) pairs where
        each succesor is either left, right, up, or down
        from the original state and the cost is 1.0 for each
        """

        succ = []
        for a in state.legalMoves():
            succ.append((state.result(a), a, 1))
        return succ

    def actionsCost(self, actions):
        """
        actions: A list of actions to take

        This method returns the total cost of a particular sequence of actions.
        The sequence must be composed of legal moves
        """

        return len(actions)

EIGHT_PUZZLE_DATA = [
    [1, 0, 2, 3, 4, 5, 6, 7, 8],
    [1, 7, 8, 2, 3, 4, 5, 6, 0],
    [4, 3, 2, 7, 0, 5, 1, 6, 8],
    [5, 1, 3, 4, 0, 2, 6, 7, 8],
    [1, 2, 5, 7, 6, 8, 0, 4, 3],
    [0, 3, 1, 6, 8, 2, 7, 5, 4],
]

def loadEightPuzzle(puzzleNumber):
    """
    puzzleNumber: The number of the eight puzzle to load.

    Returns an eight puzzle object generated from one of the
    provided puzzles in EIGHT_PUZZLE_DATA.

    puzzleNumber can range from 0 to 5.

    >>> print(loadEightPuzzle(0))
    -------------
    | 1 |   | 2 |
    -------------
    | 3 | 4 | 5 |
    -------------
    | 6 | 7 | 8 |
    -------------
    """

    return EightPuzzleState(EIGHT_PUZZLE_DATA[puzzleNumber])

def createRandomEightPuzzle(moves = 100):
    """
    moves: number of random moves to apply

    Creates a random eight puzzle by applying
    a series of 'moves' random moves to a solved
    puzzle.
    """
    puzzle = EightPuzzleState([0, 1, 2, 3, 4, 5, 6, 7, 8])
    for i in range(moves):
        # Execute a random legal move
        puzzle = puzzle.result(random.sample(puzzle.legalMoves(), 1)[0])
    return puzzle

def main():
    """
    Entry point for the eightpuzzle simulation.
    """

    initLogging()

    puzzle = createRandomEightPuzzle(25)
    print('A random puzzle:\n' + str(puzzle))

    problem = EightPuzzleSearchProblem(puzzle)
    path = search.bfs(problem)
    print('BFS found a path of %d moves: %s' % (len(path), str(path)))
    curr = puzzle
    i = 1
    for a in path:
        curr = curr.result(a)
        print('After %d move%s: %s' % (i, ("", "s")[i > 1], a) + '\n' + str(curr))

        input('Press return for the next state...')  # wait for key stroke
        i += 1

if __name__ == '__main__':
    main()