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 }