cities = {};

cities[1] = {name = "Atlanta", 		lon = 84.23, 	lat = 33.45}
cities[2] = {name = "Boston", 		lon = 71.85, 	lat = 42.21}
cities[3] = {name = "Chicago", 		lon = 87.37, 	lat = 41.50}
cities[4] = {name = "Denver", 		lon = 105.00, 	lat = 39.45}
cities[5] = {name = "Eugene", 		lon = 123.05, 	lat = 44.03}
cities[6] = {name = "Flagstaff", 		lon = 111.41, 	lat = 35.13}
cities[7] = {name = "Grand-Jct", 		lon = 108.37, 	lat = 39.05}
cities[8] = {name = "Houston", 		lon = 105.00, 	lat = 34.00}
cities[9] = {name = "Indianapolis", 	lon = 86.10, 	lat = 39.46}
cities[10] = {name = "Jacksonville", 	lon = 81.40, 	lat = 30.22}
cities[11] = {name = "Kansas-City",	lon = 94.35, 	lat = 39.06}
cities[12] = {name = "Los-Angeles", 	lon = 118.15, 	lat = 34.03}
cities[13] = {name = "Memphis", 		lon = 90.03, 	lat = 35.09}
cities[14] = {name = "New-York", 		lon = 73.58, 	lat = 40.47}
cities[15] = {name = "Oklahoma-City", 	lon = 97.28, 	lat = 35.26}
cities[16] = {name = "Pittsburgh", 		lon = 79.57, 	lat = 40.27}
cities[17] = {name = "Quebec", 		lon = 71.11, 	lat = 46.49}
cities[18] = {name = "Reno", 			lon = 119.49, 	lat = 39.30}
cities[19] = {name = "San-Francisco", 	lon = 122.26, 	lat = 37.47}
cities[20] = {name = "Tampa", 		lon = 82.27, 	lat = 27.57}
cities[21] = {name = "Victoria", 		lon = 123.21, 	lat = 48.25}
cities[22] = {name = "Washington", 	lon = 77.57, 	lat = 34.14}

function neighbors(city)
   neighborhood = {};
   for i,v in ipairs(cities) do if air_distance(cities[i], city) >= 1000.0 then table.insert(neighborhood, cities[i]); end; end
   return neighborhood;
end

function find_city(city_name)
   --Search for a city with this name and return that entire city
   for i,v in pairs(cities) do
      if cities[i].name == city_name then return cities[i]; end
   end
end

earth_diameter = 12765.0;

function air_distance(city1, city2)
   d = distance(xyz_coords(city1), xyz_coords(city2));
   return earth_diameter* math.asin(d/2);
end

function xyz_coords(city)
   psi = deg_to_radians(city.lon);
   phi = deg_to_radians(city.lat);
   return {math.cos(psi) * math.cos(phi), 
		math.cos(psi) * math.sin(phi),
		math.sin(psi)};
end

function truncate(val)
   if val < 0 then return math.cieling(val) else return math.floor(val); end
end

function deg_to_radians(degree)
   return truncate(degree) + (math.modf(degree)*(100/60)) * math.pi * (1/180);
end

function distance(p1, p2)
   sum = 0;
   for i,v in ipairs(p1) do sum = sum + ((p1[i] - p2[i])^2); end
   return math.sqrt(sum);
end

function print_city(city)
   io.write("City Name: ", city.name, ", Lon: ", city.lon, ", Lat: ", city.lat);
   print("");
end

function trip(start, dest)
print_city(start);
print_city(dest);
   return beam_search(start, is(dest), neighbors, (function(c) return air_distance(c, dest) end), 1)
end