Day 19 done

diff --git a/SIGNED.md b/SIGNED.md
index f2a0403cee1f8a9004f5ee9fa5915bacab03963f..351850c3b98efc5fd57e37a742b97b6417ba886c 100644 (file)
--- a/SIGNED.md
+++ b/SIGNED.md
@@ -3,19 +3,19 @@
 -----BEGIN PGP SIGNATURE-----
 Version: GnuPG v2
 
-iQIcBAABCAAGBQJWc+s9AAoJEJPB2e07Pgbq/OAQAIyVBhzkraO7tanY5m2n73Kx
-9hks6rBycaaAHkUpR22SSHcCU6hO45cNT+9b2pgupLoKYQCiLrNq6cTjrACUAqX6
-UfVHZIjMwy8F5huYRTiQP2urMc4OaZ9GgZsr++oeCQW3DOty7jz+5It0uuw0BY4R
-ycb9if6XEXfezlqPw16uY7z35i+ZvS9gWfnWEJKTwFJ9i9Q02/mLtuUr97uLMTKv
-FusWDwXQEw0tmgsYb+BUCBPxBBehwdnqOwE/+F2WL6+IxOdKbGG8ZKupnPHMt5aK
-CDHlRBJBDcgeMwct5jlrk+7VrfSyNgPncYBKeYr5vl1jZDqzMES++n4M2CtYq/fM
-1BX6fAHbCUMVhK64jFriIiUCv4qB8CbaVDvro3Khgq5MHRXiTjI38c49n6xdV8c4
-6Dy/WADC0xFi9qJ/DZXRcb/owvmPu0mWpXz/+kfbjivnL9z1YzH2O5B6dAXyL3Mg
-Q/zdM0Z08HG38gcU6OqsaYTysu608gmSFI8SFAJYXHlMFevslHkOX2P78oRDRInK
-qxD25NRor/RfnIjrPSFqF4uLviE/Ybi46xwuqfFYDdlAHgGKoRjcbQrc5lmUkMXW
-r1HdMc7Dmiu2lfS0hS8YVhm2U1HiM7rmrZXl3TnAcNkOcHkIr81s0fXvNUe6rFwB
-XM0pbr/U1BOyM2++oJIX
-=bQXc
+iQIcBAABCAAGBQJWdZ3lAAoJEJPB2e07PgbqcnAP+gKgLPT4BvMRhVQfVYKzEdtq
++aVjWMr4mclxye5eYm4h9JNV8iXivPtLti0/eJ8wftb6VrakEvJrcTl8Q7yDRk3u
+rerKYL7VmNBl2NeWgVfkr9LLULLL4N6nBb6u4eXFwlO/CMjw13vCTbM8TmW06qk2
+ca3mBocIWy3eG10TO9TChJA6d3DV66d6ezvUlHL+oduZwYneHVjUvkdMaj/KK4ug
+/YCOejqo0gfMINChy/HhyRJj7jDhOkaivnrdx3++61GORKSi1p/vf+3wsuM739kr
+4wS+kFtKhVABvGBHqyUSXf6YTG8mPgbLeeZFIxF/dVtcq2TlHJ8gVPoOLPy3JDME
+1TMIKjnyKieD7m0FUC0XJe6yPmRjSublj5MtC7F2nSb+Xdq5CqEHHD20kAnAJm/q
+0ceMy12H4Jpko4RXoX1iKY02qWZFRhH1UdwWTk7ZBrXVqgJ6z2SIcsI439Ximmd2
+5PGP9+yNg5Ijfig0LZgO/9o/5KjdXqb3kfHWAvKP1eEpx1h4+iphppwLYVSluuVi
++I8cAvOEs64PmZ6Vg7Mu7Rzov+RkEdtVgRw2uUYDmS1URQN3I+NqGriDgL5mn2Lo
+EXGLoiXUaiB49HikWm//K7mWfW7tJlJvL/Sz54bBhi4LBcq9CfNt3R3RnafMkToW
+F1TvlM9fPgMHVG76U94S
+=4ntN
 -----END PGP SIGNATURE-----
 
 ```
@@ -86,6 +86,8 @@ size    exec  file                        contents
 59              advent17.txt              9ea23339652ff398a7c97d7a7303ab2deee04c3e23a6c599106d65b6b89e52df
 11716           advent18.ipynb            dab604f208f0ded7134dbebe2b04c56435187e5b37ab318953b675f9c96c0d6a
 10099           advent18.txt              23d697796dfa397e22b925f850cf5a269802e307753a7a9a26e26ed7350a56a2
+9745            advent19.ipynb            858c65e798916dd00403762a01ba6b3a55348f20e8ac927b52e700aa3cd9c073
+968             advent19.txt              eb333fc1d3ec41e3b9b22096e838fe860fbc6667068129996cae3cd3483dd9e7
 ```
 
 #### Ignore

