From 391798b6c4f79fe0631c8c29e698b6628cb8fbcf Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Sat, 19 Dec 2015 18:11:40 +0000 Subject: [PATCH] Day 19 done --- SIGNED.md | 28 ++-- advent19.ipynb | 403 +++++++++++++++++++++++++++++++++++++++++++++++++ advent19.txt | 45 ++++++ 3 files changed, 463 insertions(+), 13 deletions(-) create mode 100644 advent19.ipynb create mode 100644 advent19.txt diff --git a/SIGNED.md b/SIGNED.md index f2a0403..351850c 100644 --- 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 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 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 -- 2.34.1