{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "pi9 = open('advent09.txt').read().strip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{('AlphaCentauri',\n",
       "  'Arbre'): Connection(origin='AlphaCentauri', destination='Arbre', distance=116),\n",
       " ('AlphaCentauri',\n",
       "  'Faerun'): Connection(origin='AlphaCentauri', destination='Faerun', distance=13),\n",
       " ('AlphaCentauri',\n",
       "  'Norrath'): Connection(origin='AlphaCentauri', destination='Norrath', distance=15),\n",
       " ('AlphaCentauri',\n",
       "  'Snowdin'): Connection(origin='AlphaCentauri', destination='Snowdin', distance=12),\n",
       " ('AlphaCentauri',\n",
       "  'Straylight'): Connection(origin='AlphaCentauri', destination='Straylight', distance=91),\n",
       " ('AlphaCentauri',\n",
       "  'Tambi'): Connection(origin='AlphaCentauri', destination='Tambi', distance=18),\n",
       " ('AlphaCentauri',\n",
       "  'Tristram'): Connection(origin='AlphaCentauri', destination='Tristram', distance=118),\n",
       " ('Arbre',\n",
       "  'AlphaCentauri'): Connection(origin='Arbre', destination='AlphaCentauri', distance=116),\n",
       " ('Arbre',\n",
       "  'Faerun'): Connection(origin='Arbre', destination='Faerun', distance=24),\n",
       " ('Arbre',\n",
       "  'Norrath'): Connection(origin='Arbre', destination='Norrath', distance=135),\n",
       " ('Arbre',\n",
       "  'Snowdin'): Connection(origin='Arbre', destination='Snowdin', distance=129),\n",
       " ('Arbre',\n",
       "  'Straylight'): Connection(origin='Arbre', destination='Straylight', distance=40),\n",
       " ('Arbre',\n",
       "  'Tambi'): Connection(origin='Arbre', destination='Tambi', distance=53),\n",
       " ('Arbre',\n",
       "  'Tristram'): Connection(origin='Arbre', destination='Tristram', distance=122),\n",
       " ('Faerun',\n",
       "  'AlphaCentauri'): Connection(origin='Faerun', destination='AlphaCentauri', distance=13),\n",
       " ('Faerun',\n",
       "  'Arbre'): Connection(origin='Faerun', destination='Arbre', distance=24),\n",
       " ('Faerun',\n",
       "  'Norrath'): Connection(origin='Faerun', destination='Norrath', distance=129),\n",
       " ('Faerun',\n",
       "  'Snowdin'): Connection(origin='Faerun', destination='Snowdin', distance=60),\n",
       " ('Faerun',\n",
       "  'Straylight'): Connection(origin='Faerun', destination='Straylight', distance=67),\n",
       " ('Faerun',\n",
       "  'Tambi'): Connection(origin='Faerun', destination='Tambi', distance=71),\n",
       " ('Faerun',\n",
       "  'Tristram'): Connection(origin='Faerun', destination='Tristram', distance=58),\n",
       " ('Norrath',\n",
       "  'AlphaCentauri'): Connection(origin='Norrath', destination='AlphaCentauri', distance=15),\n",
       " ('Norrath',\n",
       "  'Arbre'): Connection(origin='Norrath', destination='Arbre', distance=135),\n",
       " ('Norrath',\n",
       "  'Faerun'): Connection(origin='Norrath', destination='Faerun', distance=129),\n",
       " ('Norrath',\n",
       "  'Snowdin'): Connection(origin='Norrath', destination='Snowdin', distance=75),\n",
       " ('Norrath',\n",
       "  'Straylight'): Connection(origin='Norrath', destination='Straylight', distance=54),\n",
       " ('Norrath',\n",
       "  'Tambi'): Connection(origin='Norrath', destination='Tambi', distance=82),\n",
       " ('Norrath',\n",
       "  'Tristram'): Connection(origin='Norrath', destination='Tristram', distance=142),\n",
       " ('Snowdin',\n",
       "  'AlphaCentauri'): Connection(origin='Snowdin', destination='AlphaCentauri', distance=12),\n",
       " ('Snowdin',\n",
       "  'Arbre'): Connection(origin='Snowdin', destination='Arbre', distance=129),\n",
       " ('Snowdin',\n",
       "  'Faerun'): Connection(origin='Snowdin', destination='Faerun', distance=60),\n",
       " ('Snowdin',\n",
       "  'Norrath'): Connection(origin='Snowdin', destination='Norrath', distance=75),\n",
       " ('Snowdin',\n",
       "  'Straylight'): Connection(origin='Snowdin', destination='Straylight', distance=99),\n",
       " ('Snowdin',\n",
       "  'Tambi'): Connection(origin='Snowdin', destination='Tambi', distance=15),\n",
       " ('Snowdin',\n",
       "  'Tristram'): Connection(origin='Snowdin', destination='Tristram', distance=103),\n",
       " ('Straylight',\n",
       "  'AlphaCentauri'): Connection(origin='Straylight', destination='AlphaCentauri', distance=91),\n",
       " ('Straylight',\n",
       "  'Arbre'): Connection(origin='Straylight', destination='Arbre', distance=40),\n",
       " ('Straylight',\n",
       "  'Faerun'): Connection(origin='Straylight', destination='Faerun', distance=67),\n",
       " ('Straylight',\n",
       "  'Norrath'): Connection(origin='Straylight', destination='Norrath', distance=54),\n",
       " ('Straylight',\n",
       "  'Snowdin'): Connection(origin='Straylight', destination='Snowdin', distance=99),\n",
       " ('Straylight',\n",
       "  'Tambi'): Connection(origin='Straylight', destination='Tambi', distance=70),\n",
       " ('Straylight',\n",
       "  'Tristram'): Connection(origin='Straylight', destination='Tristram', distance=97),\n",
       " ('Tambi',\n",
       "  'AlphaCentauri'): Connection(origin='Tambi', destination='AlphaCentauri', distance=18),\n",
       " ('Tambi',\n",
       "  'Arbre'): Connection(origin='Tambi', destination='Arbre', distance=53),\n",
       " ('Tambi',\n",
       "  'Faerun'): Connection(origin='Tambi', destination='Faerun', distance=71),\n",
       " ('Tambi',\n",
       "  'Norrath'): Connection(origin='Tambi', destination='Norrath', distance=82),\n",
       " ('Tambi',\n",
       "  'Snowdin'): Connection(origin='Tambi', destination='Snowdin', distance=15),\n",
       " ('Tambi',\n",
       "  'Straylight'): Connection(origin='Tambi', destination='Straylight', distance=70),\n",
       " ('Tambi',\n",
       "  'Tristram'): Connection(origin='Tambi', destination='Tristram', distance=49),\n",
       " ('Tristram',\n",
       "  'AlphaCentauri'): Connection(origin='Tristram', destination='AlphaCentauri', distance=118),\n",
       " ('Tristram',\n",
       "  'Arbre'): Connection(origin='Tristram', destination='Arbre', distance=122),\n",
       " ('Tristram',\n",
       "  'Faerun'): Connection(origin='Tristram', destination='Faerun', distance=58),\n",
       " ('Tristram',\n",
       "  'Norrath'): Connection(origin='Tristram', destination='Norrath', distance=142),\n",
       " ('Tristram',\n",
       "  'Snowdin'): Connection(origin='Tristram', destination='Snowdin', distance=103),\n",
       " ('Tristram',\n",
       "  'Straylight'): Connection(origin='Tristram', destination='Straylight', distance=97),\n",
       " ('Tristram',\n",
       "  'Tambi'): Connection(origin='Tristram', destination='Tambi', distance=49)}"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import namedtuple\n",
    "\n",
    "Connection = namedtuple('Connection', ['origin', 'destination', 'distance'])\n",
    "\n",
    "connections = {}\n",
    "\n",
    "for l in pi9.splitlines():\n",
    "    s = l.split(' ')\n",
    "    connections[(s[0], s[2])] = Connection(origin=s[0], destination=s[2], distance=int(s[4]))\n",
    "    connections[(s[2], s[0])] = Connection(origin=s[2], destination=s[0], distance=int(s[4]))\n",
    "connections"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'AlphaCentauri',\n",
       " 'Arbre',\n",
       " 'Faerun',\n",
       " 'Norrath',\n",
       " 'Snowdin',\n",
       " 'Straylight',\n",
       " 'Tambi',\n",
       " 'Tristram'}"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "towns = set([c[0] for c in connections] + [c[1] for c in connections])\n",
    "towns"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def viable(route):\n",
    "    return all((c in connections) for c in zip(route, route[1:]))        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "viable(['Faerun', 'Norrath', 'Tambi', 'Arbre'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def length(route):\n",
    "    return sum(connections[c].distance for c in zip(route, route[1:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "211"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "length(['Faerun', 'Norrath', 'Tambi'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def best(route1, route2):\n",
    "    if length(route1) < length(route2):\n",
    "        return route1\n",
    "    else:\n",
    "        return route2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def worst(route1, route2):\n",
    "    if length(route1) > length(route2):\n",
    "        return route1\n",
    "    else:\n",
    "        return route2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(('Norrath',\n",
       "  'Straylight',\n",
       "  'Arbre',\n",
       "  'Faerun',\n",
       "  'AlphaCentauri',\n",
       "  'Snowdin',\n",
       "  'Tambi',\n",
       "  'Tristram'),\n",
       " 207)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import itertools\n",
    "import functools\n",
    "\n",
    "possible_routes = filter(viable, [r for r in itertools.permutations(towns)])\n",
    "best_route = functools.reduce(best, possible_routes)\n",
    "best_route, length(best_route)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "40320"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(list(filter(viable, [r for r in itertools.permutations(towns)])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "ps = list(itertools.permutations(towns))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "40320"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(list(filter(viable, ps)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(('Straylight',\n",
       "  'Snowdin',\n",
       "  'Arbre',\n",
       "  'AlphaCentauri',\n",
       "  'Tristram',\n",
       "  'Norrath',\n",
       "  'Faerun',\n",
       "  'Tambi'),\n",
       " 804)"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "possible_routes = filter(viable, [r for r in itertools.permutations(towns)])\n",
    "worst_route = functools.reduce(worst, possible_routes)\n",
    "worst_route, length(worst_route)"
   ]
  },
  {
   "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
}