diff --git a/advent19.ipynb b/advent19.ipynb
new file mode 100644 (file)
index 0000000..f096690
--- /dev/null
+++ b/advent19.ipynb
@@ -0,0 +1,403 @@
+{
+ "cells": [
+  {
+   "cell_type": "code",
+   "execution_count": 10,
+   "metadata": {
+    "collapsed": true
+   },
+   "outputs": [],
+   "source": [
+    "import re"
+   ]
+  },
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "#Part 1"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 1,
+   "metadata": {
+    "collapsed": false
+   },
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "['Al => ThF',\n",
+       " 'Al => ThRnFAr',\n",
+       " 'B => BCa',\n",
+       " 'B => TiB',\n",
+       " 'B => TiRnFAr',\n",
+       " 'Ca => CaCa',\n",
+       " 'Ca => PB',\n",
+       " 'Ca => PRnFAr',\n",
+       " 'Ca => SiRnFYFAr',\n",
+       " 'Ca => SiRnMgAr',\n",
+       " 'Ca => SiTh',\n",
+       " 'F => CaF',\n",
+       " 'F => PMg',\n",
+       " 'F => SiAl',\n",
+       " 'H => CRnAlAr',\n",
+       " 'H => CRnFYFYFAr',\n",
+       " 'H => CRnFYMgAr',\n",
+       " 'H => CRnMgYFAr',\n",
+       " 'H => HCa',\n",
+       " 'H => NRnFYFAr',\n",
+       " 'H => NRnMgAr',\n",
+       " 'H => NTh',\n",
+       " 'H => OB',\n",
+       " 'H => ORnFAr',\n",
+       " 'Mg => BF',\n",
+       " 'Mg => TiMg',\n",
+       " 'N => CRnFAr',\n",
+       " 'N => HSi',\n",
+       " 'O => CRnFYFAr',\n",
+       " 'O => CRnMgAr',\n",
+       " 'O => HP',\n",
+       " 'O => NRnFAr',\n",
+       " 'O => OTi',\n",
+       " 'P => CaP',\n",
+       " 'P => PTi',\n",
+       " 'P => SiRnFAr',\n",
+       " 'Si => CaSi',\n",
+       " 'Th => ThCa',\n",
+       " 'Ti => BP',\n",
+       " 'Ti => TiTi',\n",
+       " 'e => HF',\n",
+       " 'e => NAl',\n",
+       " 'e => OMg',\n",
+       " '',\n",
+       " 'CRnSiRnCaPTiMgYCaPTiRnFArSiThFArCaSiThSiThPBCaCaSiRnSiRnTiTiMgArPBCaPMgYPTiRnFArFArCaSiRnBPMgArPRnCaPTiRnFArCaSiThCaCaFArPBCaCaPTiTiRnFArCaSiRnSiAlYSiThRnFArArCaSiRnBFArCaCaSiRnSiThCaCaCaFYCaPTiBCaSiThCaSiThPMgArSiRnCaPBFYCaCaFArCaCaCaCaSiThCaSiRnPRnFArPBSiThPRnFArSiRnMgArCaFYFArCaSiRnSiAlArTiTiTiTiTiTiTiRnPMgArPTiTiTiBSiRnSiAlArTiTiRnPMgArCaFYBPBPTiRnSiRnMgArSiThCaFArCaSiThFArPRnFArCaSiRnTiBSiThSiRnSiAlYCaFArPRnFArSiThCaFArCaCaSiThCaCaCaSiRnPRnCaFArFYPMgArCaPBCaPBSiRnFYPBCaFArCaSiAl']"
+      ]
+     },
+     "execution_count": 1,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "pi19 = [l.strip() for l in open('advent19.txt').readlines()]\n",
+    "pi19"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 2,
+   "metadata": {
+    "collapsed": false
+   },
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "[['Al', 'ThF'],\n",
+       " ['Al', 'ThRnFAr'],\n",
+       " ['B', 'BCa'],\n",
+       " ['B', 'TiB'],\n",
+       " ['B', 'TiRnFAr'],\n",
+       " ['Ca', 'CaCa'],\n",
+       " ['Ca', 'PB'],\n",
+       " ['Ca', 'PRnFAr'],\n",
+       " ['Ca', 'SiRnFYFAr'],\n",
+       " ['Ca', 'SiRnMgAr'],\n",
+       " ['Ca', 'SiTh'],\n",
+       " ['F', 'CaF'],\n",
+       " ['F', 'PMg'],\n",
+       " ['F', 'SiAl'],\n",
+       " ['H', 'CRnAlAr'],\n",
+       " ['H', 'CRnFYFYFAr'],\n",
+       " ['H', 'CRnFYMgAr'],\n",
+       " ['H', 'CRnMgYFAr'],\n",
+       " ['H', 'HCa'],\n",
+       " ['H', 'NRnFYFAr'],\n",
+       " ['H', 'NRnMgAr'],\n",
+       " ['H', 'NTh'],\n",
+       " ['H', 'OB'],\n",
+       " ['H', 'ORnFAr'],\n",
+       " ['Mg', 'BF'],\n",
+       " ['Mg', 'TiMg'],\n",
+       " ['N', 'CRnFAr'],\n",
+       " ['N', 'HSi'],\n",
+       " ['O', 'CRnFYFAr'],\n",
+       " ['O', 'CRnMgAr'],\n",
+       " ['O', 'HP'],\n",
+       " ['O', 'NRnFAr'],\n",
+       " ['O', 'OTi'],\n",
+       " ['P', 'CaP'],\n",
+       " ['P', 'PTi'],\n",
+       " ['P', 'SiRnFAr'],\n",
+       " ['Si', 'CaSi'],\n",
+       " ['Th', 'ThCa'],\n",
+       " ['Ti', 'BP'],\n",
+       " ['Ti', 'TiTi'],\n",
+       " ['e', 'HF'],\n",
+       " ['e', 'NAl'],\n",
+       " ['e', 'OMg']]"
+      ]
+     },
+     "execution_count": 2,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "rules = [r.split(' => ') for r in pi19 if '=>' in r]\n",
+    "rules"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 8,
+   "metadata": {
+    "collapsed": false
+   },
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "'CRnSiRnCaPTiMgYCaPTiRnFArSiThFArCaSiThSiThPBCaCaSiRnSiRnTiTiMgArPBCaPMgYPTiRnFArFArCaSiRnBPMgArPRnCaPTiRnFArCaSiThCaCaFArPBCaCaPTiTiRnFArCaSiRnSiAlYSiThRnFArArCaSiRnBFArCaCaSiRnSiThCaCaCaFYCaPTiBCaSiThCaSiThPMgArSiRnCaPBFYCaCaFArCaCaCaCaSiThCaSiRnPRnFArPBSiThPRnFArSiRnMgArCaFYFArCaSiRnSiAlArTiTiTiTiTiTiTiRnPMgArPTiTiTiBSiRnSiAlArTiTiRnPMgArCaFYBPBPTiRnSiRnMgArSiThCaFArCaSiThFArPRnFArCaSiRnTiBSiThSiRnSiAlYCaFArPRnFArSiThCaFArCaCaSiThCaCaCaSiRnPRnCaFArFYPMgArCaPBCaPBSiRnFYPBCaFArCaSiAl'"
+      ]
+     },
+     "execution_count": 8,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "base = pi19[-1]\n",
+    "base"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 5,
+   "metadata": {
+    "collapsed": false
+   },
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "set()"
+      ]
+     },
+     "execution_count": 5,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "transformed = set([])\n",
+    "transformed"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 18,
+   "metadata": {
+    "collapsed": false
+   },
+   "outputs": [],
+   "source": [
+    "transformed = set([])\n",
+    "for r in rules:\n",
+    "    for m in re.finditer(r[0], target):\n",
+    "        t = base[:m.start(0)] + r[1] + base[m.end(0):]\n",
+    "        # print(t, m.start(0), m.end(0))\n",
+    "        transformed.update([t])"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 19,
+   "metadata": {
+    "collapsed": false
+   },
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "518"
+      ]
+     },
+     "execution_count": 19,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "len(transformed)"
+   ]
+  },
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "#Part 2"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 48,
+   "metadata": {
+    "collapsed": true
+   },
+   "outputs": [],
+   "source": [
+    "def reductions(rule, molecule):\n",
+    "    return [molecule[:m.start(0)] + rule[0] + molecule[m.end(0):]\n",
+    "                for m in re.finditer(rule[1], molecule)]"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 76,
+   "metadata": {
+    "collapsed": false
+   },
+   "outputs": [],
+   "source": [
+    "#This is infeasible\n",
+    "\n",
+    "#agenda = [(base, 0)]\n",
+    "#closed_set = set()\n",
+    "\n",
+    "#while agenda[0][0] != 'e':\n",
+    "#    # print(len(agenda), len(agenda[0][0]))\n",
+    "#    current_m, current_c = agenda[0]\n",
+    "#    if current_m in closed_set:\n",
+    "#        agenda = agenda[1:]\n",
+    "#    else:\n",
+    "#        closed_set.update(current_m)\n",
+    "#        new_molecules = [(reduced, current_c + 1) for r in rules for reduced in reductions(r, current_m)]\n",
+    "#        agenda = agenda[1:] + new_molecules\n",
+    "#agenda[0]"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 75,
+   "metadata": {
+    "collapsed": false
+   },
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "('e', 200)"
+      ]
+     },
+     "execution_count": 75,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "agenda = [(base, 0)]\n",
+    "\n",
+    "while agenda[0][0] != 'e':\n",
+    "    # print(len(agenda), len(agenda[0][0]))\n",
+    "    current_m, current_c = agenda[0]\n",
+    "    new_molecules = [(reduced, current_c + 1) \n",
+    "                     for r in rules \n",
+    "                     for reduced in reductions(r, current_m)]\n",
+    "    agenda = new_molecules + agenda[1:]\n",
+    "agenda[0]"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 73,
+   "metadata": {
+    "collapsed": false
+   },
+   "outputs": [
+    {
+     "name": "stdout",
+     "output_type": "stream",
+     "text": [
+      "1 loops, best of 3: 281 ms per loop\n"
+     ]
+    }
+   ],
+   "source": [
+    "%%timeit\n",
+    "\n",
+    "agenda = [(base, 0)]\n",
+    "\n",
+    "while agenda[0][0] != 'e':\n",
+    "    # print(len(agenda), len(agenda[0][0]))\n",
+    "    current_m, current_c = agenda[0]\n",
+    "    new_molecules = [(reduced, current_c + 1) for r in rules for reduced in reductions(r, current_m)]\n",
+    "    agenda = sorted(agenda[1:] + new_molecules,\n",
+    "                   key=lambda m: len(m[0]))\n",
+    "agenda[0]"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 74,
+   "metadata": {
+    "collapsed": false
+   },
+   "outputs": [
+    {
+     "name": "stdout",
+     "output_type": "stream",
+     "text": [
+      "10 loops, best of 3: 44.4 ms per loop\n"
+     ]
+    }
+   ],
+   "source": [
+    "%%timeit\n",
+    "\n",
+    "agenda = [(base, 0)]\n",
+    "\n",
+    "while agenda[0][0] != 'e':\n",
+    "    # print(len(agenda), len(agenda[0][0]))\n",
+    "    current_m, current_c = agenda[0]\n",
+    "    new_molecules = [(reduced, current_c + 1) \n",
+    "                     for r in rules \n",
+    "                     for reduced in reductions(r, current_m)]\n",
+    "    agenda = new_molecules + agenda[1:]\n",
+    "agenda[0]"
+   ]
+  },
+  {
+   "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
+}

