# -*- coding: utf-8 -*-
"""
Created on Sun Sep 15 11:39:20 2019

@author: HERAMB
"""
from math import sqrt
import timeit
#import resource
from collections import deque
from state import State
from heapq import heappush, heappop, heapify
import itertools

#goal_state = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,0]
goal_state = [1,2,3,4,5,6,7,8,0]
goal_node = State
initial_state = list()
board_len = 0
board_side = 0

nodes_expanded = 0
max_search_depth = 0
max_frontier_size = 0

moves = list()
costs = set()


def bfs(start_state):

    global max_frontier_size, goal_node, max_search_depth

    explored, queue = set(), deque([State(start_state, None, None, 0, 0, 0)])

    while queue:

        node = queue.popleft()
        explored.add(node.map)

        if node.state == goal_state:
            goal_node = node
            return True, queue

        neighbors = expand(node)

        for neighbor in neighbors:
            if neighbor.map not in explored:
                queue.append(neighbor)
                explored.add(neighbor.map)

                if neighbor.depth > max_search_depth:
                    max_search_depth += 1

        if len(queue) > max_frontier_size:
            max_frontier_size = len(queue)
    
    return False, None    

def dfs(start_state):

    global max_frontier_size, goal_node, max_search_depth

    explored, stack = set(), list([State(start_state, None, None, 0, 0, 0)])

    while stack:

        node = stack.pop()

        explored.add(node.map)

        if node.state == goal_state:
            goal_node = node
            return True,stack

        neighbors = reversed(expand(node))

        for neighbor in neighbors:
            if neighbor.map not in explored:
                stack.append(neighbor)
                explored.add(neighbor.map)

                if neighbor.depth > max_search_depth:
                    max_search_depth += 1

        if len(stack) > max_frontier_size:
            max_frontier_size = len(stack)

    return False, None

def ast(start_state):

    global max_frontier_size, goal_node, max_search_depth

    explored, heap, heap_entry, counter = set(), list(), {}, itertools.count()

    key = h(start_state)

    root = State(start_state, None, None, 0, 0, key)

    entry = (key, 0, root)

    heappush(heap, entry)

    heap_entry[root.map] = entry

    while heap:

        node = heappop(heap)
        #print(node)
        explored.add(node[2].map)

        if node[2].state == goal_state:
            goal_node = node[2]
            return True, heap

        neighbors = expand(node[2])

        for neighbor in neighbors:

            neighbor.key = neighbor.cost + h(neighbor.state)

            entry = (neighbor.key, neighbor.move, neighbor)

            if neighbor.map not in explored:

                heappush(heap, entry)

                explored.add(neighbor.map)

                heap_entry[neighbor.map] = entry

                if neighbor.depth > max_search_depth:
                    max_search_depth += 1

            elif neighbor.map in heap_entry and neighbor.key < heap_entry[neighbor.map][2].key:

                hindex = heap.index((heap_entry[neighbor.map][2].key,
                                     heap_entry[neighbor.map][2].move,
                                     heap_entry[neighbor.map][2]))

                heap[int(hindex)] = entry

                heap_entry[neighbor.map] = entry

                heapify(heap)

        if len(heap) > max_frontier_size:
            max_frontier_size = len(heap)
    return False, None

