{
 "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": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "target = 150"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100 loops, best of 3: 14.2 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "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",
    "    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": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loops, best of 3: 753 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "partials = []\n",
    "for c in containers:\n",
    "    new_partials = []\n",
    "    for p in partials:\n",
    "        if sum(p) + c <= target:\n",
    "            partials = [[c] + p] + partials\n",
    "    if c <= target:\n",
    "        partials = [[c]] + 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": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import itertools"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "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": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[True, False, False, False, True, True, False, False]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(int_to_bitstring(140, 8))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "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": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loops, best of 3: 4.41 s per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\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
}