import argparse as ap

import re

import platform

import numpy as np


######## RUNNING THE CODE ####################################################

#   You can run this code from terminal by executing the following command

#   python a*algorithm.py <INPUT/input#.txt> <OUTPUT/output#.txt> <flag>

#   for example: python a*algorithm.py INPUT/input2.txt OUTPUT/output2.txt 3

#   NOTE: THIS IS JUST ONE EXAMPLE INPUT DATA

###############################################################################





################## YOUR CODE GOES HERE ########################################

#Basic logic was derived from here
#https://www.raywenderlich.com/3016-introduction-to-a-pathfinding
#https://www.analytics-link.com/post/2018/09/14/applying-the-a-path-finding-algorithm-in-python-part-1-2d-square-grid
#https://www.geeksforgeeks.org/a-search-algorithm/

class Node:

    def __init__(self, nodeid, pos, dir):

        self.id = nodeid
        self.position = pos
        self.direction = dir
        self.number = 0
        self.g = 0
        self.h = 0
        self.f = 0
        self.child = []
        self.parent = None

    def __eq__(self, other):
        return self.position == other.position

#main heuristic function
def heuristic1(a, b):

    x = np.sqrt((b[0] - a[0]) ** 2 + (b[1] - a[1]) ** 2)
    return x

#heuristic function for tie break
def heuristic2(a, b):

    x = max ( abs(b[0] - a[0]), abs(a[0] - b[0]) )
    return x
#function display the final output
def final_output(current,array,start,goal):

    if current is None:
        return ""

    array2 = array.copy()

    #add star in the postion moved
    if current.position != start:
        array2[current.position] = '*'

    #https://stackoverflow.com/questions/103844/how-do-i-merge-a-2d-array-in-python-into-one-string-with-list-comprehension
    #print the array
    output = '\n'.join([''.join([i for i in item]) for item in array2])

    # if its a goal state, append - G at the end
    if (current.position == goal):
        array_output = output + '\n\n' + get_path(current) + '-G' + ' ' + str(current.g) + '\n\n'

    else:
        array_output = output + '\n\n' + get_path(current) + ' ' + str(current.g) + '\n\n'

    return final_output(current.parent, array,start,goal) + array_output

#function display the diagnostic output
def diagnostic_output(node, open_set, CLOSED):

    print(node.id + ':' + get_path(node), node.direction, node.number, node.g, node.h, node.f ,'\n')

    #https://stackoverflow.com/questions/103844/how-do-i-merge-a-2d-array-in-python-into-one-string-with-list-comprehension
    print('Children: {', ', '.join([(item.id + ':  ' + item.direction + ' '+ str(item.g) + ' ' + str(item.h) + ' ' + str(item.f) +  ')') for item in node.child]),'}', sep='')
    print('OPEN: {', ', '.join([('(' + str(item.id) + ':' + get_path(item) + ' ' + item.direction + ' ' + str(item.g) + ' ' + str(item.h) + ' ' + str(item.f) + ')') for item in open_set]), '}', sep='')
    print('CLOSED: {', ', '.join([('(' + str(item.id) + ':' + item.direction + ' ' + str(item.number) + ' ' + str(item.g) + ' ' + str(item.h) + ' ' + str(item.f) + ')') for item in CLOSED]),'}', '\n',sep='')

#recursive function to return the path traversed
def get_path(current):

    if current.parent is None:
        return str(current.direction)

    return get_path(current.parent) + "-" + str(current.direction)

# function to return the neighbours
def successors(current):

    directions = ['R', 'D', 'L','U','RD', 'LD', 'LU', 'RU']
    neighbors = [(0, 1), (1, 0),(0, -1), (-1, 0), (1, 1), (1, -1), (-1, -1), (-1, 1)]

    return [(tuple(x + y for x, y in zip(current.position, neighbors[i])), directions[i]) for i in range(len(directions))]