diff --git a/advent19.txt b/advent19.txt
new file mode 100644 (file)
index 0000000..b0515c0
--- /dev/null
+++ b/advent19.txt
@@ -0,0 +1,45 @@
+Al => ThF
+Al => ThRnFAr
+B => BCa
+B => TiB
+B => TiRnFAr
+Ca => CaCa
+Ca => PB
+Ca => PRnFAr
+Ca => SiRnFYFAr
+Ca => SiRnMgAr
+Ca => SiTh
+F => CaF
+F => PMg
+F => SiAl
+H => CRnAlAr
+H => CRnFYFYFAr
+H => CRnFYMgAr
+H => CRnMgYFAr
+H => HCa
+H => NRnFYFAr
+H => NRnMgAr
+H => NTh
+H => OB
+H => ORnFAr
+Mg => BF
+Mg => TiMg
+N => CRnFAr
+N => HSi
+O => CRnFYFAr
+O => CRnMgAr
+O => HP
+O => NRnFAr
+O => OTi
+P => CaP
+P => PTi
+P => SiRnFAr
+Si => CaSi
+Th => ThCa
+Ti => BP
+Ti => TiTi
+e => HF
+e => NAl
+e => OMg
+
+CRnSiRnCaPTiMgYCaPTiRnFArSiThFArCaSiThSiThPBCaCaSiRnSiRnTiTiMgArPBCaPMgYPTiRnFArFArCaSiRnBPMgArPRnCaPTiRnFArCaSiThCaCaFArPBCaCaPTiTiRnFArCaSiRnSiAlYSiThRnFArArCaSiRnBFArCaCaSiRnSiThCaCaCaFYCaPTiBCaSiThCaSiThPMgArSiRnCaPBFYCaCaFArCaCaCaCaSiThCaSiRnPRnFArPBSiThPRnFArSiRnMgArCaFYFArCaSiRnSiAlArTiTiTiTiTiTiTiRnPMgArPTiTiTiBSiRnSiAlArTiTiRnPMgArCaFYBPBPTiRnSiRnMgArSiThCaFArCaSiThFArPRnFArCaSiRnTiBSiThSiRnSiAlYCaFArPRnFArSiThCaFArCaCaSiThCaCaCaSiRnPRnCaFArFYPMgArCaPBCaPBSiRnFYPBCaFArCaSiAl