11 "pi9 = open('advent09.txt').read().strip()"
25 "{('AlphaCentauri',\n",
26 " 'Arbre'): Connection(origin='AlphaCentauri', destination='Arbre', distance=116),\n",
27 " ('AlphaCentauri',\n",
28 " 'Faerun'): Connection(origin='AlphaCentauri', destination='Faerun', distance=13),\n",
29 " ('AlphaCentauri',\n",
30 " 'Norrath'): Connection(origin='AlphaCentauri', destination='Norrath', distance=15),\n",
31 " ('AlphaCentauri',\n",
32 " 'Snowdin'): Connection(origin='AlphaCentauri', destination='Snowdin', distance=12),\n",
33 " ('AlphaCentauri',\n",
34 " 'Straylight'): Connection(origin='AlphaCentauri', destination='Straylight', distance=91),\n",
35 " ('AlphaCentauri',\n",
36 " 'Tambi'): Connection(origin='AlphaCentauri', destination='Tambi', distance=18),\n",
37 " ('AlphaCentauri',\n",
38 " 'Tristram'): Connection(origin='AlphaCentauri', destination='Tristram', distance=118),\n",
40 " 'AlphaCentauri'): Connection(origin='Arbre', destination='AlphaCentauri', distance=116),\n",
42 " 'Faerun'): Connection(origin='Arbre', destination='Faerun', distance=24),\n",
44 " 'Norrath'): Connection(origin='Arbre', destination='Norrath', distance=135),\n",
46 " 'Snowdin'): Connection(origin='Arbre', destination='Snowdin', distance=129),\n",
48 " 'Straylight'): Connection(origin='Arbre', destination='Straylight', distance=40),\n",
50 " 'Tambi'): Connection(origin='Arbre', destination='Tambi', distance=53),\n",
52 " 'Tristram'): Connection(origin='Arbre', destination='Tristram', distance=122),\n",
54 " 'AlphaCentauri'): Connection(origin='Faerun', destination='AlphaCentauri', distance=13),\n",
56 " 'Arbre'): Connection(origin='Faerun', destination='Arbre', distance=24),\n",
58 " 'Norrath'): Connection(origin='Faerun', destination='Norrath', distance=129),\n",
60 " 'Snowdin'): Connection(origin='Faerun', destination='Snowdin', distance=60),\n",
62 " 'Straylight'): Connection(origin='Faerun', destination='Straylight', distance=67),\n",
64 " 'Tambi'): Connection(origin='Faerun', destination='Tambi', distance=71),\n",
66 " 'Tristram'): Connection(origin='Faerun', destination='Tristram', distance=58),\n",
68 " 'AlphaCentauri'): Connection(origin='Norrath', destination='AlphaCentauri', distance=15),\n",
70 " 'Arbre'): Connection(origin='Norrath', destination='Arbre', distance=135),\n",
72 " 'Faerun'): Connection(origin='Norrath', destination='Faerun', distance=129),\n",
74 " 'Snowdin'): Connection(origin='Norrath', destination='Snowdin', distance=75),\n",
76 " 'Straylight'): Connection(origin='Norrath', destination='Straylight', distance=54),\n",
78 " 'Tambi'): Connection(origin='Norrath', destination='Tambi', distance=82),\n",
80 " 'Tristram'): Connection(origin='Norrath', destination='Tristram', distance=142),\n",
82 " 'AlphaCentauri'): Connection(origin='Snowdin', destination='AlphaCentauri', distance=12),\n",
84 " 'Arbre'): Connection(origin='Snowdin', destination='Arbre', distance=129),\n",
86 " 'Faerun'): Connection(origin='Snowdin', destination='Faerun', distance=60),\n",
88 " 'Norrath'): Connection(origin='Snowdin', destination='Norrath', distance=75),\n",
90 " 'Straylight'): Connection(origin='Snowdin', destination='Straylight', distance=99),\n",
92 " 'Tambi'): Connection(origin='Snowdin', destination='Tambi', distance=15),\n",
94 " 'Tristram'): Connection(origin='Snowdin', destination='Tristram', distance=103),\n",
96 " 'AlphaCentauri'): Connection(origin='Straylight', destination='AlphaCentauri', distance=91),\n",
98 " 'Arbre'): Connection(origin='Straylight', destination='Arbre', distance=40),\n",
100 " 'Faerun'): Connection(origin='Straylight', destination='Faerun', distance=67),\n",
102 " 'Norrath'): Connection(origin='Straylight', destination='Norrath', distance=54),\n",
104 " 'Snowdin'): Connection(origin='Straylight', destination='Snowdin', distance=99),\n",
106 " 'Tambi'): Connection(origin='Straylight', destination='Tambi', distance=70),\n",
108 " 'Tristram'): Connection(origin='Straylight', destination='Tristram', distance=97),\n",
110 " 'AlphaCentauri'): Connection(origin='Tambi', destination='AlphaCentauri', distance=18),\n",
112 " 'Arbre'): Connection(origin='Tambi', destination='Arbre', distance=53),\n",
114 " 'Faerun'): Connection(origin='Tambi', destination='Faerun', distance=71),\n",
116 " 'Norrath'): Connection(origin='Tambi', destination='Norrath', distance=82),\n",
118 " 'Snowdin'): Connection(origin='Tambi', destination='Snowdin', distance=15),\n",
120 " 'Straylight'): Connection(origin='Tambi', destination='Straylight', distance=70),\n",
122 " 'Tristram'): Connection(origin='Tambi', destination='Tristram', distance=49),\n",
124 " 'AlphaCentauri'): Connection(origin='Tristram', destination='AlphaCentauri', distance=118),\n",
126 " 'Arbre'): Connection(origin='Tristram', destination='Arbre', distance=122),\n",
128 " 'Faerun'): Connection(origin='Tristram', destination='Faerun', distance=58),\n",
130 " 'Norrath'): Connection(origin='Tristram', destination='Norrath', distance=142),\n",
132 " 'Snowdin'): Connection(origin='Tristram', destination='Snowdin', distance=103),\n",
134 " 'Straylight'): Connection(origin='Tristram', destination='Straylight', distance=97),\n",
136 " 'Tambi'): Connection(origin='Tristram', destination='Tambi', distance=49)}"
139 "execution_count": 2,
141 "output_type": "execute_result"
145 "from collections import namedtuple\n",
147 "Connection = namedtuple('Connection', ['origin', 'destination', 'distance'])\n",
149 "connections = {}\n",
151 "for l in pi9.splitlines():\n",
152 " s = l.split(' ')\n",
153 " connections[(s[0], s[2])] = Connection(origin=s[0], destination=s[2], distance=int(s[4]))\n",
154 " connections[(s[2], s[0])] = Connection(origin=s[2], destination=s[0], distance=int(s[4]))\n",
160 "execution_count": 3,
168 "{'AlphaCentauri',\n",
178 "execution_count": 3,
180 "output_type": "execute_result"
184 "towns = set([c[0] for c in connections] + [c[1] for c in connections])\n",
190 "execution_count": 4,
196 "def viable(route):\n",
197 " return all((c in connections) for c in zip(route, route[1:])) "
202 "execution_count": 5,
213 "execution_count": 5,
215 "output_type": "execute_result"
219 "viable(['Faerun', 'Norrath', 'Tambi', 'Arbre'])"
224 "execution_count": 6,
230 "def length(route):\n",
231 " return sum(connections[c].distance for c in zip(route, route[1:]))"
236 "execution_count": 7,
247 "execution_count": 7,
249 "output_type": "execute_result"
253 "length(['Faerun', 'Norrath', 'Tambi'])"
258 "execution_count": 8,
264 "def best(route1, route2):\n",
265 " if length(route1) < length(route2):\n",
273 "execution_count": 9,
279 "def worst(route1, route2):\n",
280 " if length(route1) > length(route2):\n",
288 "execution_count": 10,
300 " 'AlphaCentauri',\n",
307 "execution_count": 10,
309 "output_type": "execute_result"
313 "import itertools\n",
314 "import functools\n",
316 "possible_routes = filter(viable, [r for r in itertools.permutations(towns)])\n",
317 "best_route = functools.reduce(best, possible_routes)\n",
318 "best_route, length(best_route)"
323 "execution_count": 11,
334 "execution_count": 11,
336 "output_type": "execute_result"
340 "len(list(filter(viable, [r for r in itertools.permutations(towns)])))"
345 "execution_count": 12,
351 "ps = list(itertools.permutations(towns))"
356 "execution_count": 13,
367 "execution_count": 13,
369 "output_type": "execute_result"
373 "len(list(filter(viable, ps)))"
378 "execution_count": 14,
389 " 'AlphaCentauri',\n",
397 "execution_count": 14,
399 "output_type": "execute_result"
403 "possible_routes = filter(viable, [r for r in itertools.permutations(towns)])\n",
404 "worst_route = functools.reduce(worst, possible_routes)\n",
405 "worst_route, length(worst_route)"
410 "execution_count": null,
420 "display_name": "Python 3",
421 "language": "python",
429 "file_extension": ".py",
430 "mimetype": "text/x-python",
432 "nbconvert_exporter": "python",
433 "pygments_lexer": "ipython3",