def graphsearch(map, flag):
    array = map

    open_set = []
    close_set = []

    solution = ""

    i, j = np.where(array == 'S')
    start = list(zip(i, j))[0]

    i, j = np.where(array == 'G')
    goal = list(zip(i, j))[0]

    nid_val = 0
    nid = 'N' + str(nid_val)

    #root node
    root = Node(nid, start, 'S')
    root.g = 0
    root.h = heuristic1(start, goal)
    root.f = root.g + root.h
    #appenc root to the open list
    open_set.append(root)

    curr = None
    #number is to get the number of order of expansion
    number = 1
    no_path = 0

    while len(open_set) > 0:

        minimum_f = open_set[0].f
        minimum_g = open_set[0].g
        next_node = open_set[0]

        #to pop the node from open list with mininmum cost
        for node in open_set:
            if node.f < minimum_f or node.f == minimum_f and node.g < minimum_g:
                mininum_f = node.f
                minimum_g = node.g
                next_node = node
        #curr is the node poped from open list with min cost
        curr = next_node

        open_set.remove(curr)
        close_set.append(curr)

        #neighbours include all the possible nodes nearby the current node
        neighbors = successors(curr)

        #get the dimensions of array
        numrows = int(len(array))
        numcol = int(len(array[0]))

        curr.number = number
        #return if goal is reached
        if curr.position == goal:
            output = final_output(curr, array, start, goal)
            solution = output.rstrip('\n')
            no_path = 1
            break
        valid_children = []

        #loop to find the valid neighbours out of the generated neighbours
        for item in neighbors:
            # calculation of g . G = 1 if its a diagnol else its given 2.
            gs = 1 if np.sqrt((curr.position[0] - item[0][0]) ** 2 + (curr.position[1] - item[0][1]) ** 2) > 1 else 2

            # Out of bound values
            if item[0][0] < 0 or item[0][0] >= numrows or item[0][1] < 0 or item[0][1] >= numcol:
                continue
            #Mountain encoundered
            elif array[item[0]] == 'X':
                continue
            #diagonol moved where adjacent element is a mountain
            elif ((array[(curr.position[0], item[0][1])] == 'X' or array[(item[0][0], curr.position[1])] == 'X') and ( np.sqrt((curr.position[0] - item[0][0]) ** 2 + (curr.position[1] - item[0][1]) ** 2) > 1)):
                continue

            # https://www.programiz.com/python-programming/methods/built-in/any
            elif any(node.position == item[0] and node.f < curr.g + gs + heuristic1(item[0], goal) for node in open_set):
                continue

            elif any(node.position == item[0] and node.f < curr.g + gs + heuristic1(item[0], goal) for node in close_set):
                continue
            # tie breaking case
            elif any(node.position == item[0] and node.f == curr.g + gs + heuristic1(item[0], goal) for node in open_set):
                if any(node.position == item[0] and node.f < curr.g + gs + heuristic2(item[0], goal) for node in open_set):
                    continue
            # tie breaking case
            elif any(node.position == item[0] and node.f == curr.g + gs + heuristic1(item[0], goal) for node in close_set):
                if any(node.position == item[0] and node.f < curr.g + gs + heuristic2(item[0], goal) for node in close_set):
                    continue
            #append all the valid children to the list
            valid_children.append(item)

        # loop through the valid children to create a node for each chile and add it to open set
        for item in valid_children:
            gs = 1 if np.sqrt((curr.position[0] - item[0][0]) ** 2 + (curr.position[1] - item[0][1]) ** 2) > 1 else 2
            nid_val = nid_val + 1
            nid = 'N' + str(nid_val)
            new_node = Node(nid, item[0], item[1])
            new_node.g = curr.g + gs
            new_node.h = heuristic1(item[0], goal)
            new_node.f = new_node.g + new_node.h
            curr.child.append(new_node)
            new_node.parent = curr
            open_set.append(new_node)

        #prints diagnostic output
        if (flag != 0):
            diagnostic_output(curr, open_set, close_set)
            flag = flag - 1
            number = number + 1

    # to check if there's no path returned
    if no_path == 0:
        solution = "NO-PATH"
    return solution


def read_from_file(file_name):

    # You can change the file reading function to suit the way

    # you want to parse the file

    #file_handle = open(file_name)

    #map = file_handle.readlines()
    ins = open(file_name, "r")
    data = []
    for number_strings in ins:
        number_strings = number_strings.strip()
        numbers = list(number_strings)  # Convert to integers
        #print(number_strings)
        data.append(numbers)  # Add the "row" to your list.

    flag = data.pop(0)

    array = np.array(data)
    return array





###############################################################################

########### DO NOT CHANGE ANYTHING BELOW ######################################

###############################################################################



def write_to_file(file_name, solution):

    file_handle = open(file_name, 'w')

    file_handle.write(solution)



def main():

    # create a parser object

    parser = ap.ArgumentParser()



    # specify what arguments will be coming from the terminal/commandline

    parser.add_argument("input_file_name", help="specifies the name of the input file", type=str)

    parser.add_argument("output_file_name", help="specifies the name of the output file", type=str)

    parser.add_argument("flag", help="specifies the number of steps that should be printed", type=int)

    # parser.add_argument("procedure_name", help="specifies the type of algorithm to be applied, can be D, A", type=str)





    # get all the arguments

    arguments = parser.parse_args()



##############################################################################

# these print statements are here to check if the arguments are correct.

#    print("The input_file_name is " + arguments.input_file_name)

#    print("The output_file_name is " + arguments.output_file_name)

#    print("The flag is " + str(arguments.flag))

#    print("The procedure_name is " + arguments.procedure_name)

##############################################################################



    # Extract the required arguments



    operating_system = platform.system()



    if operating_system == "Windows":

        input_file_name = arguments.input_file_name

        input_tokens = input_file_name.split("\\")

        if not re.match(r"(INPUT\\input)(\d)(.txt)", input_file_name):

            print("Error: input path should be of the format INPUT\input#.txt")

            return -1



        output_file_name = arguments.output_file_name

        output_tokens = output_file_name.split("\\")

        if not re.match(r"(OUTPUT\\output)(\d)(.txt)", output_file_name):

            print("Error: output path should be of the format OUTPUT\output#.txt")

            return -1

    else:

        input_file_name = arguments.input_file_name

        input_tokens = input_file_name.split("/")

        if not re.match(r"(INPUT/input)(\d)(.txt)", input_file_name):

            print("Error: input path should be of the format INPUT/input#.txt")

            return -1



        output_file_name = arguments.output_file_name

        output_tokens = output_file_name.split("/")

        if not re.match(r"(OUTPUT/output)(\d)(.txt)", output_file_name):

            print("Error: output path should be of the format OUTPUT/output#.txt")

            return -1



    flag = arguments.flag

    # procedure_name = arguments.procedure_name





    try:

        map = read_from_file(input_file_name) # get the map

    except FileNotFoundError:

        print("input file is not present")

        return -1

    # print(map)

    

    solution_string = "" # contains solution



    solution_string = graphsearch(map, flag)

    write_flag = 1

    

    # call function write to file only in case we have a solution

    if write_flag == 1:

        write_to_file(output_file_name, solution_string)



if __name__ == "__main__":

    main()

