from paris import read_graph, closest_node, display
N, paris_graph, weight, distance, visited, paris_coords = read_graph()
from geopy.geocoders import Nominatim
geocoder = Nominatim()
start = geocoder.geocode("NUMA, Paris")
start.longitude, start.latitude
(2.34958019131168, 48.8676206)
numa = closest_node(paris_coords, start)
numa
11253
from tryalgo.dijkstra import dijkstra
def paris_cross(start_node, f):
N, paris_graph, weight, distance, visited, paris_coords = read_graph()
node = start_node
path = []
elapsed_time = 0
score = 0
while elapsed_time < 3600: # While there is still time
path.append(node)
new_neighbors = list(filter(lambda neighbor: not visited[node][neighbor], paris_graph[node]))
if new_neighbors:
new_neighbors.sort(key=lambda neighbor: f(path, neighbor))
chosen_neighbor = new_neighbors[-1]
elapsed_time += weight[node][chosen_neighbor]
score += distance[node][chosen_neighbor]
visited[node][chosen_neighbor] = True
visited[chosen_neighbor][node] = True
else:
stuck_node = node
dist, prec = dijkstra(paris_graph, weight, stuck_node)
for jump_time, node in sorted((dist[u], u) for u in range(N)):
if any(not visited[node][neighbor] for neighbor in paris_graph[node]):
chosen_neighbor = node
elapsed_time += jump_time
break
extra_path = []
node = prec[chosen_neighbor]
while node != stuck_node:
extra_path.append(node)
node = prec[node]
path.extend(extra_path)
node = chosen_neighbor
print('Score:', score, 'in', elapsed_time, 'seconds')
return path
from random import randint
def random_walk(path, neighbor):
return randint(1, 100)
path = paris_cross(numa, random_walk)
Score: 26044 in 3732 seconds
display(paris_coords, path)
def longest_road(path, neighbor):
return distance[path[-1]][neighbor]
path = paris_cross(numa, longest_road)
Score: 29197 in 3612 seconds
display(paris_coords, path)
def best_road(path, neighbor):
return distance[path[-1]][neighbor] / weight[path[-1]][neighbor]
path = paris_cross(numa, best_road)
Score: 26824 in 3627 seconds
display(paris_coords, path)