advent17.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "code",
   5    "execution_count": 1,
   6    "metadata": {
   7     "collapsed": false
   8    },
   9    "outputs": [
  10     {
  11      "data": {
  12       "text/plain": [
  13        "[50, 44, 11, 49, 42, 46, 18, 32, 26, 40, 21, 7, 18, 43, 10, 47, 36, 24, 22, 40]"
  14       ]
  15      },
  16      "execution_count": 1,
  17      "metadata": {},
  18      "output_type": "execute_result"
  19     }
  20    ],
  21    "source": [
  22     "containers = [int(c.strip()) for c in open('advent17.txt').readlines()]\n",
  23     "containers"
  24    ]
  25   },
  26   {
  27    "cell_type": "code",
  28    "execution_count": 7,
  29    "metadata": {
  30     "collapsed": true
  31    },
  32    "outputs": [],
  33    "source": [
  34     "target = 150"
  35    ]
  36   },
  37   {
  38    "cell_type": "code",
  39    "execution_count": 26,
  40    "metadata": {
  41     "collapsed": false
  42    },
  43    "outputs": [
  44     {
  45      "data": {
  46       "text/plain": [
  47        "654"
  48       ]
  49      },
  50      "execution_count": 26,
  51      "metadata": {},
  52      "output_type": "execute_result"
  53     }
  54    ],
  55    "source": [
  56     "partials = []\n",
  57     "for c in containers:\n",
  58     "    new_partials = []\n",
  59     "    for p in partials:\n",
  60     "        if sum(p) + c <= target:\n",
  61     "            new_partials += [[c] + p]\n",
  62     "        new_partials += [p]\n",
  63     "    if c <= target:\n",
  64     "        new_partials += [[c]]\n",
  65     "    partials = new_partials\n",
  66     "solutions = list(filter(lambda p: sum(p) == target, partials))\n",
  67     "len(solutions)"
  68    ]
  69   },
  70   {
  71    "cell_type": "code",
  72    "execution_count": 28,
  73    "metadata": {
  74     "collapsed": false
  75    },
  76    "outputs": [
  77     {
  78      "data": {
  79       "text/plain": [
  80        "4"
  81       ]
  82      },
  83      "execution_count": 28,
  84      "metadata": {},
  85      "output_type": "execute_result"
  86     }
  87    ],
  88    "source": [
  89     "shortest_solution = min(len(s) for s in solutions)\n",
  90     "shortest_solution"
  91    ]
  92   },
  93   {
  94    "cell_type": "code",
  95    "execution_count": 29,
  96    "metadata": {
  97     "collapsed": false,
  98     "scrolled": true
  99    },
 100    "outputs": [
 101     {
 102      "data": {
 103       "text/plain": [
 104        "[[7, 49, 44, 50],\n",
 105        " [10, 46, 44, 50],\n",
 106        " [24, 32, 44, 50],\n",
 107        " [40, 49, 11, 50],\n",
 108        " [40, 49, 11, 50],\n",
 109        " [47, 42, 11, 50],\n",
 110        " [43, 46, 11, 50],\n",
 111        " [40, 18, 42, 50],\n",
 112        " [40, 18, 42, 50],\n",
 113        " [26, 32, 42, 50],\n",
 114        " [18, 40, 42, 50],\n",
 115        " [40, 18, 42, 50],\n",
 116        " [22, 36, 42, 50],\n",
 117        " [36, 18, 46, 50],\n",
 118        " [22, 32, 46, 50],\n",
 119        " [47, 7, 46, 50],\n",
 120        " [36, 18, 46, 50],\n",
 121        " [47, 21, 32, 50],\n",
 122        " [24, 36, 40, 50],\n",
 123        " [36, 43, 21, 50],\n",
 124        " [47, 10, 43, 50],\n",
 125        " [40, 24, 36, 50],\n",
 126        " [46, 49, 11, 44],\n",
 127        " [36, 21, 49, 44],\n",
 128        " [47, 10, 49, 44],\n",
 129        " [18, 46, 42, 44],\n",
 130        " [18, 46, 42, 44],\n",
 131        " [24, 40, 42, 44],\n",
 132        " [43, 21, 42, 44],\n",
 133        " [40, 24, 42, 44],\n",
 134        " [24, 36, 46, 44],\n",
 135        " [40, 40, 26, 44],\n",
 136        " [47, 43, 49, 11],\n",
 137        " [43, 40, 18, 49],\n",
 138        " [40, 43, 18, 49],\n",
 139        " [36, 47, 18, 49],\n",
 140        " [43, 26, 32, 49],\n",
 141        " [22, 47, 32, 49],\n",
 142        " [40, 21, 40, 49],\n",
 143        " [43, 18, 40, 49],\n",
 144        " [40, 43, 18, 49],\n",
 145        " [36, 47, 18, 49],\n",
 146        " [22, 36, 43, 49],\n",
 147        " [36, 26, 46, 42],\n",
 148        " [22, 40, 46, 42],\n",
 149        " [40, 22, 46, 42],\n",
 150        " [47, 43, 18, 42],\n",
 151        " [36, 40, 32, 42],\n",
 152        " [40, 36, 32, 42],\n",
 153        " [47, 21, 40, 42],\n",
 154        " [40, 47, 21, 42],\n",
 155        " [47, 43, 18, 42],\n",
 156        " [43, 21, 40, 46],\n",
 157        " [40, 24, 40, 46],\n",
 158        " [40, 43, 21, 46],\n",
 159        " [36, 47, 21, 46],\n",
 160        " [24, 36, 47, 43]]"
 161       ]
 162      },
 163      "execution_count": 29,
 164      "metadata": {},
 165      "output_type": "execute_result"
 166     }
 167    ],
 168    "source": [
 169     "[s for s in solutions if len(s) == shortest_solution]"
 170    ]
 171   },
 172   {
 173    "cell_type": "code",
 174    "execution_count": 31,
 175    "metadata": {
 176     "collapsed": false
 177    },
 178    "outputs": [
 179     {
 180      "data": {
 181       "text/plain": [
 182        "57"
 183       ]
 184      },
 185      "execution_count": 31,
 186      "metadata": {},
 187      "output_type": "execute_result"
 188     }
 189    ],
 190    "source": [
 191     "len([s for s in solutions if len(s) == shortest_solution])"
 192    ]
 193   },
 194   {
 195    "cell_type": "code",
 196    "execution_count": 66,
 197    "metadata": {
 198     "collapsed": true
 199    },
 200    "outputs": [],
 201    "source": [
 202     "import itertools"
 203    ]
 204   },
 205   {
 206    "cell_type": "code",
 207    "execution_count": 63,
 208    "metadata": {
 209     "collapsed": false
 210    },
 211    "outputs": [],
 212    "source": [
 213     "def int_to_bitstring(i, l):\n",
 214     "    bitstring = []\n",
 215     "    for _ in range(l):\n",
 216     "        if i & 1:\n",
 217     "            bitstring.append(True)\n",
 218     "        else:\n",
 219     "            bitstring.append(False)\n",
 220     "        i >>= 1\n",
 221     "    return reversed(bitstring)"
 222    ]
 223   },
 224   {
 225    "cell_type": "code",
 226    "execution_count": 64,
 227    "metadata": {
 228     "collapsed": false
 229    },
 230    "outputs": [
 231     {
 232      "data": {
 233       "text/plain": [
 234        "[True, False, False, False, True, True, False, False]"
 235       ]
 236      },
 237      "execution_count": 64,
 238      "metadata": {},
 239      "output_type": "execute_result"
 240     }
 241    ],
 242    "source": [
 243     "list(int_to_bitstring(140, 8))"
 244    ]
 245   },
 246   {
 247    "cell_type": "code",
 248    "execution_count": 59,
 249    "metadata": {
 250     "collapsed": false
 251    },
 252    "outputs": [
 253     {
 254      "data": {
 255       "text/plain": [
 256        "[]"
 257       ]
 258      },
 259      "execution_count": 59,
 260      "metadata": {},
 261      "output_type": "execute_result"
 262     }
 263    ],
 264    "source": [
 265     "import itertools\n",
 266     "valids = []\n",
 267     "c_small = containers[:5]\n",
 268     "for i in range(2**len(c_small)):\n",
 269     "    mask = int_to_bitstring(i, len(c_small))\n",
 270     "    cs = list(itertools.compress(c_small, mask))\n",
 271     "    if sum(cs) == target:\n",
 272     "        valids += [cs]\n",
 273     "valids               "
 274    ]
 275   },
 276   {
 277    "cell_type": "code",
 278    "execution_count": 65,
 279    "metadata": {
 280     "collapsed": false
 281    },
 282    "outputs": [
 283     {
 284      "data": {
 285       "text/plain": [
 286        "654"
 287       ]
 288      },
 289      "execution_count": 65,
 290      "metadata": {},
 291      "output_type": "execute_result"
 292     }
 293    ],
 294    "source": [
 295     "import itertools\n",
 296     "valids = []\n",
 297     "for i in range(2**len(containers)):\n",
 298     "    mask = int_to_bitstring(i, len(containers))\n",
 299     "    cs = list(itertools.compress(containers, mask))\n",
 300     "    if sum(cs) == target:\n",
 301     "        valids += [cs]\n",
 302     "len(valids)"
 303    ]
 304   },
 305   {
 306    "cell_type": "code",
 307    "execution_count": null,
 308    "metadata": {
 309     "collapsed": true
 310    },
 311    "outputs": [],
 312    "source": []
 313   }
 314  ],
 315  "metadata": {
 316   "kernelspec": {
 317    "display_name": "Python 3",
 318    "language": "python",
 319    "name": "python3"
 320   },
 321   "language_info": {
 322    "codemirror_mode": {
 323     "name": "ipython",
 324     "version": 3
 325    },
 326    "file_extension": ".py",
 327    "mimetype": "text/x-python",
 328    "name": "python",
 329    "nbconvert_exporter": "python",
 330    "pygments_lexer": "ipython3",
 331    "version": "3.4.3"
 332   }
 333  },
 334  "nbformat": 4,
 335  "nbformat_minor": 0
 336 }