#!/usr/bin/env python2.7

import numpy as np
import random

# activate for debugging to get the same random
# numbers for every execution of the script
# random.seed(0)

class Board(object):
    '''models 3x3 sliding window game where the number 9 is the sliding component

    DEMO:

    >>> from board import Board
    >>> b = Board.random_solvable_board()
    >>> b
    1 9 2
    4 5 3
    7 8 6
    >>> b.apply_move('RIGHT')
    >>> b
    1 2 9
    4 5 3
    7 8 6
    >>> b.heuristic()
    4
    >>> for move, result in b.possible_next_boards():
    ...     print move
    ...     print result
    ...     print '---'
    ...
    DOWN
    1 2 3
    4 5 9
    7 8 6
    ---
    LEFT
    1 9 2
    4 5 3
    7 8 6
    ---
    '''

    # configuration of solved board
    solution = np.array([[1, 2, 3],
                         [4, 5, 6],
                         [7, 8, 9]])

    # map name of move to delta values for row and column
    moves = {'UP': (-1, 0),
             'DOWN': (1, 0),
             'LEFT': (0, -1),
             'RIGHT': (0, 1)}

    def __init__(self, configuration):
        '''Board(numpy array) -> Board instance

        example: my_board = Board(np.array([[2, 3, 9], [1, 5, 6], [4, 7, 8]]))'''
        self.configuration = configuration
        self.row_9, self.col_9 = np.where(self.configuration == 9)

    def __repr__(self):
        return '\n'.join(' '.join(map(str, row)) for row in self.configuration)

    def __eq__(self, other):
        return (self is other or
                np.array_equal(self.configuration, other.configuration))

    def is_solved(self):
        'return whether configuration is equal to Board.solution'
        return np.array_equal(self.configuration, Board.solution)

    def apply_move(self, move):
        'mutates the board by applying a legal move, e.g. board.move("UP")'
        delta_row, delta_col = Board.moves[move]
        swap_row, swap_col = self.row_9 + delta_row, self.col_9 + delta_col

        if swap_row < 0 or swap_col < 0 or swap_row > 2 or swap_col > 2:
            raise IndexError('illegal move, position ({}, {}) does not exist'
                              .format(int(swap_row), int(swap_col)))

        swap_val = self.configuration[swap_row, swap_col]

        self.configuration[self.row_9, self.col_9] = swap_val
        self.configuration[swap_row, swap_col] = 9

        self.row_9 = swap_row
        self.col_9 = swap_col

    def apply_moves(self, movelist):
        'applies all moves from movelist to board'
        for move in movelist:
            self.apply_move(move)

    def possible_next_boards(self):
        'yields (move, resulting board) tuples for every possible move'
        result_board = self.copy()

        for move in Board.moves:
            try:
                result_board.apply_move(move)
            except IndexError:
                continue

            yield (move, result_board)
            result_board = self.copy()

    def heuristic(self):
        '''sum of manhatten distances for each value to its target position on the board
        (lower is better)'''
        h = 0

        for row_idx, row in enumerate(self.configuration):
            for col_idx, val in enumerate(row):
                target_row_idx = (val - 1)/3 # integer division!
                target_col_idx = (val - 1)%3
                dist = abs(row_idx - target_row_idx) + abs(col_idx - target_col_idx)
                h += dist

        return h

    def copy(self):
        'returns a copy of the board'
        return Board(self.configuration.copy())

    def to_tuple_repr(self):
        '''returns immutable tuple representation of the board;
        suitable for insertion into sets or usage as dictionary keys'''
        return tuple(map(tuple, self.configuration))

    @staticmethod
    def from_tuple_repr(tuple_repr):
        '''constructs a full Board instance from tuple
        representation returned by to_tuple_repr'''
        return Board(np.array(tuple_repr))

    @staticmethod
    def random_solvable_board(num_moves=10):
        '''returns a random board that can be solved;
        num_moves is the number of random moves applied to the solved starting board'''
        moves = Board.moves.keys()
        random_board = Board(Board.solution.copy())

        for _ in xrange(num_moves):
            move = random.choice(moves)

            try:
                random_board.apply_move(move)
            except IndexError:
                pass

        return random_board