{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "import re"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": 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": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pi19 = [l.strip() for l in open('advent19.txt').readlines()]\n",
    "pi19"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": 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": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rules = [r.split(' => ') for r in pi19 if '=>' in r]\n",
    "rules"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'CRnSiRnCaPTiMgYCaPTiRnFArSiThFArCaSiThSiThPBCaCaSiRnSiRnTiTiMgArPBCaPMgYPTiRnFArFArCaSiRnBPMgArPRnCaPTiRnFArCaSiThCaCaFArPBCaCaPTiTiRnFArCaSiRnSiAlYSiThRnFArArCaSiRnBFArCaCaSiRnSiThCaCaCaFYCaPTiBCaSiThCaSiThPMgArSiRnCaPBFYCaCaFArCaCaCaCaSiThCaSiRnPRnFArPBSiThPRnFArSiRnMgArCaFYFArCaSiRnSiAlArTiTiTiTiTiTiTiRnPMgArPTiTiTiBSiRnSiAlArTiTiRnPMgArCaFYBPBPTiRnSiRnMgArSiThCaFArCaSiThFArPRnFArCaSiRnTiBSiThSiRnSiAlYCaFArPRnFArSiThCaFArCaCaSiThCaCaCaSiRnPRnCaFArFYPMgArCaPBCaPBSiRnFYPBCaFArCaSiAl'"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "base = pi19[-1]\n",
    "base"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "set()"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "transformed = set([])\n",
    "transformed"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [],
   "source": [
    "transformed = set([])\n",
    "for r in rules:\n",
    "    for m in re.finditer(r[0], base):\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": 8,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "518"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(transformed)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "tags": []
   },
   "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": 14,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": 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": 15,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('e', 200)"
      ]
     },
     "execution_count": 15,
     "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": 11,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "317 ms ± 18.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\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": 12,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "53.5 ms ± 1.11 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\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": {
    "tags": []
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}