"""

"""
def greedy(start_state, heuristicFunc):
    global max_frontier_size, goal_node, max_search_depth
    
    explored, pQueue = set(), list()

    key = heuristicFunc(start_state)
    
    root = State(start_state, None, None, 0, 0, key)

    entry = (key, 0, root)

    heappush(pQueue, entry)

    while pQueue:

        node = heappop(pQueue)
        #print(node)
        explored.add(node[2].map)

        if node[2].state == goal_state:
            goal_node = node[2]
            return True, pQueue

        neighbors = expand(node[2])

        for neighbor in neighbors:

            neighbor.key = heuristicFunc(neighbor.state)

            entry = (neighbor.key, neighbor.move, neighbor)

            if neighbor.map not in explored:

                heappush(pQueue, entry)

                explored.add(neighbor.map)

                if neighbor.depth > max_search_depth:
                    max_search_depth += 1

            """
            elif neighbor.map in heap_entry and neighbor.key < heap_entry[neighbor.map][2].key:

                hindex = heap.index((heap_entry[neighbor.map][2].key,
                                     heap_entry[neighbor.map][2].move,
                                     heap_entry[neighbor.map][2]))

                heap[int(hindex)] = entry

                heap_entry[neighbor.map] = entry

                heapify(heap)
            """
        if len(pQueue) > max_frontier_size:
            max_frontier_size = len(pQueue)
    return False, None
    """
    root = State(start_state, None, None, 0, 0, key)
    entry = (key, 0, root)
    heappush(pQueue, entry)
    while pQueue : 
        popped = heappop(pQueue)
        print('node --',popped)
        node = popped[2]
        print('node updated -- ',node.state)
        explored.add(node.map)
        
        if node.state == goal_state:
            goal_node = node
            return True, pQueue

        neighbors = expand(node)
        for neighbor in neighbors:
            neighbor.key = h(neighbor.state)
            entry = (neighbor.key, neighbor.move, neighbor)
            if neighbor.map not in explored:
                heappush(pQueue, entry)
                pQueue.append(neighbor)
                explored.add(neighbor.map)

                if neighbor.depth > max_search_depth:
                    max_search_depth += 1

        if len(pQueue) > max_frontier_size:
            max_frontier_size = len(pQueue)

    return False, None
    """
    

def ida(start_state):

    global costs

    threshold = h(start_state)

    while 1:
        response = dls_mod(start_state, threshold)

        if type(response) is list:
            return response
            break

        threshold = response

        costs = set()


def dls_mod(start_state, threshold):

    global max_frontier_size, goal_node, max_search_depth, costs

    explored, stack = set(), list([State(start_state, None, None, 0, 0, threshold)])

    while stack:

        node = stack.pop()

        explored.add(node.map)

        if node.state == goal_state:
            goal_node = node
            return stack

        if node.key > threshold:
            costs.add(node.key)

        if node.depth < threshold:

            neighbors = reversed(expand(node))

            for neighbor in neighbors:
                if neighbor.map not in explored:

                    neighbor.key = neighbor.cost + h(neighbor.state)
                    stack.append(neighbor)
                    explored.add(neighbor.map)

                    if neighbor.depth > max_search_depth:
                        max_search_depth += 1

            if len(stack) > max_frontier_size:
                max_frontier_size = len(stack)

    return min(costs)


def expand(node):

    global nodes_expanded
    nodes_expanded += 1

    neighbors = list()

    neighbors.append(State(move(node.state, 1), node, 1, node.depth + 1, node.cost + 1, 0))
    neighbors.append(State(move(node.state, 2), node, 2, node.depth + 1, node.cost + 1, 0))
    neighbors.append(State(move(node.state, 3), node, 3, node.depth + 1, node.cost + 1, 0))
    neighbors.append(State(move(node.state, 4), node, 4, node.depth + 1, node.cost + 1, 0))

    nodes = [neighbor for neighbor in neighbors if neighbor.state]

    return nodes


def move(state, position):

    new_state = state[:]

    index = new_state.index(0) #--- get the position of blank tile

    if position == 1:  # Up

        if index not in range(0, board_side):

            temp = new_state[index - board_side]
            new_state[index - board_side] = new_state[index]
            new_state[index] = temp

            return new_state
        else:
            return None

    if position == 2:  # Down

        if index not in range(board_len - board_side, board_len):

            temp = new_state[index + board_side]
            new_state[index + board_side] = new_state[index]
            new_state[index] = temp

            return new_state
        else:
            return None

    if position == 3:  # Left

        if index not in range(0, board_len, board_side):

            temp = new_state[index - 1]
            new_state[index - 1] = new_state[index]
            new_state[index] = temp

            return new_state
        else:
            return None

    if position == 4:  # Right

        if index not in range(board_side - 1, board_len, board_side):

            temp = new_state[index + 1]
            new_state[index + 1] = new_state[index]
            new_state[index] = temp

            return new_state
        else:
            return None


