advent09.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "code",
   5    "execution_count": 1,
   6    "metadata": {
   7     "collapsed": true
   8    },
   9    "outputs": [],
  10    "source": [
  11     "pi9 = open('advent09.txt').read().strip()"
  12    ]
  13   },
  14   {
  15    "cell_type": "code",
  16    "execution_count": 2,
  17    "metadata": {
  18     "collapsed": false,
  19     "scrolled": true
  20    },
  21    "outputs": [
  22     {
  23      "data": {
  24       "text/plain": [
  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",
  39        " ('Arbre',\n",
  40        "  'AlphaCentauri'): Connection(origin='Arbre', destination='AlphaCentauri', distance=116),\n",
  41        " ('Arbre',\n",
  42        "  'Faerun'): Connection(origin='Arbre', destination='Faerun', distance=24),\n",
  43        " ('Arbre',\n",
  44        "  'Norrath'): Connection(origin='Arbre', destination='Norrath', distance=135),\n",
  45        " ('Arbre',\n",
  46        "  'Snowdin'): Connection(origin='Arbre', destination='Snowdin', distance=129),\n",
  47        " ('Arbre',\n",
  48        "  'Straylight'): Connection(origin='Arbre', destination='Straylight', distance=40),\n",
  49        " ('Arbre',\n",
  50        "  'Tambi'): Connection(origin='Arbre', destination='Tambi', distance=53),\n",
  51        " ('Arbre',\n",
  52        "  'Tristram'): Connection(origin='Arbre', destination='Tristram', distance=122),\n",
  53        " ('Faerun',\n",
  54        "  'AlphaCentauri'): Connection(origin='Faerun', destination='AlphaCentauri', distance=13),\n",
  55        " ('Faerun',\n",
  56        "  'Arbre'): Connection(origin='Faerun', destination='Arbre', distance=24),\n",
  57        " ('Faerun',\n",
  58        "  'Norrath'): Connection(origin='Faerun', destination='Norrath', distance=129),\n",
  59        " ('Faerun',\n",
  60        "  'Snowdin'): Connection(origin='Faerun', destination='Snowdin', distance=60),\n",
  61        " ('Faerun',\n",
  62        "  'Straylight'): Connection(origin='Faerun', destination='Straylight', distance=67),\n",
  63        " ('Faerun',\n",
  64        "  'Tambi'): Connection(origin='Faerun', destination='Tambi', distance=71),\n",
  65        " ('Faerun',\n",
  66        "  'Tristram'): Connection(origin='Faerun', destination='Tristram', distance=58),\n",
  67        " ('Norrath',\n",
  68        "  'AlphaCentauri'): Connection(origin='Norrath', destination='AlphaCentauri', distance=15),\n",
  69        " ('Norrath',\n",
  70        "  'Arbre'): Connection(origin='Norrath', destination='Arbre', distance=135),\n",
  71        " ('Norrath',\n",
  72        "  'Faerun'): Connection(origin='Norrath', destination='Faerun', distance=129),\n",
  73        " ('Norrath',\n",
  74        "  'Snowdin'): Connection(origin='Norrath', destination='Snowdin', distance=75),\n",
  75        " ('Norrath',\n",
  76        "  'Straylight'): Connection(origin='Norrath', destination='Straylight', distance=54),\n",
  77        " ('Norrath',\n",
  78        "  'Tambi'): Connection(origin='Norrath', destination='Tambi', distance=82),\n",
  79        " ('Norrath',\n",
  80        "  'Tristram'): Connection(origin='Norrath', destination='Tristram', distance=142),\n",
  81        " ('Snowdin',\n",
  82        "  'AlphaCentauri'): Connection(origin='Snowdin', destination='AlphaCentauri', distance=12),\n",
  83        " ('Snowdin',\n",
  84        "  'Arbre'): Connection(origin='Snowdin', destination='Arbre', distance=129),\n",
  85        " ('Snowdin',\n",
  86        "  'Faerun'): Connection(origin='Snowdin', destination='Faerun', distance=60),\n",
  87        " ('Snowdin',\n",
  88        "  'Norrath'): Connection(origin='Snowdin', destination='Norrath', distance=75),\n",
  89        " ('Snowdin',\n",
  90        "  'Straylight'): Connection(origin='Snowdin', destination='Straylight', distance=99),\n",
  91        " ('Snowdin',\n",
  92        "  'Tambi'): Connection(origin='Snowdin', destination='Tambi', distance=15),\n",
  93        " ('Snowdin',\n",
  94        "  'Tristram'): Connection(origin='Snowdin', destination='Tristram', distance=103),\n",
  95        " ('Straylight',\n",
  96        "  'AlphaCentauri'): Connection(origin='Straylight', destination='AlphaCentauri', distance=91),\n",
  97        " ('Straylight',\n",
  98        "  'Arbre'): Connection(origin='Straylight', destination='Arbre', distance=40),\n",
  99        " ('Straylight',\n",
 100        "  'Faerun'): Connection(origin='Straylight', destination='Faerun', distance=67),\n",
 101        " ('Straylight',\n",
 102        "  'Norrath'): Connection(origin='Straylight', destination='Norrath', distance=54),\n",
 103        " ('Straylight',\n",
 104        "  'Snowdin'): Connection(origin='Straylight', destination='Snowdin', distance=99),\n",
 105        " ('Straylight',\n",
 106        "  'Tambi'): Connection(origin='Straylight', destination='Tambi', distance=70),\n",
 107        " ('Straylight',\n",
 108        "  'Tristram'): Connection(origin='Straylight', destination='Tristram', distance=97),\n",
 109        " ('Tambi',\n",
 110        "  'AlphaCentauri'): Connection(origin='Tambi', destination='AlphaCentauri', distance=18),\n",
 111        " ('Tambi',\n",
 112        "  'Arbre'): Connection(origin='Tambi', destination='Arbre', distance=53),\n",
 113        " ('Tambi',\n",
 114        "  'Faerun'): Connection(origin='Tambi', destination='Faerun', distance=71),\n",
 115        " ('Tambi',\n",
 116        "  'Norrath'): Connection(origin='Tambi', destination='Norrath', distance=82),\n",
 117        " ('Tambi',\n",
 118        "  'Snowdin'): Connection(origin='Tambi', destination='Snowdin', distance=15),\n",
 119        " ('Tambi',\n",
 120        "  'Straylight'): Connection(origin='Tambi', destination='Straylight', distance=70),\n",
 121        " ('Tambi',\n",
 122        "  'Tristram'): Connection(origin='Tambi', destination='Tristram', distance=49),\n",
 123        " ('Tristram',\n",
 124        "  'AlphaCentauri'): Connection(origin='Tristram', destination='AlphaCentauri', distance=118),\n",
 125        " ('Tristram',\n",
 126        "  'Arbre'): Connection(origin='Tristram', destination='Arbre', distance=122),\n",
 127        " ('Tristram',\n",
 128        "  'Faerun'): Connection(origin='Tristram', destination='Faerun', distance=58),\n",
 129        " ('Tristram',\n",
 130        "  'Norrath'): Connection(origin='Tristram', destination='Norrath', distance=142),\n",
 131        " ('Tristram',\n",
 132        "  'Snowdin'): Connection(origin='Tristram', destination='Snowdin', distance=103),\n",
 133        " ('Tristram',\n",
 134        "  'Straylight'): Connection(origin='Tristram', destination='Straylight', distance=97),\n",
 135        " ('Tristram',\n",
 136        "  'Tambi'): Connection(origin='Tristram', destination='Tambi', distance=49)}"
 137       ]
 138      },
 139      "execution_count": 2,
 140      "metadata": {},
 141      "output_type": "execute_result"
 142     }
 143    ],
 144    "source": [
 145     "from collections import namedtuple\n",
 146     "\n",
 147     "Connection = namedtuple('Connection', ['origin', 'destination', 'distance'])\n",
 148     "\n",
 149     "connections = {}\n",
 150     "\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",
 155     "connections"
 156    ]
 157   },
 158   {
 159    "cell_type": "code",
 160    "execution_count": 3,
 161    "metadata": {
 162     "collapsed": false
 163    },
 164    "outputs": [
 165     {
 166      "data": {
 167       "text/plain": [
 168        "{'AlphaCentauri',\n",
 169        " 'Arbre',\n",
 170        " 'Faerun',\n",
 171        " 'Norrath',\n",
 172        " 'Snowdin',\n",
 173        " 'Straylight',\n",
 174        " 'Tambi',\n",
 175        " 'Tristram'}"
 176       ]
 177      },
 178      "execution_count": 3,
 179      "metadata": {},
 180      "output_type": "execute_result"
 181     }
 182    ],
 183    "source": [
 184     "towns = set([c[0] for c in connections] + [c[1] for c in connections])\n",
 185     "towns"
 186    ]
 187   },
 188   {
 189    "cell_type": "code",
 190    "execution_count": 4,
 191    "metadata": {
 192     "collapsed": true
 193    },
 194    "outputs": [],
 195    "source": [
 196     "def viable(route):\n",
 197     "    return all((c in connections) for c in zip(route, route[1:]))        "
 198    ]
 199   },
 200   {
 201    "cell_type": "code",
 202    "execution_count": 5,
 203    "metadata": {
 204     "collapsed": false
 205    },
 206    "outputs": [
 207     {
 208      "data": {
 209       "text/plain": [
 210        "True"
 211       ]
 212      },
 213      "execution_count": 5,
 214      "metadata": {},
 215      "output_type": "execute_result"
 216     }
 217    ],
 218    "source": [
 219     "viable(['Faerun', 'Norrath', 'Tambi', 'Arbre'])"
 220    ]
 221   },
 222   {
 223    "cell_type": "code",
 224    "execution_count": 6,
 225    "metadata": {
 226     "collapsed": true
 227    },
 228    "outputs": [],
 229    "source": [
 230     "def length(route):\n",
 231     "    return sum(connections[c].distance for c in zip(route, route[1:]))"
 232    ]
 233   },
 234   {
 235    "cell_type": "code",
 236    "execution_count": 7,
 237    "metadata": {
 238     "collapsed": false
 239    },
 240    "outputs": [
 241     {
 242      "data": {
 243       "text/plain": [
 244        "211"
 245       ]
 246      },
 247      "execution_count": 7,
 248      "metadata": {},
 249      "output_type": "execute_result"
 250     }
 251    ],
 252    "source": [
 253     "length(['Faerun', 'Norrath', 'Tambi'])"
 254    ]
 255   },
 256   {
 257    "cell_type": "code",
 258    "execution_count": 8,
 259    "metadata": {
 260     "collapsed": true
 261    },
 262    "outputs": [],
 263    "source": [
 264     "def best(route1, route2):\n",
 265     "    if length(route1) < length(route2):\n",
 266     "        return route1\n",
 267     "    else:\n",
 268     "        return route2"
 269    ]
 270   },
 271   {
 272    "cell_type": "code",
 273    "execution_count": 9,
 274    "metadata": {
 275     "collapsed": true
 276    },
 277    "outputs": [],
 278    "source": [
 279     "def worst(route1, route2):\n",
 280     "    if length(route1) > length(route2):\n",
 281     "        return route1\n",
 282     "    else:\n",
 283     "        return route2"
 284    ]
 285   },
 286   {
 287    "cell_type": "code",
 288    "execution_count": 10,
 289    "metadata": {
 290     "collapsed": false
 291    },
 292    "outputs": [
 293     {
 294      "data": {
 295       "text/plain": [
 296        "(('Norrath',\n",
 297        "  'Straylight',\n",
 298        "  'Arbre',\n",
 299        "  'Faerun',\n",
 300        "  'AlphaCentauri',\n",
 301        "  'Snowdin',\n",
 302        "  'Tambi',\n",
 303        "  'Tristram'),\n",
 304        " 207)"
 305       ]
 306      },
 307      "execution_count": 10,
 308      "metadata": {},
 309      "output_type": "execute_result"
 310     }
 311    ],
 312    "source": [
 313     "import itertools\n",
 314     "import functools\n",
 315     "\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)"
 319    ]
 320   },
 321   {
 322    "cell_type": "code",
 323    "execution_count": 11,
 324    "metadata": {
 325     "collapsed": false
 326    },
 327    "outputs": [
 328     {
 329      "data": {
 330       "text/plain": [
 331        "40320"
 332       ]
 333      },
 334      "execution_count": 11,
 335      "metadata": {},
 336      "output_type": "execute_result"
 337     }
 338    ],
 339    "source": [
 340     "len(list(filter(viable, [r for r in itertools.permutations(towns)])))"
 341    ]
 342   },
 343   {
 344    "cell_type": "code",
 345    "execution_count": 12,
 346    "metadata": {
 347     "collapsed": false
 348    },
 349    "outputs": [],
 350    "source": [
 351     "ps = list(itertools.permutations(towns))"
 352    ]
 353   },
 354   {
 355    "cell_type": "code",
 356    "execution_count": 13,
 357    "metadata": {
 358     "collapsed": false
 359    },
 360    "outputs": [
 361     {
 362      "data": {
 363       "text/plain": [
 364        "40320"
 365       ]
 366      },
 367      "execution_count": 13,
 368      "metadata": {},
 369      "output_type": "execute_result"
 370     }
 371    ],
 372    "source": [
 373     "len(list(filter(viable, ps)))"
 374    ]
 375   },
 376   {
 377    "cell_type": "code",
 378    "execution_count": 14,
 379    "metadata": {
 380     "collapsed": false
 381    },
 382    "outputs": [
 383     {
 384      "data": {
 385       "text/plain": [
 386        "(('Straylight',\n",
 387        "  'Snowdin',\n",
 388        "  'Arbre',\n",
 389        "  'AlphaCentauri',\n",
 390        "  'Tristram',\n",
 391        "  'Norrath',\n",
 392        "  'Faerun',\n",
 393        "  'Tambi'),\n",
 394        " 804)"
 395       ]
 396      },
 397      "execution_count": 14,
 398      "metadata": {},
 399      "output_type": "execute_result"
 400     }
 401    ],
 402    "source": [
 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)"
 406    ]
 407   },
 408   {
 409    "cell_type": "code",
 410    "execution_count": null,
 411    "metadata": {
 412     "collapsed": true
 413    },
 414    "outputs": [],
 415    "source": []
 416   }
 417  ],
 418  "metadata": {
 419   "kernelspec": {
 420    "display_name": "Python 3",
 421    "language": "python",
 422    "name": "python3"
 423   },
 424   "language_info": {
 425    "codemirror_mode": {
 426     "name": "ipython",
 427     "version": 3
 428    },
 429    "file_extension": ".py",
 430    "mimetype": "text/x-python",
 431    "name": "python",
 432    "nbconvert_exporter": "python",
 433    "pygments_lexer": "ipython3",
 434    "version": "3.4.3"
 435   }
 436  },
 437  "nbformat": 4,
 438  "nbformat_minor": 0
 439 }