import numpy as np

# <<<CELL>>>

graph = {
    'A':[('B',9),('C',4),('D',7)],
    'B':[('E',11)],
    'C':[('E',17),('F',12)],
    'D':[('A',7),('F',14)],
    'E':[('C',17),('Z',5)],
    'F':[('Z',9)],
    'Z':[]
}

# <<<CELL>>>

heuristic = {
    'A':21,
    'B':14,
    'C':18,
    'D':18,
    'E':5,
    'F':8,
    'Z':0
}

# <<<CELL>>>

#GBFS

open_list = [('A',['A'],0)]
visited = []

goal = 'Z'

while open_list:
  best = 0

  for i in range(len(open_list)):
    if heuristic[open_list[i][0]] < heuristic[open_list[best][0]]:
      best = i

  current, path, cost = open_list.pop(best)

  if current in visited:
    continue

  visited.append(current)
  print("Visited: ",current)
  print("Path: ",path)
  print("Cost: ",cost)

  if current==goal:
    print("Goal found!!")
    print("Final Path: ", " -> ".join(path))
    print("Total Cost: ",cost)
    break

  for neighbour, edge_cost in graph[current]:
    if neighbour not in visited:
      open_list.append([neighbour,path+[neighbour],cost + edge_cost])

# <<<CELL>>>

#A*

open_list = [('A',['A'],0)]
visited = []

goal = 'Z'

while open_list:
  best = 0

  for i in range(len(open_list)):

    if heuristic[open_list[i][0]]+open_list[i][2]< heuristic[open_list[best][0]]+open_list[best][2]:
      best = i

  current, path, cost = open_list.pop(best)

  if current in visited:
    continue

  visited.append(current)
  print("Visited: ",current)
  print("Path: ",path)
  print("Cost: ",cost)

  if current==goal:
    print("Goal found!!")
    print("Final Path: ", " -> ".join(path))
    print("Total Cost: ",cost)
    break

  for neighbour, edge_cost in graph[current]:
    if neighbour not in visited:
      open_list.append([neighbour,path+[neighbour],cost + edge_cost])
