advent19.ipynb

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