def h(state):

    return sum(abs(b % board_side - g % board_side) + abs(b//board_side - g//board_side)
               for b, g in ((state.index(i), goal_state.index(i)) for i in range(1, board_len)))


def h1(state):
    count = 0
    for i in range(0,board_len):
        if not (state.index(i) == goal_state.index(i)) : 
            count+=1
    return count 

def h2(state): 
    return sum(abs(p%board_side - g%board_side) + abs(p//board_side - g//board_side)
               for p,g in ((state.index(i),goal_state.index(i)) 
               for i in range(1, board_len)))

def backtrace():

    current_node = goal_node

    while initial_state != current_node.state:

        if current_node.move == 1:
            movement = 'Up'
        elif current_node.move == 2:
            movement = 'Down'
        elif current_node.move == 3:
            movement = 'Left'
        else:
            movement = 'Right'

        moves.insert(0, movement)
        current_node = current_node.parent

    return moves


def export(frontier, time):
    
    if frontier : 
        
        global moves
    
        moves = backtrace()
    
        file = open('output_solvable.txt', 'w')
        file.write("<-- # SOLVABLE # -->")
        file.write("path_to_goal: " + str(moves))
        file.write("\ncost_of_path: " + str(len(moves)))
        file.write("\nnodes_expanded: " + str(nodes_expanded))
        file.write("\nfringe_size: " + str(len(frontier)))
        file.write("\nmax_fringe_size: " + str(max_frontier_size))
        file.write("\nsearch_depth: " + str(goal_node.depth))
        file.write("\nmax_search_depth: " + str(max_search_depth))
        file.write("\nrunning_time: " + format(time, '.8f'))
        file.close()
    else : 
        file = open('output_unsolvable.txt', 'w')
        file.write("<-- # UNSOLVABLE # -->")
        file.write("\nnodes_expanded: " + str(nodes_expanded))
        file.write("\nmax_fringe_size: " + str(max_frontier_size))
        file.write("\nmax_search_depth: " + str(max_search_depth))
        file.write("\nrunning_time: " + format(time, '.8f'))
        file.close()

def read(configuration):

    global board_len, board_side

    data = configuration.split(",")

    for element in data:
        initial_state.append(int(element))

    board_len = len(initial_state)

    board_side = int(board_len ** 0.5)

def get(dataList):
    global board_len, board_side
    
    data = dataList.split(',') 
    for element in data:
        initial_state.append(int(element))
    board_len = len(data)                   #--- get the length f puzzle
    board_side = int(sqrt(board_len))       #--- calculate square root in order to get the length of puzzle size


def main():
    """
    parser = argparse.ArgumentParser()

    parser.add_argument('algorithm')
    parser.add_argument('board')
    args = parser.parse_args()

    read(args.board)
    """
    algorithm = input('--> Please select the algorithm \
                      \n1. bfs : Breadth First Search \
                      \n2. dfs : Depth First Search \
                      \n3. ast : A Star Search\
                      \n4. ida : Iterative Deepening\
                      \n5. greedy : Greedy Search\
                      \n enter the Selection : ')
    
    data = input('--> Enter puzzle elements : ')
    
    get(data)

    function = function_map[algorithm]
    
    # if greedy ask for whiich heuristic they are opting for
    if(algorithm == 'greedy' | algorithm == 'ast'):
        heuristic = input('-- Please select the Heuristic Function\
                      \n h1 : number of misplaced tiles\
                      \n h2 : sum of the distances of every tile to its goal position.\
                      \n-- Enter your choice : ')
    
        heuristicFunc = heuristic_map[heuristic]
        
        start = timeit.default_timer()
        
        search, frontier = function(initial_state, heuristicFunc)
    else :
        start = timeit.default_timer()

        search, frontier = function(initial_state)
        

    stop = timeit.default_timer()

    if not search : 
        print('<-- # UNSOLVABLE # -->')
        export(frontier, stop-start)
    else : 
        export(frontier, stop-start)


function_map = {
    'bfs': bfs,
    'dfs': dfs,
    'ast': ast,
    'ida': ida,
    'greedy' : greedy
}

heuristic_map = {
        'h1' : h1,
        'h2' : h2
        }

if __name__ == '__main__':
    main()