from heapq import heappush, heappop
from sys import maxsize
import curses, random
import re
from serial import Serial

ser = Serial('/dev/ttyACM0',9600)


DUNGEON = """
#####################
#     #     ###   # #
#   #    #    # # # #
# #    # #   ##   # #
# ##  ##     ##  ## #
##     ### # ### ## #
#  #          #     #
####    ### ##### ###
#### ##      ###  ###
##   #####          #
#####################
"""

F, H, NUM, G, POS, OPEN, VALID, PARENT = range(8)

HEIGHT, WIDTH = 11, 21
MAX_LIMIT = HEIGHT * WIDTH
LIMIT = MAX_LIMIT // 2
DEBUG = False
COLOR = True

def astar(start_pos, neighbors, goal, start_g, cost, heuristic, limit=maxsize):


    nums = iter(range(maxsize))
    start_h = heuristic(start_pos)
    start = [start_g + start_h, start_h, next(nums), start_g, start_pos, True,
             True, None]


    nodes = {start_pos: start}
    heap = [start]
    best = start

    while heap:
        current = heappop(heap)
        current[OPEN] = False

        if goal(current[POS]):
            best = current
            break

        for neighbor_pos in neighbors(current[POS]):
            neighbor_g = current[G] + cost(current[POS], neighbor_pos)
            neighbor = nodes.get(neighbor_pos)
            if neighbor is None:
                if len(nodes) >= limit:
                    continue

                neighbor_h = heuristic(neighbor_pos)
                neighbor = [neighbor_g + neighbor_h, neighbor_h, next(nums),
                            neighbor_g, neighbor_pos, True, True, current[POS]]
                nodes[neighbor_pos] = neighbor
                heappush(heap, neighbor)
                if neighbor_h < best[H]:
                    best = neighbor

            elif neighbor_g < neighbor[G]:
                if neighbor[OPEN]:

                    neighbor[VALID] = False
                    nodes[neighbor_pos] = neighbor = neighbor[:]
                    neighbor[F] = neighbor_g + neighbor[H]
                    neighbor[NUM] = next(nums)
                    neighbor[G] = neighbor_g
                    neighbor[VALID] = True
                    neighbor[PARENT] = current[POS]
                    heappush(heap, neighbor)
                else:
                    neighbor[F] = neighbor_g + neighbor[H]
                    neighbor[G] = neighbor_g
                    neighbor[PARENT] = current[POS]
                    neighbor[OPEN] = True
                    heappush(heap, neighbor)


        while heap and not heap[0][VALID]:
            heappop(heap)

    path = []
    current = best
    while current[PARENT] is not None:
        path.append(current[POS])
        current = nodes[current[PARENT]]
    path.reverse()

    return path


class Cell(object):
    def __init__(self, char):
        self.char = char
        self.tag = 0
        self.index = 0
        self.neighbors = None


class Grid(object):

    def __init__(self, cells):
        self.height, self.width = len(cells), len(cells[0])
        self.cells = cells

    def __contains__(self, pos):
        y, x = pos
        return 0 <= y < self.height and 0 <= x < self.width

    def __getitem__(self, pos):
        y, x = pos
        return self.cells[y][x]

    def neighbors(self, y, x):
        for dy, dx in ((-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1),
                       (1, 0), (1, 1)):
            if (y + dy, x + dx) in self:
                yield y + dy, x + dx


def parse_grid(grid_str, width, height):

    # Split the grid string into lines.
    lines = [line.rstrip() for line in grid_str.splitlines()[1:]]

    # Pad the top and bottom.
    top = (height - len(lines)) // 2
    bottom = (height - len(lines) + 1) // 2
    lines = ([''] * top + lines + [''] * bottom)[:height]

    # Pad the left and right sides.
    max_len = max(len(line) for line in lines)
    left = (width - max_len) // 2
    lines = [' ' * left + line.ljust(width - left)[:width - left]
             for line in lines]

    # Create the grid.
    cells = [[Cell(char) for char in line] for line in lines]
    return Grid(cells)


class Engine(object):

    def __init__(self, grid):
        self.grid = grid
        self.y = 1
        self.x = 1
        self.goal = (10,20) #Target
        self.limit = LIMIT
        self.tag = 1
        self.nodes = {}
        self.path = []
        self.dirty = True
        self.debug = DEBUG



    def update_path(self):
        if not self.dirty:
            return
        self.dirty = False
        self.tag += 1
        def neighbors(pos):
            cell = self.grid[pos]
            if cell.neighbors is None:
                y, x = pos
                cell.neighbors = []
                for neighbor_y, neighbor_x in self.grid.neighbors(y, x):
                    if self.grid[neighbor_y, neighbor_x].char != '#':
                        cell.neighbors.append((neighbor_y, neighbor_x))
            return cell.neighbors
        def goal(pos):
            return pos == self.goal
        def cost(from_pos, to_pos):
            from_y, from_x = from_pos
            to_y, to_x = to_pos
            return 14 if to_y - from_y and to_x - from_x else 10
        def estimate(pos):
            y, x = pos
            goal_y, goal_x = self.goal
            dy, dx = abs(goal_y - y), abs(goal_x - x)
            return min(dy, dx) * 14 + abs(dy - dx) * 10
        def debug(nodes):
            self.nodes = nodes
        self.path = astar((self.y, self.x), neighbors, goal, 0, cost,
                          estimate, self.limit)









grid = parse_grid(DUNGEON, WIDTH, HEIGHT)
engine = Engine(grid)
engine.update_path()
print(engine.path)



from http.server import BaseHTTPRequestHandler, HTTPServer

class StoreHandler(BaseHTTPRequestHandler):

    def do_GET(self):
        print(self.path)
        aud = self.path
        print("Path : ", self.path)

        result = re.search(r'\/[0-9][0-9][0-9]', aud)
        if result.group(0) != None:
            print('ok')
            result = re.search(r'[0-9][0-9][0-9]', aud)
            aud = int(result.group(0))
            if aud == 100:
                x=10
                y=20
            elif aud == 101:
                x=3
                y=20

            engine.goal = (x,y)
            engine.dirty = True
            print(engine.goal)
            engine.update_path()
            print(engine.path)

            command = ""

            for i in range(1,len(engine.path)-1):
                if engine.path[i-1][0] > engine.path[i][0]:
                    command += "T"
                elif engine.path[i-1][0] < engine.path[i][0]:
                    command += "D"

                if engine.path[i-1][1] < engine.path[i][1]:
                    command += "R"
                elif engine.path[i-1][1] > engine.path[i][1]:
                    command += "L"
            print(command)
            ser.write(command.encode('ascii'))

    def do_POST(self):
            self.send_response(200)


server = HTTPServer(('', 8080), StoreHandler)
server.serve_forever()