--- /dev/null
+{
+ "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
+}
projects / advent-of-code-15.git / blobdiff