{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# TryAlgo in Paris"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"from paris import read_graph, closest_node, display\n",
"\n",
"N, paris_graph, weight, distance, visited, paris_coords = read_graph()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Géolocalisation de NUMA"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"(2.34958019131168, 48.8676206)"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"from geopy.geocoders import Nominatim\n",
"\n",
"geocoder = Nominatim()\n",
"start = geocoder.geocode(\"NUMA, Paris\")\n",
"start.longitude, start.latitude"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"11253"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"numa = closest_node(paris_coords, start)\n",
"numa"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"from tryalgo.dijkstra import dijkstra\n",
"\n",
"def paris_cross(start_node, f):\n",
" N, paris_graph, weight, distance, visited, paris_coords = read_graph()\n",
" node = start_node\n",
" path = []\n",
" elapsed_time = 0\n",
" score = 0\n",
" while elapsed_time < 3600: # While there is still time\n",
" path.append(node)\n",
" new_neighbors = list(filter(lambda neighbor: not visited[node][neighbor], paris_graph[node]))\n",
" if new_neighbors:\n",
" new_neighbors.sort(key=lambda neighbor: f(path, neighbor))\n",
" chosen_neighbor = new_neighbors[-1]\n",
" elapsed_time += weight[node][chosen_neighbor]\n",
" score += distance[node][chosen_neighbor]\n",
" visited[node][chosen_neighbor] = True\n",
" visited[chosen_neighbor][node] = True\n",
" else:\n",
" stuck_node = node\n",
" dist, prec = dijkstra(paris_graph, weight, stuck_node)\n",
" for jump_time, node in sorted((dist[u], u) for u in range(N)):\n",
" if any(not visited[node][neighbor] for neighbor in paris_graph[node]):\n",
" chosen_neighbor = node\n",
" elapsed_time += jump_time\n",
" break\n",
" extra_path = []\n",
" node = prec[chosen_neighbor]\n",
" while node != stuck_node:\n",
" extra_path.append(node)\n",
" node = prec[node]\n",
" path.extend(extra_path)\n",
" node = chosen_neighbor\n",
" print('Score:', score, 'in', elapsed_time, 'seconds')\n",
" return path"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Première balade : marche aléatoire"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Score: 26044 in 3732 seconds\n"
]
}
],
"source": [
"from random import randint\n",
"\n",
"def random_walk(path, neighbor):\n",
" return randint(1, 100)\n",
"\n",
"path = paris_cross(numa, random_walk)"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/plain": [
""
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"display(paris_coords, path)"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"## Deuxième balade : la route la plus longue"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Score: 29197 in 3612 seconds\n"
]
}
],
"source": [
"def longest_road(path, neighbor):\n",
" return distance[path[-1]][neighbor]\n",
"\n",
"path = paris_cross(numa, longest_road)"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/plain": [
""
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"display(paris_coords, path)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Troisième balade : la route ayant le plus grand rapport longueur / temps"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Score: 26824 in 3627 seconds\n"
]
}
],
"source": [
"def best_road(path, neighbor):\n",
" return distance[path[-1]][neighbor] / weight[path[-1]][neighbor]\n",
"\n",
"path = paris_cross(numa, best_road)"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/plain": [
""
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"display(paris_coords, path)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.4.3"
}
},
"nbformat": 4,
"nbformat_minor": 0
}