Please Solving in Python 3

1. (40 points) Implement an optimal route finder program using A* algorithm. i. Find coordinates.txt and map.txt. Figure 1 is attached for your information. ii. coordinates.txt stores the longitude and latitude of each city. City: (Longitude, Latitude) iii. map.txt stores actual distances between connected cities in California. We assume each city is connected with limited number of nearby cities. City-NearbyCity1(Distance), NearbyCity2(Distance),... iv. You can compute the straight line distance between two cities using the Haversine formula. You need to convert longitude and latitude to radian. (radian = 1k0 degree) Let 41, 42 be the latitude of point 1 and latitude of point 2 and 11, 12 be the longitude of point 1 and longitude of point 2. The straight line distance d is defined by d=2r arcsin (Vsin* (* (92 27.01) + cos 41 - cos p2 - sin (127'!)) 3 where r is the radius of the earth. Use r= 3,958.8 mile. v. The program should be able to parse coordinates.txt and map.txt take a departing city and an arriving city as input arguments (an interactive style is not acceptable). output an optimal route from the departing city to the arriving city