Done puzzle 64
[project-euler.git] / euler32.ipynb
1 {
2 "cells": [
3 {
4 "cell_type": "code",
5 "execution_count": 66,
6 "metadata": {
7 "collapsed": false
8 },
9 "outputs": [
10 {
11 "data": {
12 "text/plain": [
13 "true"
14 ]
15 },
16 "execution_count": 66,
17 "metadata": {},
18 "output_type": "execute_result"
19 }
20 ],
21 "source": [
22 "require 'set'\n",
23 "require 'awesome_print'"
24 ]
25 },
26 {
27 "cell_type": "code",
28 "execution_count": 2,
29 "metadata": {
30 "collapsed": false
31 },
32 "outputs": [
33 {
34 "data": {
35 "text/plain": [
36 "[1, 2, 3, 4, 5, 6, 7, 8, 9]"
37 ]
38 },
39 "execution_count": 2,
40 "metadata": {},
41 "output_type": "execute_result"
42 }
43 ],
44 "source": [
45 "digits = (1..9).to_a"
46 ]
47 },
48 {
49 "cell_type": "code",
50 "execution_count": 88,
51 "metadata": {
52 "collapsed": false
53 },
54 "outputs": [
55 {
56 "data": {
57 "text/plain": [
58 ":full_subbags"
59 ]
60 },
61 "execution_count": 88,
62 "metadata": {},
63 "output_type": "execute_result"
64 }
65 ],
66 "source": [
67 "class Array\n",
68 " def subbags(n)\n",
69 " return enum_for(:subbags, n) unless block_given?\n",
70 " if n == 1\n",
71 " yield [self]\n",
72 " else\n",
73 " (0..self.length).each do |i|\n",
74 " self.combination(i).each do |f|\n",
75 " (self - f).subbags(n-1).each do |r|\n",
76 " yield [f] + r\n",
77 " end\n",
78 " end\n",
79 " end\n",
80 " end\n",
81 " end\n",
82 " \n",
83 " def full_subbags(n)\n",
84 " return enum_for(:full_subbags, n) unless block_given?\n",
85 " self.subbags(n).select {|bags| bags.none? {|b| b.empty?}}.each do |bs|\n",
86 " yield bs\n",
87 " end\n",
88 " end\n",
89 "end"
90 ]
91 },
92 {
93 "cell_type": "code",
94 "execution_count": 89,
95 "metadata": {
96 "collapsed": false
97 },
98 "outputs": [
99 {
100 "name": "stdout",
101 "output_type": "stream",
102 "text": [
103 "[[1, 2, 3]]\n"
104 ]
105 }
106 ],
107 "source": [
108 "[1,2,3].subbags(1) {|i| puts i}"
109 ]
110 },
111 {
112 "cell_type": "code",
113 "execution_count": 90,
114 "metadata": {
115 "collapsed": false
116 },
117 "outputs": [
118 {
119 "data": {
120 "text/plain": [
121 "[[[1, 2, 3]]]"
122 ]
123 },
124 "execution_count": 90,
125 "metadata": {},
126 "output_type": "execute_result"
127 }
128 ],
129 "source": [
130 "[1,2,3].subbags(1).to_a"
131 ]
132 },
133 {
134 "cell_type": "code",
135 "execution_count": 91,
136 "metadata": {
137 "collapsed": false
138 },
139 "outputs": [
140 {
141 "name": "stdout",
142 "output_type": "stream",
143 "text": [
144 "[[], [1, 2, 3]]\n",
145 "[[1], [2, 3]]\n",
146 "[[2], [1, 3]]\n",
147 "[[3], [1, 2]]\n",
148 "[[1, 2], [3]]\n",
149 "[[1, 3], [2]]\n",
150 "[[2, 3], [1]]\n",
151 "[[1, 2, 3], []]\n"
152 ]
153 },
154 {
155 "data": {
156 "text/plain": [
157 "0..3"
158 ]
159 },
160 "execution_count": 91,
161 "metadata": {},
162 "output_type": "execute_result"
163 }
164 ],
165 "source": [
166 "[1,2,3].subbags(2) {|i| puts i}"
167 ]
168 },
169 {
170 "cell_type": "code",
171 "execution_count": 92,
172 "metadata": {
173 "collapsed": false
174 },
175 "outputs": [
176 {
177 "data": {
178 "text/plain": [
179 "[[[], [1, 2, 3]], [[1], [2, 3]], [[2], [1, 3]], [[3], [1, 2]], [[1, 2], [3]], [[1, 3], [2]], [[2, 3], [1]], [[1, 2, 3], []]]"
180 ]
181 },
182 "execution_count": 92,
183 "metadata": {},
184 "output_type": "execute_result"
185 }
186 ],
187 "source": [
188 "[1,2,3].subbags(2).to_a"
189 ]
190 },
191 {
192 "cell_type": "code",
193 "execution_count": 93,
194 "metadata": {
195 "collapsed": false
196 },
197 "outputs": [
198 {
199 "data": {
200 "text/plain": [
201 "8"
202 ]
203 },
204 "execution_count": 93,
205 "metadata": {},
206 "output_type": "execute_result"
207 }
208 ],
209 "source": [
210 "[1,2,3].subbags(2).to_a.length"
211 ]
212 },
213 {
214 "cell_type": "code",
215 "execution_count": 94,
216 "metadata": {
217 "collapsed": false
218 },
219 "outputs": [
220 {
221 "data": {
222 "text/plain": [
223 "[[[], [], [1, 2, 3]], [[], [1], [2, 3]], [[], [2], [1, 3]], [[], [3], [1, 2]], [[], [1, 2], [3]], [[], [1, 3], [2]], [[], [2, 3], [1]], [[], [1, 2, 3], []], [[1], [], [2, 3]], [[1], [2], [3]], [[1], [3], [2]], [[1], [2, 3], []], [[2], [], [1, 3]], [[2], [1], [3]], [[2], [3], [1]], [[2], [1, 3], []], [[3], [], [1, 2]], [[3], [1], [2]], [[3], [2], [1]], [[3], [1, 2], []], [[1, 2], [], [3]], [[1, 2], [3], []], [[1, 3], [], [2]], [[1, 3], [2], []], [[2, 3], [], [1]], [[2, 3], [1], []], [[1, 2, 3], [], []]]"
224 ]
225 },
226 "execution_count": 94,
227 "metadata": {},
228 "output_type": "execute_result"
229 }
230 ],
231 "source": [
232 "[1,2,3].subbags(3).to_a"
233 ]
234 },
235 {
236 "cell_type": "code",
237 "execution_count": 95,
238 "metadata": {
239 "collapsed": false
240 },
241 "outputs": [
242 {
243 "data": {
244 "text/plain": [
245 "27"
246 ]
247 },
248 "execution_count": 95,
249 "metadata": {},
250 "output_type": "execute_result"
251 }
252 ],
253 "source": [
254 "[1,2,3].subbags(3).to_a.length"
255 ]
256 },
257 {
258 "cell_type": "code",
259 "execution_count": 96,
260 "metadata": {
261 "collapsed": false
262 },
263 "outputs": [
264 {
265 "name": "stdout",
266 "output_type": "stream",
267 "text": [
268 "i: 0, f: []\n",
269 "i: 1, f: [1]\n",
270 "i: 1, f: [2]\n",
271 "i: 1, f: [3]\n",
272 "i: 2, f: [1, 2]\n",
273 "i: 2, f: [1, 3]\n",
274 "i: 2, f: [2, 3]\n",
275 "i: 3, f: [1, 2, 3]\n"
276 ]
277 },
278 {
279 "data": {
280 "text/plain": [
281 "0..3"
282 ]
283 },
284 "execution_count": 96,
285 "metadata": {},
286 "output_type": "execute_result"
287 }
288 ],
289 "source": [
290 "(0..[1,2,3].length).each do |i|\n",
291 " [1,2,3].combination(i).each do |f|\n",
292 " puts \"i: #{i}, f: #{f}\"\n",
293 " end\n",
294 "end"
295 ]
296 },
297 {
298 "cell_type": "code",
299 "execution_count": 97,
300 "metadata": {
301 "collapsed": false
302 },
303 "outputs": [
304 {
305 "data": {
306 "text/plain": [
307 "[[[1], [2], [3, 4]], [[1], [3], [2, 4]], [[1], [4], [2, 3]], [[1], [2, 3], [4]], [[1], [2, 4], [3]], [[1], [3, 4], [2]], [[2], [1], [3, 4]], [[2], [3], [1, 4]], [[2], [4], [1, 3]], [[2], [1, 3], [4]], [[2], [1, 4], [3]], [[2], [3, 4], [1]], [[3], [1], [2, 4]], [[3], [2], [1, 4]], [[3], [4], [1, 2]], [[3], [1, 2], [4]], [[3], [1, 4], [2]], [[3], [2, 4], [1]], [[4], [1], [2, 3]], [[4], [2], [1, 3]], [[4], [3], [1, 2]], [[4], [1, 2], [3]], [[4], [1, 3], [2]], [[4], [2, 3], [1]], [[1, 2], [3], [4]], [[1, 2], [4], [3]], [[1, 3], [2], [4]], [[1, 3], [4], [2]], [[1, 4], [2], [3]], [[1, 4], [3], [2]], [[2, 3], [1], [4]], [[2, 3], [4], [1]], [[2, 4], [1], [3]], [[2, 4], [3], [1]], [[3, 4], [1], [2]], [[3, 4], [2], [1]]]"
308 ]
309 },
310 "execution_count": 97,
311 "metadata": {},
312 "output_type": "execute_result"
313 }
314 ],
315 "source": [
316 "[1,2,3,4].full_subbags(3).to_a"
317 ]
318 },
319 {
320 "cell_type": "code",
321 "execution_count": 98,
322 "metadata": {
323 "collapsed": false
324 },
325 "outputs": [
326 {
327 "data": {
328 "text/plain": [
329 "18150"
330 ]
331 },
332 "execution_count": 98,
333 "metadata": {},
334 "output_type": "execute_result"
335 }
336 ],
337 "source": [
338 "digits.full_subbags(3).to_a.length"
339 ]
340 },
341 {
342 "cell_type": "code",
343 "execution_count": 78,
344 "metadata": {
345 "collapsed": false
346 },
347 "outputs": [
348 {
349 "data": {
350 "text/plain": [
351 ":euler_product"
352 ]
353 },
354 "execution_count": 78,
355 "metadata": {},
356 "output_type": "execute_result"
357 }
358 ],
359 "source": [
360 "def euler_product(subbags)\n",
361 " products = []\n",
362 " a, b, c = subbags\n",
363 " csort = c.sort\n",
364 " a.permutation.each do |ap|\n",
365 " an = ap.map {|d| d.to_s}.join.to_i\n",
366 " b.permutation.each do |bp|\n",
367 " bn = bp.map {|d| d.to_s}.join.to_i\n",
368 " cn = (an * bn)\n",
369 " cp = cn.to_s.split('').map {|d| d.to_i}\n",
370 " if cp.sort == csort\n",
371 " products << cn\n",
372 " end\n",
373 " end\n",
374 " end\n",
375 " products\n",
376 "end"
377 ]
378 },
379 {
380 "cell_type": "code",
381 "execution_count": 54,
382 "metadata": {
383 "collapsed": false
384 },
385 "outputs": [
386 {
387 "data": {
388 "text/plain": [
389 "123"
390 ]
391 },
392 "execution_count": 54,
393 "metadata": {},
394 "output_type": "execute_result"
395 }
396 ],
397 "source": [
398 "[1,2,3].map {|d| d.to_s}.join.to_i"
399 ]
400 },
401 {
402 "cell_type": "code",
403 "execution_count": 58,
404 "metadata": {
405 "collapsed": false
406 },
407 "outputs": [
408 {
409 "data": {
410 "text/plain": [
411 "[1, 2, 3]"
412 ]
413 },
414 "execution_count": 58,
415 "metadata": {},
416 "output_type": "execute_result"
417 }
418 ],
419 "source": [
420 "123.to_s.split('').map {|d| d.to_i}"
421 ]
422 },
423 {
424 "cell_type": "code",
425 "execution_count": 85,
426 "metadata": {
427 "collapsed": false,
428 "scrolled": true
429 },
430 "outputs": [
431 {
432 "data": {
433 "text/plain": [
434 "12"
435 ]
436 },
437 "execution_count": 85,
438 "metadata": {},
439 "output_type": "execute_result"
440 }
441 ],
442 "source": [
443 "[1,2,3,4].full_subbags(3).flat_map {|bs| euler_product bs}.to_set"
444 ]
445 },
446 {
447 "cell_type": "code",
448 "execution_count": 83,
449 "metadata": {
450 "collapsed": false
451 },
452 "outputs": [
453 {
454 "data": {
455 "text/plain": [
456 "[7254]"
457 ]
458 },
459 "execution_count": 83,
460 "metadata": {},
461 "output_type": "execute_result"
462 }
463 ],
464 "source": [
465 "euler_product([[3, 9], [1, 8, 6], [7, 2, 5, 4]])"
466 ]
467 },
468 {
469 "cell_type": "code",
470 "execution_count": 87,
471 "metadata": {
472 "collapsed": false,
473 "scrolled": true
474 },
475 "outputs": [
476 {
477 "data": {
478 "text/plain": [
479 "45228"
480 ]
481 },
482 "execution_count": 87,
483 "metadata": {},
484 "output_type": "execute_result"
485 }
486 ],
487 "source": [
488 "digits.full_subbags(3).flat_map {|bs| euler_product bs}.to_set.sum"
489 ]
490 },
491 {
492 "cell_type": "code",
493 "execution_count": null,
494 "metadata": {
495 "collapsed": true
496 },
497 "outputs": [],
498 "source": []
499 }
500 ],
501 "metadata": {
502 "kernelspec": {
503 "display_name": "Ruby 2.4.0",
504 "language": "ruby",
505 "name": "ruby"
506 },
507 "language_info": {
508 "file_extension": ".rb",
509 "mimetype": "application/x-ruby",
510 "name": "ruby",
511 "version": "2.4.0"
512 }
513 },
514 "nbformat": 4,
515 "nbformat_minor": 0
516 }