X-Git-Url: https://git.njae.me.uk/?p=advent-of-code-15.git;a=blobdiff_plain;f=advent19.ipynb;fp=advent19.ipynb;h=f0966902fe7d5c7d1ffc9ca72b38e6d0299fd790;hp=0000000000000000000000000000000000000000;hb=391798b6c4f79fe0631c8c29e698b6628cb8fbcf;hpb=b90db1964a6f86a9b412bc05b4819ef8c1340bc4 diff --git a/advent19.ipynb b/advent19.ipynb new file mode 100644 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 +}