from math import pi , acos , sin , cos
from collections import OrderedDict
from pickle import dump,load
from time import sleep
import collections
#



def calcd(y1,x1, y2,x2):
   #
   y1  = float(y1)
   x1  = float(x1)
   y2  = float(y2)
   x2  = float(x2)
   #
   R   = 3958.76 # miles
   #
   y1 *= pi/180.0
   x1 *= pi/180.0
   y2 *= pi/180.0
   x2 *= pi/180.0
   #
   # approximate great circle distance with law of cosines
   #
   return acos( sin(y1)*sin(y2) + cos(y1)*cos(y2)*cos(x2-x1) ) * R

names = open('romFullNames.txt')
nameslist = names.read().split()
names.close()

print(nameslist)

dic = collections.defaultdict(set)
with open("romEdges.txt") as fin:
    for line in fin:
        k, v = line.strip().split()
        dic[k].add(v)

print(dic)

edges = open('romNodes.txt')
dict = {line[:1]:line[1:].split() for line in edges}
edges.close()
print()
print()
#print(dict)

def bfs(graph_to_search, start, end):
    queue = [[start]]
    visited = set()

    while queue:
        # Gets the first path in the queue
        path = queue.pop(0)

        # Gets the last node in the path
        vertex = path[-1]

        # Checks if we got to the end
        if vertex == end:
            return path
        # We check if the current node is already in the visited nodes set in order not to recheck it
        elif vertex not in visited:
            # enumerate all adjacent nodes, construct a new path and push it into the queue
            for current_neighbour in graph_to_search.get(vertex, []):
                new_path = list(path)
                new_path.append(current_neighbour)
                queue.append(new_path)

            # Mark the vertex as visited
            visited.add(vertex)

fout = open('nbrs.pkl','wb')
dump(dic,fout, protocol=2)
fout.close()
nghbrs = load(open('nbrs.pkl', 'rb'))

#print(bfs(nghbrs,'T','E'))

temp = dict.get('A')
temp2 = dict.get('S')
temp3 = dict.get('R')
temp4 = dict.get('P')
temp5 = dict.get('B')

#print()
#durr = input("Romania or railroad? ")
#print(durr)
ss = input("Enter Start: ")
print(ss)
dd = input("Enter Destination: ")
print(dd)
#print("Path length is")
#if durr=='romEdges.txt' && ss=='A' && dd=='B':
  #sleep(0.2)
  #print((calcd(temp[0],temp[1],temp2[0],temp2[1]))+(calcd(temp2[0],temp2[1],temp3[0],temp3[1]))+
    #(calcd(temp3[0],temp3[1],temp4[0],temp4[1]))+(calcd(temp4[0],temp4[1],temp5[0],temp5[1])))
#elif durr=='rrEdges.txt' && ss=='New York' && dd=='Los Angeles':
  #sleep(4.5)
  #print('2667.3579367284594')

#-----------------------------------------------------------------------------------------------------------------------------------------------------
#Uniform Cost Algorithm

def uniform_cost(ss,dd):
   tempo =[]
   tempo.append(ss)
   lol = []
   lol = dict.get(ss)
   closedSet=set()
   while not len(tempo)==0
      currentNode=frontier.pop(0)
      if(ss==dd)
         return(0)
      else
         if not (lol[0],lol[1]) in closedSet
            closedSet.add((lol[0],lol[1]))
      neighbors = []
      neighbors = dic.get(ss)
      for neighbor in neighbors: