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