13 "[50, 44, 11, 49, 42, 46, 18, 32, 26, 40, 21, 7, 18, 43, 10, 47, 36, 24, 22, 40]"
18 "output_type": "execute_result"
22 "containers = [int(c.strip()) for c in open('advent17.txt').readlines()]\n",
46 "output_type": "stream",
48 "100 loops, best of 3: 14.2 ms per loop\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",
61 " new_partials += [[c]]\n",
62 " partials += new_partials\n",
63 "solutions = list(filter(lambda p: sum(p) == target, partials))\n",
76 "output_type": "stream",
78 "1 loops, best of 3: 753 ms per loop\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",
91 " partials = [[c]] + partials\n",
92 "solutions = list(filter(lambda p: sum(p) == target, partials))\n",
98 "execution_count": 28,
109 "execution_count": 28,
111 "output_type": "execute_result"
115 "shortest_solution = min(len(s) for s in solutions)\n",
121 "execution_count": 29,
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",
189 "execution_count": 29,
191 "output_type": "execute_result"
195 "[s for s in solutions if len(s) == shortest_solution]"
200 "execution_count": 31,
211 "execution_count": 31,
213 "output_type": "execute_result"
217 "len([s for s in solutions if len(s) == shortest_solution])"
222 "execution_count": 9,
233 "execution_count": 10,
239 "def int_to_bitstring(i, l):\n",
241 " for _ in range(l):\n",
243 " bitstring.append(True)\n",
245 " bitstring.append(False)\n",
247 " return reversed(bitstring)"
252 "execution_count": 11,
260 "[True, False, False, False, True, True, False, False]"
263 "execution_count": 11,
265 "output_type": "execute_result"
269 "list(int_to_bitstring(140, 8))"
274 "execution_count": 12,
285 "execution_count": 12,
287 "output_type": "execute_result"
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",
303 "execution_count": 13,
310 "output_type": "stream",
312 "1 loops, best of 3: 4.41 s per loop\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",
329 "execution_count": null,
339 "display_name": "Python 3",
340 "language": "python",
348 "file_extension": ".py",
349 "mimetype": "text/x-python",
351 "nbconvert_exporter": "python",
352 "pygments_lexer": "ipython3",