advent19.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "code",
   5    "execution_count": 10,
   6    "metadata": {
   7     "collapsed": true
   8    },
   9    "outputs": [],
  10    "source": [
  11     "import re"
  12    ]
  13   },
  14   {
  15    "cell_type": "markdown",
  16    "metadata": {},
  17    "source": [
  18     "#Part 1"
  19    ]
  20   },
  21   {
  22    "cell_type": "code",
  23    "execution_count": 1,
  24    "metadata": {
  25     "collapsed": false
  26    },
  27    "outputs": [
  28     {
  29      "data": {
  30       "text/plain": [
  31        "['Al => ThF',\n",
  32        " 'Al => ThRnFAr',\n",
  33        " 'B => BCa',\n",
  34        " 'B => TiB',\n",
  35        " 'B => TiRnFAr',\n",
  36        " 'Ca => CaCa',\n",
  37        " 'Ca => PB',\n",
  38        " 'Ca => PRnFAr',\n",
  39        " 'Ca => SiRnFYFAr',\n",
  40        " 'Ca => SiRnMgAr',\n",
  41        " 'Ca => SiTh',\n",
  42        " 'F => CaF',\n",
  43        " 'F => PMg',\n",
  44        " 'F => SiAl',\n",
  45        " 'H => CRnAlAr',\n",
  46        " 'H => CRnFYFYFAr',\n",
  47        " 'H => CRnFYMgAr',\n",
  48        " 'H => CRnMgYFAr',\n",
  49        " 'H => HCa',\n",
  50        " 'H => NRnFYFAr',\n",
  51        " 'H => NRnMgAr',\n",
  52        " 'H => NTh',\n",
  53        " 'H => OB',\n",
  54        " 'H => ORnFAr',\n",
  55        " 'Mg => BF',\n",
  56        " 'Mg => TiMg',\n",
  57        " 'N => CRnFAr',\n",
  58        " 'N => HSi',\n",
  59        " 'O => CRnFYFAr',\n",
  60        " 'O => CRnMgAr',\n",
  61        " 'O => HP',\n",
  62        " 'O => NRnFAr',\n",
  63        " 'O => OTi',\n",
  64        " 'P => CaP',\n",
  65        " 'P => PTi',\n",
  66        " 'P => SiRnFAr',\n",
  67        " 'Si => CaSi',\n",
  68        " 'Th => ThCa',\n",
  69        " 'Ti => BP',\n",
  70        " 'Ti => TiTi',\n",
  71        " 'e => HF',\n",
  72        " 'e => NAl',\n",
  73        " 'e => OMg',\n",
  74        " '',\n",
  75        " 'CRnSiRnCaPTiMgYCaPTiRnFArSiThFArCaSiThSiThPBCaCaSiRnSiRnTiTiMgArPBCaPMgYPTiRnFArFArCaSiRnBPMgArPRnCaPTiRnFArCaSiThCaCaFArPBCaCaPTiTiRnFArCaSiRnSiAlYSiThRnFArArCaSiRnBFArCaCaSiRnSiThCaCaCaFYCaPTiBCaSiThCaSiThPMgArSiRnCaPBFYCaCaFArCaCaCaCaSiThCaSiRnPRnFArPBSiThPRnFArSiRnMgArCaFYFArCaSiRnSiAlArTiTiTiTiTiTiTiRnPMgArPTiTiTiBSiRnSiAlArTiTiRnPMgArCaFYBPBPTiRnSiRnMgArSiThCaFArCaSiThFArPRnFArCaSiRnTiBSiThSiRnSiAlYCaFArPRnFArSiThCaFArCaCaSiThCaCaCaSiRnPRnCaFArFYPMgArCaPBCaPBSiRnFYPBCaFArCaSiAl']"
  76       ]
  77      },
  78      "execution_count": 1,
  79      "metadata": {},
  80      "output_type": "execute_result"
  81     }
  82    ],
  83    "source": [
  84     "pi19 = [l.strip() for l in open('advent19.txt').readlines()]\n",
  85     "pi19"
  86    ]
  87   },
  88   {
  89    "cell_type": "code",
  90    "execution_count": 2,
  91    "metadata": {
  92     "collapsed": false
  93    },
  94    "outputs": [
  95     {
  96      "data": {
  97       "text/plain": [
  98        "[['Al', 'ThF'],\n",
  99        " ['Al', 'ThRnFAr'],\n",
 100        " ['B', 'BCa'],\n",
 101        " ['B', 'TiB'],\n",
 102        " ['B', 'TiRnFAr'],\n",
 103        " ['Ca', 'CaCa'],\n",
 104        " ['Ca', 'PB'],\n",
 105        " ['Ca', 'PRnFAr'],\n",
 106        " ['Ca', 'SiRnFYFAr'],\n",
 107        " ['Ca', 'SiRnMgAr'],\n",
 108        " ['Ca', 'SiTh'],\n",
 109        " ['F', 'CaF'],\n",
 110        " ['F', 'PMg'],\n",
 111        " ['F', 'SiAl'],\n",
 112        " ['H', 'CRnAlAr'],\n",
 113        " ['H', 'CRnFYFYFAr'],\n",
 114        " ['H', 'CRnFYMgAr'],\n",
 115        " ['H', 'CRnMgYFAr'],\n",
 116        " ['H', 'HCa'],\n",
 117        " ['H', 'NRnFYFAr'],\n",
 118        " ['H', 'NRnMgAr'],\n",
 119        " ['H', 'NTh'],\n",
 120        " ['H', 'OB'],\n",
 121        " ['H', 'ORnFAr'],\n",
 122        " ['Mg', 'BF'],\n",
 123        " ['Mg', 'TiMg'],\n",
 124        " ['N', 'CRnFAr'],\n",
 125        " ['N', 'HSi'],\n",
 126        " ['O', 'CRnFYFAr'],\n",
 127        " ['O', 'CRnMgAr'],\n",
 128        " ['O', 'HP'],\n",
 129        " ['O', 'NRnFAr'],\n",
 130        " ['O', 'OTi'],\n",
 131        " ['P', 'CaP'],\n",
 132        " ['P', 'PTi'],\n",
 133        " ['P', 'SiRnFAr'],\n",
 134        " ['Si', 'CaSi'],\n",
 135        " ['Th', 'ThCa'],\n",
 136        " ['Ti', 'BP'],\n",
 137        " ['Ti', 'TiTi'],\n",
 138        " ['e', 'HF'],\n",
 139        " ['e', 'NAl'],\n",
 140        " ['e', 'OMg']]"
 141       ]
 142      },
 143      "execution_count": 2,
 144      "metadata": {},
 145      "output_type": "execute_result"
 146     }
 147    ],
 148    "source": [
 149     "rules = [r.split(' => ') for r in pi19 if '=>' in r]\n",
 150     "rules"
 151    ]
 152   },
 153   {
 154    "cell_type": "code",
 155    "execution_count": 8,
 156    "metadata": {
 157     "collapsed": false
 158    },
 159    "outputs": [
 160     {
 161      "data": {
 162       "text/plain": [
 163        "'CRnSiRnCaPTiMgYCaPTiRnFArSiThFArCaSiThSiThPBCaCaSiRnSiRnTiTiMgArPBCaPMgYPTiRnFArFArCaSiRnBPMgArPRnCaPTiRnFArCaSiThCaCaFArPBCaCaPTiTiRnFArCaSiRnSiAlYSiThRnFArArCaSiRnBFArCaCaSiRnSiThCaCaCaFYCaPTiBCaSiThCaSiThPMgArSiRnCaPBFYCaCaFArCaCaCaCaSiThCaSiRnPRnFArPBSiThPRnFArSiRnMgArCaFYFArCaSiRnSiAlArTiTiTiTiTiTiTiRnPMgArPTiTiTiBSiRnSiAlArTiTiRnPMgArCaFYBPBPTiRnSiRnMgArSiThCaFArCaSiThFArPRnFArCaSiRnTiBSiThSiRnSiAlYCaFArPRnFArSiThCaFArCaCaSiThCaCaCaSiRnPRnCaFArFYPMgArCaPBCaPBSiRnFYPBCaFArCaSiAl'"
 164       ]
 165      },
 166      "execution_count": 8,
 167      "metadata": {},
 168      "output_type": "execute_result"
 169     }
 170    ],
 171    "source": [
 172     "base = pi19[-1]\n",
 173     "base"
 174    ]
 175   },
 176   {
 177    "cell_type": "code",
 178    "execution_count": 5,
 179    "metadata": {
 180     "collapsed": false
 181    },
 182    "outputs": [
 183     {
 184      "data": {
 185       "text/plain": [
 186        "set()"
 187       ]
 188      },
 189      "execution_count": 5,
 190      "metadata": {},
 191      "output_type": "execute_result"
 192     }
 193    ],
 194    "source": [
 195     "transformed = set([])\n",
 196     "transformed"
 197    ]
 198   },
 199   {
 200    "cell_type": "code",
 201    "execution_count": 18,
 202    "metadata": {
 203     "collapsed": false
 204    },
 205    "outputs": [],
 206    "source": [
 207     "transformed = set([])\n",
 208     "for r in rules:\n",
 209     "    for m in re.finditer(r[0], target):\n",
 210     "        t = base[:m.start(0)] + r[1] + base[m.end(0):]\n",
 211     "        # print(t, m.start(0), m.end(0))\n",
 212     "        transformed.update([t])"
 213    ]
 214   },
 215   {
 216    "cell_type": "code",
 217    "execution_count": 19,
 218    "metadata": {
 219     "collapsed": false
 220    },
 221    "outputs": [
 222     {
 223      "data": {
 224       "text/plain": [
 225        "518"
 226       ]
 227      },
 228      "execution_count": 19,
 229      "metadata": {},
 230      "output_type": "execute_result"
 231     }
 232    ],
 233    "source": [
 234     "len(transformed)"
 235    ]
 236   },
 237   {
 238    "cell_type": "markdown",
 239    "metadata": {},
 240    "source": [
 241     "#Part 2"
 242    ]
 243   },
 244   {
 245    "cell_type": "code",
 246    "execution_count": 48,
 247    "metadata": {
 248     "collapsed": true
 249    },
 250    "outputs": [],
 251    "source": [
 252     "def reductions(rule, molecule):\n",
 253     "    return [molecule[:m.start(0)] + rule[0] + molecule[m.end(0):]\n",
 254     "                for m in re.finditer(rule[1], molecule)]"
 255    ]
 256   },
 257   {
 258    "cell_type": "code",
 259    "execution_count": 76,
 260    "metadata": {
 261     "collapsed": false
 262    },
 263    "outputs": [],
 264    "source": [
 265     "#This is infeasible\n",
 266     "\n",
 267     "#agenda = [(base, 0)]\n",
 268     "#closed_set = set()\n",
 269     "\n",
 270     "#while agenda[0][0] != 'e':\n",
 271     "#    # print(len(agenda), len(agenda[0][0]))\n",
 272     "#    current_m, current_c = agenda[0]\n",
 273     "#    if current_m in closed_set:\n",
 274     "#        agenda = agenda[1:]\n",
 275     "#    else:\n",
 276     "#        closed_set.update(current_m)\n",
 277     "#        new_molecules = [(reduced, current_c + 1) for r in rules for reduced in reductions(r, current_m)]\n",
 278     "#        agenda = agenda[1:] + new_molecules\n",
 279     "#agenda[0]"
 280    ]
 281   },
 282   {
 283    "cell_type": "code",
 284    "execution_count": 75,
 285    "metadata": {
 286     "collapsed": false
 287    },
 288    "outputs": [
 289     {
 290      "data": {
 291       "text/plain": [
 292        "('e', 200)"
 293       ]
 294      },
 295      "execution_count": 75,
 296      "metadata": {},
 297      "output_type": "execute_result"
 298     }
 299    ],
 300    "source": [
 301     "agenda = [(base, 0)]\n",
 302     "\n",
 303     "while agenda[0][0] != 'e':\n",
 304     "    # print(len(agenda), len(agenda[0][0]))\n",
 305     "    current_m, current_c = agenda[0]\n",
 306     "    new_molecules = [(reduced, current_c + 1) \n",
 307     "                     for r in rules \n",
 308     "                     for reduced in reductions(r, current_m)]\n",
 309     "    agenda = new_molecules + agenda[1:]\n",
 310     "agenda[0]"
 311    ]
 312   },
 313   {
 314    "cell_type": "code",
 315    "execution_count": 73,
 316    "metadata": {
 317     "collapsed": false
 318    },
 319    "outputs": [
 320     {
 321      "name": "stdout",
 322      "output_type": "stream",
 323      "text": [
 324       "1 loops, best of 3: 281 ms per loop\n"
 325      ]
 326     }
 327    ],
 328    "source": [
 329     "%%timeit\n",
 330     "\n",
 331     "agenda = [(base, 0)]\n",
 332     "\n",
 333     "while agenda[0][0] != 'e':\n",
 334     "    # print(len(agenda), len(agenda[0][0]))\n",
 335     "    current_m, current_c = agenda[0]\n",
 336     "    new_molecules = [(reduced, current_c + 1) for r in rules for reduced in reductions(r, current_m)]\n",
 337     "    agenda = sorted(agenda[1:] + new_molecules,\n",
 338     "                   key=lambda m: len(m[0]))\n",
 339     "agenda[0]"
 340    ]
 341   },
 342   {
 343    "cell_type": "code",
 344    "execution_count": 74,
 345    "metadata": {
 346     "collapsed": false
 347    },
 348    "outputs": [
 349     {
 350      "name": "stdout",
 351      "output_type": "stream",
 352      "text": [
 353       "10 loops, best of 3: 44.4 ms per loop\n"
 354      ]
 355     }
 356    ],
 357    "source": [
 358     "%%timeit\n",
 359     "\n",
 360     "agenda = [(base, 0)]\n",
 361     "\n",
 362     "while agenda[0][0] != 'e':\n",
 363     "    # print(len(agenda), len(agenda[0][0]))\n",
 364     "    current_m, current_c = agenda[0]\n",
 365     "    new_molecules = [(reduced, current_c + 1) \n",
 366     "                     for r in rules \n",
 367     "                     for reduced in reductions(r, current_m)]\n",
 368     "    agenda = new_molecules + agenda[1:]\n",
 369     "agenda[0]"
 370    ]
 371   },
 372   {
 373    "cell_type": "code",
 374    "execution_count": null,
 375    "metadata": {
 376     "collapsed": true
 377    },
 378    "outputs": [],
 379    "source": []
 380   }
 381  ],
 382  "metadata": {
 383   "kernelspec": {
 384    "display_name": "Python 3",
 385    "language": "python",
 386    "name": "python3"
 387   },
 388   "language_info": {
 389    "codemirror_mode": {
 390     "name": "ipython",
 391     "version": 3
 392    },
 393    "file_extension": ".py",
 394    "mimetype": "text/x-python",
 395    "name": "python",
 396    "nbconvert_exporter": "python",
 397    "pygments_lexer": "ipython3",
 398    "version": "3.4.3"
 399   }
 400  },
 401  "nbformat": 4,
 402  "nbformat_minor": 0
 403 }