# TryAlgo in Paris¶

In :
from paris import read_graph, closest_node, display

N, paris_graph, weight, distance, visited, paris_coords = read_graph()


## Géolocalisation de NUMA¶

In :
from geopy.geocoders import Nominatim

geocoder = Nominatim()
start = geocoder.geocode("NUMA, Paris")
start.longitude, start.latitude

Out:
(2.34958019131168, 48.8676206)
In :
numa = closest_node(paris_coords, start)
numa

Out:
11253
In :
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


## Première balade : marche aléatoire¶

In :
from random import randint

def random_walk(path, neighbor):
return randint(1, 100)

path = paris_cross(numa, random_walk)

Score: 26044 in 3732 seconds

In :
display(paris_coords, path)

Out:

## Deuxième balade : la route la plus longue¶

In :
def longest_road(path, neighbor):
return distance[path[-1]][neighbor]


Score: 29197 in 3612 seconds

In :
display(paris_coords, path)

Out:

## Troisième balade : la route ayant le plus grand rapport longueur / temps¶

In :
def best_road(path, neighbor):
return distance[path[-1]][neighbor] / weight[path[-1]][neighbor]


Score: 26824 in 3627 seconds

display(paris_coords, path)