#!/usr/bin/env python2.7

from board import Board

import numpy as np
from Queue import PriorityQueue
import sys

sys.setrecursionlimit(10000)

def solve_A_star(board):
    '''solve_A_star(board) -> list of solution moves
    applies a non recursive variant of the A* algorithm'''
    # setup
    opposite_move = {'UP': 'DOWN', 'DOWN': 'UP',
                     'LEFT': 'RIGHT', 'RIGHT': 'LEFT', None: None}
    depth = 0
    preds = {} # mapping of board configuration to move that leads to previous board
    PQ = PriorityQueue()
    PQ_item = (None, (depth, None, board))
    PQ.put(PQ_item)

    # explore boards
    while not PQ.empty():
        # evaluate next board in PQ
        h_plus_depth, (depth, from_move, board) = PQ.get()
        configuration = board.to_tuple_repr()
        if configuration in preds:
            continue

        preds[configuration] = opposite_move[from_move]
        if board.is_solved():
            break

        # add children of board to PQ
        for from_move, result in board.possible_next_boards():
            new_depth = depth + 1
            h = result.heuristic()
            PQ_item = (h + new_depth, (new_depth, from_move, result))
            PQ.put(PQ_item)
    else:
       # executes if while loop did not break, i.e. PQ is empty -> no solution
       return None

    # construct list of moves to backtrack from solved to initial board
    solved_to_initial = []
    move = preds[configuration]

    while move is not None:
        solved_to_initial.append(move)
        prev_board = Board.from_tuple_repr(configuration)
        prev_board.apply_move(move)
        configuration = prev_board.to_tuple_repr()
        move = preds[configuration]

    # construct solution:
    return [opposite_move[move] for move in reversed(solved_to_initial)]

def solve_IDS(board, prints=False):
    '''solve_IDS(board) -> list of solution moves
    applies iterative deepening search by calling solve_DFS iteratively with
    increasing max_depth values; expects solvable board

    will find a good solution but can take very long if the
    solution is at a high depth'''
    solution = None
    max_depth = 0

    while solution is None:
        if prints:
            print 'max_depth={}'.format(max_depth)

        solution = solve_DFS(board, max_depth)
        max_depth += 1

    return solution

def solve_DFS(board, max_depth=float('inf'), depth=0, seen=None):
    '''solve_DFS(board) -> list of solution moves
    applies DFS, childs are chosen heuristically

    tends to find long solutions to relatively simple boards and can take very
    long -> use solve_IDS for shorter solutions

    do not touch the default arguments when calling directly, use solve_IDS to
    apply iterative deepening search!'''
    if seen is None:
        seen = set()

    # simple case
    if board.is_solved():
        return []

    # used to abort when in IDS mode (called via solve_IDS)
    # with max_depth < infinity
    if depth == max_depth:
        return None

    # construct copy of seen with the current board added
    seen = seen | {board.to_tuple_repr()}

    # put (move, result board) tuples into priority queue
    PQ = PriorityQueue()

    for move, result in board.possible_next_boards():
        result_config = result.to_tuple_repr()
        if result_config not in seen:
            h = result.heuristic()
            PQ_item = (h, (move, result))
            PQ.put(PQ_item)

    # try moves in order of their position in the PQ
    while not PQ.empty():
        h, (move, result) = PQ.get()
        sub_solution = solve_DFS(result, max_depth, depth + 1, seen)

        if sub_solution is not None:
            return [move] + sub_solution

    return None

# the two hardest boards to play around with (use solve_A_star for these)
hardest1 = Board(np.array([[8, 6, 7], [2, 5, 4], [3, 9, 1]]))
hardest2 = Board(np.array([[6, 4, 7], [8, 5, 9], [3, 2, 1]]))

# DEMO SECTION
if __name__ == '__main__':
    strategies = [('solve_IDS', solve_IDS), ('solve_A_star', solve_A_star)]
    TESTS = 20
    boards = [Board.random_solvable_board(num_moves) for num_moves in xrange(TESTS)]

    for strategy_name, strategy in strategies:
        print '\n---------- TESTING STRATEGY {} ----------\n'.format(strategy_name)

        # generate copy of boards (to later apply the solutions)
        to_solve = [board.copy() for board in boards]

        # generate solutions
        solutions = [strategy(board) for board in boards]

        # apply solutions
        for solution, board in zip(solutions, to_solve):
            board.apply_moves(solution)

        # are all boards solved?
        success = all(board.is_solved() for board in to_solve)
        if success:
            print 'success! all test cases solved!\n'
            solution, board = max(zip(solutions, boards),
                                  key=lambda (solution, board): len(solution))
            print 'longest solution has {} moves:\n{}\n'.format(len(solution), solution)
            print 'and solves the board:\n{}'.format(board)
        else:
            print 'oh no! /o\\'