Done puzzle 64
[project-euler.git] / euler51.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 "true"
14 ]
15 },
16 "execution_count": 1,
17 "metadata": {},
18 "output_type": "execute_result"
19 }
20 ],
21 "source": [
22 "load 'primes.rb'\n",
23 "load 'array-numbers.rb'\n",
24 "primes = Primes.instance\n",
25 "true"
26 ]
27 },
28 {
29 "cell_type": "code",
30 "execution_count": 2,
31 "metadata": {
32 "collapsed": false
33 },
34 "outputs": [
35 {
36 "data": {
37 "text/plain": [
38 ":replace"
39 ]
40 },
41 "execution_count": 2,
42 "metadata": {},
43 "output_type": "execute_result"
44 }
45 ],
46 "source": [
47 "def replace(num, positions, replace_with)\n",
48 " digits = num.to_digits\n",
49 " positions.each do |p|\n",
50 " digits[p] = replace_with\n",
51 " end\n",
52 " digits.to_i\n",
53 "end"
54 ]
55 },
56 {
57 "cell_type": "code",
58 "execution_count": 3,
59 "metadata": {
60 "collapsed": false
61 },
62 "outputs": [
63 {
64 "data": {
65 "text/plain": [
66 "56993"
67 ]
68 },
69 "execution_count": 3,
70 "metadata": {},
71 "output_type": "execute_result"
72 }
73 ],
74 "source": [
75 "replace(56003, [2, 3], 9)"
76 ]
77 },
78 {
79 "cell_type": "code",
80 "execution_count": 38,
81 "metadata": {
82 "collapsed": false
83 },
84 "outputs": [
85 {
86 "data": {
87 "text/plain": [
88 ":replace_in_positions"
89 ]
90 },
91 "execution_count": 38,
92 "metadata": {},
93 "output_type": "execute_result"
94 }
95 ],
96 "source": [
97 "def replace_in_positions(num, positions)\n",
98 " (0..9).map {|d| replace num, positions, d}.select {|n| n.to_digits.length == num.to_digits.length}\n",
99 "end"
100 ]
101 },
102 {
103 "cell_type": "code",
104 "execution_count": 5,
105 "metadata": {
106 "collapsed": false
107 },
108 "outputs": [
109 {
110 "data": {
111 "text/plain": [
112 "[56003, 56113, 56223, 56333, 56443, 56553, 56663, 56773, 56883, 56993]"
113 ]
114 },
115 "execution_count": 5,
116 "metadata": {},
117 "output_type": "execute_result"
118 }
119 ],
120 "source": [
121 "replace_in_positions(56003, [2, 3])"
122 ]
123 },
124 {
125 "cell_type": "code",
126 "execution_count": 50,
127 "metadata": {
128 "collapsed": false
129 },
130 "outputs": [
131 {
132 "data": {
133 "text/plain": [
134 ":count_primes_in_positions"
135 ]
136 },
137 "execution_count": 50,
138 "metadata": {},
139 "output_type": "execute_result"
140 }
141 ],
142 "source": [
143 "def count_primes_in_positions(num, positions)\n",
144 " others = replace_in_positions(num, positions).select {|n| n.prime?}\n",
145 " if others.include?(num)\n",
146 " others.length\n",
147 " else\n",
148 " 0\n",
149 " end\n",
150 "end"
151 ]
152 },
153 {
154 "cell_type": "code",
155 "execution_count": 52,
156 "metadata": {
157 "collapsed": false
158 },
159 "outputs": [
160 {
161 "data": {
162 "text/plain": [
163 "0"
164 ]
165 },
166 "execution_count": 52,
167 "metadata": {},
168 "output_type": "execute_result"
169 }
170 ],
171 "source": [
172 "count_primes_in_positions(56004, [2, 3])"
173 ]
174 },
175 {
176 "cell_type": "code",
177 "execution_count": 8,
178 "metadata": {
179 "collapsed": false
180 },
181 "outputs": [
182 {
183 "data": {
184 "text/plain": [
185 ":best_count_primes_r"
186 ]
187 },
188 "execution_count": 8,
189 "metadata": {},
190 "output_type": "execute_result"
191 }
192 ],
193 "source": [
194 "def best_count_primes_r(num, n_digits)\n",
195 " possibles = (0...num.to_digits.length).to_a\n",
196 " possibles.combination(n_digits).map {|ps| count_primes_in_positions(num, ps)}.max\n",
197 "end"
198 ]
199 },
200 {
201 "cell_type": "code",
202 "execution_count": 9,
203 "metadata": {
204 "collapsed": false
205 },
206 "outputs": [
207 {
208 "data": {
209 "text/plain": [
210 "7"
211 ]
212 },
213 "execution_count": 9,
214 "metadata": {},
215 "output_type": "execute_result"
216 }
217 ],
218 "source": [
219 "best_count_primes_r(56003, 2)"
220 ]
221 },
222 {
223 "cell_type": "code",
224 "execution_count": 15,
225 "metadata": {
226 "collapsed": false
227 },
228 "outputs": [
229 {
230 "data": {
231 "text/plain": [
232 "4"
233 ]
234 },
235 "execution_count": 15,
236 "metadata": {},
237 "output_type": "execute_result"
238 }
239 ],
240 "source": [
241 "best_count_primes_r(3, 1)"
242 ]
243 },
244 {
245 "cell_type": "code",
246 "execution_count": 18,
247 "metadata": {
248 "collapsed": false
249 },
250 "outputs": [
251 {
252 "data": {
253 "text/plain": [
254 ":best_count_primes"
255 ]
256 },
257 "execution_count": 18,
258 "metadata": {},
259 "output_type": "execute_result"
260 }
261 ],
262 "source": [
263 "def best_count_primes(num)\n",
264 " replacements = (1..num.to_digits.length).to_a\n",
265 " replacements.map {|n| best_count_primes_r(num, n)}.max\n",
266 "end"
267 ]
268 },
269 {
270 "cell_type": "code",
271 "execution_count": 21,
272 "metadata": {
273 "collapsed": false
274 },
275 "outputs": [
276 {
277 "data": {
278 "text/plain": [
279 "7"
280 ]
281 },
282 "execution_count": 21,
283 "metadata": {},
284 "output_type": "execute_result"
285 }
286 ],
287 "source": [
288 "best_count_primes(56003)"
289 ]
290 },
291 {
292 "cell_type": "code",
293 "execution_count": 20,
294 "metadata": {
295 "collapsed": false
296 },
297 "outputs": [
298 {
299 "data": {
300 "text/plain": [
301 "4"
302 ]
303 },
304 "execution_count": 20,
305 "metadata": {},
306 "output_type": "execute_result"
307 }
308 ],
309 "source": [
310 "best_count_primes(4)"
311 ]
312 },
313 {
314 "cell_type": "code",
315 "execution_count": 26,
316 "metadata": {
317 "collapsed": false
318 },
319 "outputs": [
320 {
321 "data": {
322 "text/plain": [
323 ":sequence"
324 ]
325 },
326 "execution_count": 26,
327 "metadata": {},
328 "output_type": "execute_result"
329 }
330 ],
331 "source": [
332 "def sequence(&generator)\n",
333 " Enumerator.new do |yielder|\n",
334 " n = 0\n",
335 " loop do\n",
336 " yielder.yield generator.call(n)\n",
337 " n = n + 1\n",
338 " end\n",
339 " end\n",
340 "end"
341 ]
342 },
343 {
344 "cell_type": "code",
345 "execution_count": 53,
346 "metadata": {
347 "collapsed": false
348 },
349 "outputs": [
350 {
351 "data": {
352 "text/plain": [
353 "[[2, 4], [3, 4], [5, 4], [7, 4], [11, 5], [13, 6], [17, 5], [19, 5], [23, 6], [29, 5], [31, 5], [37, 5], [41, 5], [43, 6], [47, 5], [53, 6], [59, 5], [61, 5], [67, 5], [71, 5]]"
354 ]
355 },
356 "execution_count": 53,
357 "metadata": {},
358 "output_type": "execute_result"
359 }
360 ],
361 "source": [
362 "primes.take(20).map {|p| [p, best_count_primes(p)]}"
363 ]
364 },
365 {
366 "cell_type": "code",
367 "execution_count": 56,
368 "metadata": {
369 "collapsed": false,
370 "scrolled": true
371 },
372 "outputs": [
373 {
374 "data": {
375 "text/plain": [
376 "121313"
377 ]
378 },
379 "execution_count": 56,
380 "metadata": {},
381 "output_type": "execute_result"
382 }
383 ],
384 "source": [
385 "i = 1\n",
386 "while best_count_primes(primes[i]) < 8 do\n",
387 " i += 1\n",
388 "end\n",
389 "primes[i]"
390 ]
391 },
392 {
393 "cell_type": "code",
394 "execution_count": 55,
395 "metadata": {
396 "collapsed": false
397 },
398 "outputs": [
399 {
400 "data": {
401 "text/plain": [
402 "3"
403 ]
404 },
405 "execution_count": 55,
406 "metadata": {},
407 "output_type": "execute_result"
408 }
409 ],
410 "source": [
411 "best_count_primes 120383"
412 ]
413 },
414 {
415 "cell_type": "code",
416 "execution_count": 48,
417 "metadata": {
418 "collapsed": false
419 },
420 "outputs": [
421 {
422 "data": {
423 "text/plain": [
424 "[[333383, 555383, 777383], [110183, 330383, 660683, 880883], [], [330383, 770387, 990389], [323383, 525583, 626683, 929983], [121313, 222323, 323333, 424343, 525353, 626363, 828383, 929393], [323383, 929389], [620663, 720773], [120181], [920399], [], [122323, 166363], [], [100003, 120223, 140443, 160663, 170773, 180883], [], [110311], [], [121181], [], []]"
425 ]
426 },
427 "execution_count": 48,
428 "metadata": {},
429 "output_type": "execute_result"
430 }
431 ],
432 "source": [
433 "num = 120383\n",
434 "possibles = (0...num.to_digits.length).to_a\n",
435 "possibles.combination(3).map {|ps| replace_in_positions(num, ps).select {|n| n.prime?}}# .map {|ps| count_primes_in_positions(num, ps)}"
436 ]
437 },
438 {
439 "cell_type": "code",
440 "execution_count": 25,
441 "metadata": {
442 "collapsed": false
443 },
444 "outputs": [
445 {
446 "data": {
447 "text/plain": [
448 "8"
449 ]
450 },
451 "execution_count": 25,
452 "metadata": {},
453 "output_type": "execute_result"
454 }
455 ],
456 "source": [
457 "best_count_primes(121313)"
458 ]
459 },
460 {
461 "cell_type": "code",
462 "execution_count": null,
463 "metadata": {
464 "collapsed": true
465 },
466 "outputs": [],
467 "source": []
468 }
469 ],
470 "metadata": {
471 "kernelspec": {
472 "display_name": "Ruby 2.4.0",
473 "language": "ruby",
474 "name": "ruby"
475 },
476 "language_info": {
477 "file_extension": ".rb",
478 "mimetype": "application/x-ruby",
479 "name": "ruby",
480 "version": "2.4.0"
481 }
482 },
483 "nbformat": 4,
484 "nbformat_minor": 0
485 }