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