X-Git-Url: https://git.njae.me.uk/?p=advent-of-code-15.git;a=blobdiff_plain;f=advent17.ipynb;fp=advent17.ipynb;h=9e175afce84c6c0a918adde1a4eadfafd0f7299f;hp=0000000000000000000000000000000000000000;hb=39525ef9a82b9e7e738e6c13fcc2067e7a0818a4;hpb=16385fdc96184dca5cc78fca75a5842103ccdb47 diff --git a/advent17.ipynb b/advent17.ipynb new file mode 100644 index 0000000..9e175af --- /dev/null +++ b/advent17.ipynb @@ -0,0 +1,336 @@ +{ + "cells": [ + { + "cell_type": "code", + "execution_count": 1, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "[50, 44, 11, 49, 42, 46, 18, 32, 26, 40, 21, 7, 18, 43, 10, 47, 36, 24, 22, 40]" + ] + }, + "execution_count": 1, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "containers = [int(c.strip()) for c in open('advent17.txt').readlines()]\n", + "containers" + ] + }, + { + "cell_type": "code", + "execution_count": 7, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "target = 150" + ] + }, + { + "cell_type": "code", + "execution_count": 26, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "654" + ] + }, + "execution_count": 26, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "partials = []\n", + "for c in containers:\n", + " new_partials = []\n", + " for p in partials:\n", + " if sum(p) + c <= target:\n", + " new_partials += [[c] + p]\n", + " new_partials += [p]\n", + " if c <= target:\n", + " new_partials += [[c]]\n", + " partials = new_partials\n", + "solutions = list(filter(lambda p: sum(p) == target, partials))\n", + "len(solutions)" + ] + }, + { + "cell_type": "code", + "execution_count": 28, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "4" + ] + }, + "execution_count": 28, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "shortest_solution = min(len(s) for s in solutions)\n", + "shortest_solution" + ] + }, + { + "cell_type": "code", + "execution_count": 29, + "metadata": { + "collapsed": false, + "scrolled": true + }, + "outputs": [ + { + "data": { + "text/plain": [ + "[[7, 49, 44, 50],\n", + " [10, 46, 44, 50],\n", + " [24, 32, 44, 50],\n", + " [40, 49, 11, 50],\n", + " [40, 49, 11, 50],\n", + " [47, 42, 11, 50],\n", + " [43, 46, 11, 50],\n", + " [40, 18, 42, 50],\n", + " [40, 18, 42, 50],\n", + " [26, 32, 42, 50],\n", + " [18, 40, 42, 50],\n", + " [40, 18, 42, 50],\n", + " [22, 36, 42, 50],\n", + " [36, 18, 46, 50],\n", + " [22, 32, 46, 50],\n", + " [47, 7, 46, 50],\n", + " [36, 18, 46, 50],\n", + " [47, 21, 32, 50],\n", + " [24, 36, 40, 50],\n", + " [36, 43, 21, 50],\n", + " [47, 10, 43, 50],\n", + " [40, 24, 36, 50],\n", + " [46, 49, 11, 44],\n", + " [36, 21, 49, 44],\n", + " [47, 10, 49, 44],\n", + " [18, 46, 42, 44],\n", + " [18, 46, 42, 44],\n", + " [24, 40, 42, 44],\n", + " [43, 21, 42, 44],\n", + " [40, 24, 42, 44],\n", + " [24, 36, 46, 44],\n", + " [40, 40, 26, 44],\n", + " [47, 43, 49, 11],\n", + " [43, 40, 18, 49],\n", + " [40, 43, 18, 49],\n", + " [36, 47, 18, 49],\n", + " [43, 26, 32, 49],\n", + " [22, 47, 32, 49],\n", + " [40, 21, 40, 49],\n", + " [43, 18, 40, 49],\n", + " [40, 43, 18, 49],\n", + " [36, 47, 18, 49],\n", + " [22, 36, 43, 49],\n", + " [36, 26, 46, 42],\n", + " [22, 40, 46, 42],\n", + " [40, 22, 46, 42],\n", + " [47, 43, 18, 42],\n", + " [36, 40, 32, 42],\n", + " [40, 36, 32, 42],\n", + " [47, 21, 40, 42],\n", + " [40, 47, 21, 42],\n", + " [47, 43, 18, 42],\n", + " [43, 21, 40, 46],\n", + " [40, 24, 40, 46],\n", + " [40, 43, 21, 46],\n", + " [36, 47, 21, 46],\n", + " [24, 36, 47, 43]]" + ] + }, + "execution_count": 29, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "[s for s in solutions if len(s) == shortest_solution]" + ] + }, + { + "cell_type": "code", + "execution_count": 31, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "57" + ] + }, + "execution_count": 31, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "len([s for s in solutions if len(s) == shortest_solution])" + ] + }, + { + "cell_type": "code", + "execution_count": 66, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "import itertools" + ] + }, + { + "cell_type": "code", + "execution_count": 63, + "metadata": { + "collapsed": false + }, + "outputs": [], + "source": [ + "def int_to_bitstring(i, l):\n", + " bitstring = []\n", + " for _ in range(l):\n", + " if i & 1:\n", + " bitstring.append(True)\n", + " else:\n", + " bitstring.append(False)\n", + " i >>= 1\n", + " return reversed(bitstring)" + ] + }, + { + "cell_type": "code", + "execution_count": 64, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "[True, False, False, False, True, True, False, False]" + ] + }, + "execution_count": 64, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "list(int_to_bitstring(140, 8))" + ] + }, + { + "cell_type": "code", + "execution_count": 59, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "[]" + ] + }, + "execution_count": 59, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "import itertools\n", + "valids = []\n", + "c_small = containers[:5]\n", + "for i in range(2**len(c_small)):\n", + " mask = int_to_bitstring(i, len(c_small))\n", + " cs = list(itertools.compress(c_small, mask))\n", + " if sum(cs) == target:\n", + " valids += [cs]\n", + "valids " + ] + }, + { + "cell_type": "code", + "execution_count": 65, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "654" + ] + }, + "execution_count": 65, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "import itertools\n", + "valids = []\n", + "for i in range(2**len(containers)):\n", + " mask = int_to_bitstring(i, len(containers))\n", + " cs = list(itertools.compress(containers, mask))\n", + " if sum(cs) == target:\n", + " valids += [cs]\n", + "len(valids)" + ] + }, + { + "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 +}