euler40.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "code",
   5    "execution_count": 45,
   6    "metadata": {
   7     "collapsed": false
   8    },
   9    "outputs": [
  10     {
  11      "data": {
  12       "text/plain": [
  13        "true"
  14       ]
  15      },
  16      "execution_count": 45,
  17      "metadata": {},
  18      "output_type": "execute_result"
  19     }
  20    ],
  21    "source": [
  22     "load 'array-numbers.rb'"
  23    ]
  24   },
  25   {
  26    "cell_type": "code",
  27    "execution_count": 46,
  28    "metadata": {
  29     "collapsed": false
  30    },
  31    "outputs": [
  32     {
  33      "data": {
  34       "text/plain": [
  35        "38890"
  36       ]
  37      },
  38      "execution_count": 46,
  39      "metadata": {},
  40      "output_type": "execute_result"
  41     }
  42    ],
  43    "source": [
  44     "ch = (0..9999).flat_map {|i| i.to_digits}\n",
  45     "ch.length"
  46    ]
  47   },
  48   {
  49    "cell_type": "code",
  50    "execution_count": 47,
  51    "metadata": {
  52     "collapsed": false
  53    },
  54    "outputs": [
  55     {
  56      "data": {
  57       "text/plain": [
  58        "[9, 7, 9, 9, 9, 8, 9, 9, 9, 9]"
  59       ]
  60      },
  61      "execution_count": 47,
  62      "metadata": {},
  63      "output_type": "execute_result"
  64     }
  65    ],
  66    "source": [
  67     "ch[-10..-1]"
  68    ]
  69   },
  70   {
  71    "cell_type": "code",
  72    "execution_count": 48,
  73    "metadata": {
  74     "collapsed": false
  75    },
  76    "outputs": [
  77     {
  78      "data": {
  79       "text/plain": [
  80        "1"
  81       ]
  82      },
  83      "execution_count": 48,
  84      "metadata": {},
  85      "output_type": "execute_result"
  86     }
  87    ],
  88    "source": [
  89     "ch[1]"
  90    ]
  91   },
  92   {
  93    "cell_type": "code",
  94    "execution_count": 49,
  95    "metadata": {
  96     "collapsed": false
  97    },
  98    "outputs": [
  99     {
 100      "data": {
 101       "text/plain": [
 102        "1"
 103       ]
 104      },
 105      "execution_count": 49,
 106      "metadata": {},
 107      "output_type": "execute_result"
 108     }
 109    ],
 110    "source": [
 111     "ch[10]"
 112    ]
 113   },
 114   {
 115    "cell_type": "code",
 116    "execution_count": 50,
 117    "metadata": {
 118     "collapsed": false
 119    },
 120    "outputs": [
 121     {
 122      "data": {
 123       "text/plain": [
 124        "5"
 125       ]
 126      },
 127      "execution_count": 50,
 128      "metadata": {},
 129      "output_type": "execute_result"
 130     }
 131    ],
 132    "source": [
 133     "ch[100]"
 134    ]
 135   },
 136   {
 137    "cell_type": "code",
 138    "execution_count": 51,
 139    "metadata": {
 140     "collapsed": false
 141    },
 142    "outputs": [
 143     {
 144      "data": {
 145       "text/plain": [
 146        "38890"
 147       ]
 148      },
 149      "execution_count": 51,
 150      "metadata": {},
 151      "output_type": "execute_result"
 152     }
 153    ],
 154    "source": [
 155     "ch.length"
 156    ]
 157   },
 158   {
 159    "cell_type": "code",
 160    "execution_count": 52,
 161    "metadata": {
 162     "collapsed": false
 163    },
 164    "outputs": [
 165     {
 166      "data": {
 167       "text/plain": [
 168        ":champ"
 169       ]
 170      },
 171      "execution_count": 52,
 172      "metadata": {},
 173      "output_type": "execute_result"
 174     }
 175    ],
 176    "source": [
 177     "def champ(i)\n",
 178     "  if i < 10\n",
 179     "    i\n",
 180     "  elsif i < 190\n",
 181     "    if (i - 10) % 2 == 0 # tens\n",
 182     "      ((i - 10) / 2) / 10 + 1\n",
 183     "    else # units\n",
 184     "      # ((i - 11) / 2) % 10\n",
 185     "     ((i - 10) / 2) % 10\n",
 186     "    end\n",
 187     "  elsif i < 2890\n",
 188     "    if (i - 190) % 3 == 0 #hundreds\n",
 189     "      ((i - 190) / 3) / 100 + 1\n",
 190     "    elsif (i - 190) % 3 == 1 # tens\n",
 191     "      (((i - 190) / 3) / 10) % 10\n",
 192     "    else # units\n",
 193     "      ((i - 190) / 3) % 10\n",
 194     "    end\n",
 195     "  elsif i < 38890\n",
 196     "    if (i - 2890) % 4 == 0 # thousands\n",
 197     "      ((i - 2890) / 4) / 1000 + 1\n",
 198     "    elsif (i - 2890) % 4 == 1 # hundreds\n",
 199     "      (((i - 2890) / 4) / 100) % 10\n",
 200     "    elsif (i - 2890) % 4 == 2 # tens\n",
 201     "      (((i - 2890) / 4) / 10) % 10\n",
 202     "    else # units\n",
 203     "      ((i - 2890) / 4) % 10\n",
 204     "    end\n",
 205     "  else\n",
 206     "    99\n",
 207     "  end\n",
 208     "end"
 209    ]
 210   },
 211   {
 212    "cell_type": "code",
 213    "execution_count": 105,
 214    "metadata": {
 215     "collapsed": false,
 216     "scrolled": true
 217    },
 218    "outputs": [
 219     {
 220      "name": "stdout",
 221      "output_type": "stream",
 222      "text": [
 223       "1 :: 1 (2890)\n",
 224       "0 :: 0 (2891)\n",
 225       "0 :: 0 (2892)\n",
 226       "0 :: 0 (2893)\n",
 227       "1 :: 1 (2894)\n",
 228       "0 :: 0 (2895)\n",
 229       "0 :: 0 (2896)\n",
 230       "1 :: 1 (2897)\n",
 231       "1 :: 1 (2898)\n",
 232       "0 :: 0 (2899)\n",
 233       "0 :: 0 (2900)\n"
 234      ]
 235     },
 236     {
 237      "data": {
 238       "text/plain": [
 239        "2890..2900"
 240       ]
 241      },
 242      "execution_count": 105,
 243      "metadata": {},
 244      "output_type": "execute_result"
 245     }
 246    ],
 247    "source": [
 248     "(2890..2900).each do |i|\n",
 249     "  puts \"#{champ i} :: #{ch[i]} (#{i})\"\n",
 250     "end"
 251    ]
 252   },
 253   {
 254    "cell_type": "code",
 255    "execution_count": 95,
 256    "metadata": {
 257     "collapsed": false
 258    },
 259    "outputs": [
 260     {
 261      "data": {
 262       "text/plain": [
 263        "true"
 264       ]
 265      },
 266      "execution_count": 95,
 267      "metadata": {},
 268      "output_type": "execute_result"
 269     }
 270    ],
 271    "source": [
 272     "(1..38889).all? {|i| champ(i) == ch[i]}"
 273    ]
 274   },
 275   {
 276    "cell_type": "code",
 277    "execution_count": 107,
 278    "metadata": {
 279     "collapsed": false
 280    },
 281    "outputs": [
 282     {
 283      "data": {
 284       "text/plain": [
 285        "[]"
 286       ]
 287      },
 288      "execution_count": 107,
 289      "metadata": {},
 290      "output_type": "execute_result"
 291     }
 292    ],
 293    "source": [
 294     "(1..38889).select {|i| champ(i) != ch[i]}"
 295    ]
 296   },
 297   {
 298    "cell_type": "code",
 299    "execution_count": 108,
 300    "metadata": {
 301     "collapsed": false
 302    },
 303    "outputs": [
 304     {
 305      "data": {
 306       "text/plain": [
 307        "true"
 308       ]
 309      },
 310      "execution_count": 108,
 311      "metadata": {},
 312      "output_type": "execute_result"
 313     }
 314    ],
 315    "source": [
 316     "190 - 10 == 2 * 9 * 10 ** 1"
 317    ]
 318   },
 319   {
 320    "cell_type": "code",
 321    "execution_count": 109,
 322    "metadata": {
 323     "collapsed": false
 324    },
 325    "outputs": [
 326     {
 327      "data": {
 328       "text/plain": [
 329        "true"
 330       ]
 331      },
 332      "execution_count": 109,
 333      "metadata": {},
 334      "output_type": "execute_result"
 335     }
 336    ],
 337    "source": [
 338     "2890 - 190 == 3 * 9 * 10 ** 2"
 339    ]
 340   },
 341   {
 342    "cell_type": "code",
 343    "execution_count": 110,
 344    "metadata": {
 345     "collapsed": false
 346    },
 347    "outputs": [
 348     {
 349      "data": {
 350       "text/plain": [
 351        "true"
 352       ]
 353      },
 354      "execution_count": 110,
 355      "metadata": {},
 356      "output_type": "execute_result"
 357     }
 358    ],
 359    "source": [
 360     "38890 - 2890 == 4 * 9 * 10 ** 3"
 361    ]
 362   },
 363   {
 364    "cell_type": "code",
 365    "execution_count": 120,
 366    "metadata": {
 367     "collapsed": false
 368    },
 369    "outputs": [
 370     {
 371      "data": {
 372       "text/plain": [
 373        "[1, 10, 190, 2890, 38890, 488890, 5888890]"
 374       ]
 375      },
 376      "execution_count": 120,
 377      "metadata": {},
 378      "output_type": "execute_result"
 379     }
 380    ],
 381    "source": [
 382     "# threshold, number of digits, offset\n",
 383     "(1..6).map {|n| n * 9 * 10**(n-1)}.reduce([1, 0, 0]) {|ss, n| ss + [[ss[-1][0] + n]}"
 384    ]
 385   },
 386   {
 387    "cell_type": "code",
 388    "execution_count": 2,
 389    "metadata": {
 390     "collapsed": false
 391    },
 392    "outputs": [
 393     {
 394      "data": {
 395       "text/plain": [
 396        "[1, 0, 0, [9], [189], [2889], [38889], [488889], [5888889]]"
 397       ]
 398      },
 399      "execution_count": 2,
 400      "metadata": {},
 401      "output_type": "execute_result"
 402     }
 403    ],
 404    "source": [
 405     "(1..6).map {|n| n * 9 * 10**(n-1)}.reduce([[1, 0, 0]]) {|ss, n| ss + [[ss[-1][0] + n, n, ]]}"
 406    ]
 407   },
 408   {
 409    "cell_type": "code",
 410    "execution_count": 7,
 411    "metadata": {
 412     "collapsed": false
 413    },
 414    "outputs": [
 415     {
 416      "data": {
 417       "text/plain": [
 418        "[[0, 9], [1, 180], [2, 2700], [3, 36000], [4, 450000], [5, 5400000], [6, 63000000]]"
 419       ]
 420      },
 421      "execution_count": 7,
 422      "metadata": {},
 423      "output_type": "execute_result"
 424     }
 425    ],
 426    "source": [
 427     "(0..6).map {|n| [n, (n+1) * 9 * 10**n]}"
 428    ]
 429   },
 430   {
 431    "cell_type": "code",
 432    "execution_count": 20,
 433    "metadata": {
 434     "collapsed": false
 435    },
 436    "outputs": [
 437     {
 438      "data": {
 439       "text/plain": [
 440        "[[0, 1, 1], [9, 0, 10], [189, 1, 190], [2889, 2, 2890], [38889, 3, 38890], [488889, 4, 488890], [5888889, 5, 5888890], [68888889, 6, 68888890]]"
 441       ]
 442      },
 443      "execution_count": 20,
 444      "metadata": {},
 445      "output_type": "execute_result"
 446     }
 447    ],
 448    "source": [
 449     "(0..6).map {|n| [n, (n+1) * 9 * 10**n]}.reduce([[0, 1, 1]]) {|ts, ns| ts + [[ts[-1][0] + ns[1], ns[0], ts[-1][2] + ns[1]]] }"
 450    ]
 451   },
 452   {
 453    "cell_type": "code",
 454    "execution_count": 94,
 455    "metadata": {
 456     "collapsed": false
 457    },
 458    "outputs": [
 459     {
 460      "data": {
 461       "text/plain": [
 462        ":champ2"
 463       ]
 464      },
 465      "execution_count": 94,
 466      "metadata": {},
 467      "output_type": "execute_result"
 468     }
 469    ],
 470    "source": [
 471     "def champ2(n)\n",
 472     "  i = 1\n",
 473     "  limit = 10\n",
 474     "  offset = 0\n",
 475     "  while n >= limit\n",
 476     "    offset = limit\n",
 477     "    i += 1\n",
 478     "    step = i * 9 * 10**(i-1)\n",
 479     "    limit += step\n",
 480     "  end\n",
 481     "  unit = (n - offset) % i\n",
 482     "  digit = ((n - offset) / i) / (10 ** (i-(unit +1))) % 10\n",
 483     "  digit += 1 if unit == 0 && i != 1\n",
 484     "  # return i, limit, offset, unit, digit\n",
 485     "  digit\n",
 486     "end"
 487    ]
 488   },
 489   {
 490    "cell_type": "code",
 491    "execution_count": 91,
 492    "metadata": {
 493     "collapsed": false
 494    },
 495    "outputs": [
 496     {
 497      "name": "stdout",
 498      "output_type": "stream",
 499      "text": [
 500       "1 : 1 :: [1, 10, 0, 0, 1]\n",
 501       "2 : 2 :: [1, 10, 0, 0, 2]\n",
 502       "3 : 3 :: [1, 10, 0, 0, 3]\n",
 503       "4 : 4 :: [1, 10, 0, 0, 4]\n",
 504       "5 : 5 :: [1, 10, 0, 0, 5]\n",
 505       "6 : 6 :: [1, 10, 0, 0, 6]\n",
 506       "7 : 7 :: [1, 10, 0, 0, 7]\n",
 507       "8 : 8 :: [1, 10, 0, 0, 8]\n",
 508       "9 : 9 :: [1, 10, 0, 0, 9]\n",
 509       "10 : 1 :: [2, 190, 10, 0, 1]\n",
 510       "11 : 0 :: [2, 190, 10, 1, 0]\n",
 511       "12 : 1 :: [2, 190, 10, 0, 1]\n",
 512       "13 : 1 :: [2, 190, 10, 1, 1]\n",
 513       "14 : 1 :: [2, 190, 10, 0, 1]\n",
 514       "15 : 2 :: [2, 190, 10, 1, 2]\n",
 515       "16 : 1 :: [2, 190, 10, 0, 1]\n",
 516       "17 : 3 :: [2, 190, 10, 1, 3]\n",
 517       "18 : 1 :: [2, 190, 10, 0, 1]\n",
 518       "19 : 4 :: [2, 190, 10, 1, 4]\n",
 519       "20 : 1 :: [2, 190, 10, 0, 1]\n"
 520      ]
 521     },
 522     {
 523      "data": {
 524       "text/plain": [
 525        "1..20"
 526       ]
 527      },
 528      "execution_count": 91,
 529      "metadata": {},
 530      "output_type": "execute_result"
 531     }
 532    ],
 533    "source": [
 534     "(1..20).each do |i| puts \"#{i} : #{champ i} :: #{champ2 i}\" end"
 535    ]
 536   },
 537   {
 538    "cell_type": "code",
 539    "execution_count": 92,
 540    "metadata": {
 541     "collapsed": false
 542    },
 543    "outputs": [
 544     {
 545      "name": "stdout",
 546      "output_type": "stream",
 547      "text": [
 548       "180 : 9 :: [2, 190, 10, 0, 9]\n",
 549       "181 : 5 :: [2, 190, 10, 1, 5]\n",
 550       "182 : 9 :: [2, 190, 10, 0, 9]\n",
 551       "183 : 6 :: [2, 190, 10, 1, 6]\n",
 552       "184 : 9 :: [2, 190, 10, 0, 9]\n",
 553       "185 : 7 :: [2, 190, 10, 1, 7]\n",
 554       "186 : 9 :: [2, 190, 10, 0, 9]\n",
 555       "187 : 8 :: [2, 190, 10, 1, 8]\n",
 556       "188 : 9 :: [2, 190, 10, 0, 9]\n",
 557       "189 : 9 :: [2, 190, 10, 1, 9]\n",
 558       "190 : 1 :: [3, 2890, 190, 0, 1]\n",
 559       "191 : 0 :: [3, 2890, 190, 1, 0]\n",
 560       "192 : 0 :: [3, 2890, 190, 2, 0]\n",
 561       "193 : 1 :: [3, 2890, 190, 0, 1]\n",
 562       "194 : 0 :: [3, 2890, 190, 1, 0]\n",
 563       "195 : 1 :: [3, 2890, 190, 2, 1]\n",
 564       "196 : 1 :: [3, 2890, 190, 0, 1]\n",
 565       "197 : 0 :: [3, 2890, 190, 1, 0]\n",
 566       "198 : 2 :: [3, 2890, 190, 2, 2]\n",
 567       "199 : 1 :: [3, 2890, 190, 0, 1]\n",
 568       "200 : 0 :: [3, 2890, 190, 1, 0]\n"
 569      ]
 570     },
 571     {
 572      "data": {
 573       "text/plain": [
 574        "180..200"
 575       ]
 576      },
 577      "execution_count": 92,
 578      "metadata": {},
 579      "output_type": "execute_result"
 580     }
 581    ],
 582    "source": [
 583     "(180..200).each do |i| puts \"#{i} : #{champ i} :: #{champ2 i}\" end"
 584    ]
 585   },
 586   {
 587    "cell_type": "code",
 588    "execution_count": 93,
 589    "metadata": {
 590     "collapsed": false
 591    },
 592    "outputs": [
 593     {
 594      "name": "stdout",
 595      "output_type": "stream",
 596      "text": [
 597       "2880 : 6 :: [3, 2890, 190, 2, 6]\n",
 598       "2881 : 9 :: [3, 2890, 190, 0, 9]\n",
 599       "2882 : 9 :: [3, 2890, 190, 1, 9]\n",
 600       "2883 : 7 :: [3, 2890, 190, 2, 7]\n",
 601       "2884 : 9 :: [3, 2890, 190, 0, 9]\n",
 602       "2885 : 9 :: [3, 2890, 190, 1, 9]\n",
 603       "2886 : 8 :: [3, 2890, 190, 2, 8]\n",
 604       "2887 : 9 :: [3, 2890, 190, 0, 9]\n",
 605       "2888 : 9 :: [3, 2890, 190, 1, 9]\n",
 606       "2889 : 9 :: [3, 2890, 190, 2, 9]\n",
 607       "2890 : 1 :: [4, 38890, 2890, 0, 1]\n",
 608       "2891 : 0 :: [4, 38890, 2890, 1, 0]\n",
 609       "2892 : 0 :: [4, 38890, 2890, 2, 0]\n",
 610       "2893 : 0 :: [4, 38890, 2890, 3, 0]\n",
 611       "2894 : 1 :: [4, 38890, 2890, 0, 1]\n",
 612       "2895 : 0 :: [4, 38890, 2890, 1, 0]\n",
 613       "2896 : 0 :: [4, 38890, 2890, 2, 0]\n",
 614       "2897 : 1 :: [4, 38890, 2890, 3, 1]\n",
 615       "2898 : 1 :: [4, 38890, 2890, 0, 1]\n",
 616       "2899 : 0 :: [4, 38890, 2890, 1, 0]\n",
 617       "2900 : 0 :: [4, 38890, 2890, 2, 0]\n"
 618      ]
 619     },
 620     {
 621      "data": {
 622       "text/plain": [
 623        "2880..2900"
 624       ]
 625      },
 626      "execution_count": 93,
 627      "metadata": {},
 628      "output_type": "execute_result"
 629     }
 630    ],
 631    "source": [
 632     "(2880..2900).each do |i| puts \"#{i} : #{champ i} :: #{champ2 i}\" end"
 633    ]
 634   },
 635   {
 636    "cell_type": "code",
 637    "execution_count": 96,
 638    "metadata": {
 639     "collapsed": false
 640    },
 641    "outputs": [
 642     {
 643      "data": {
 644       "text/plain": [
 645        "true"
 646       ]
 647      },
 648      "execution_count": 96,
 649      "metadata": {},
 650      "output_type": "execute_result"
 651     }
 652    ],
 653    "source": [
 654     "(1..38889).all? {|i| champ2(i) == ch[i]}"
 655    ]
 656   },
 657   {
 658    "cell_type": "code",
 659    "execution_count": 99,
 660    "metadata": {
 661     "collapsed": false
 662    },
 663    "outputs": [
 664     {
 665      "data": {
 666       "text/plain": [
 667        "210"
 668       ]
 669      },
 670      "execution_count": 99,
 671      "metadata": {},
 672      "output_type": "execute_result"
 673     }
 674    ],
 675    "source": [
 676     "(0..6).map {|e| champ2(10**e)}.reduce(:*)"
 677    ]
 678   },
 679   {
 680    "cell_type": "code",
 681    "execution_count": null,
 682    "metadata": {
 683     "collapsed": true
 684    },
 685    "outputs": [],
 686    "source": []
 687   }
 688  ],
 689  "metadata": {
 690   "kernelspec": {
 691    "display_name": "Ruby 2.4.0",
 692    "language": "ruby",
 693    "name": "ruby"
 694   },
 695   "language_info": {
 696    "file_extension": ".rb",
 697    "mimetype": "application/x-ruby",
 698    "name": "ruby",
 699    "version": "2.4.0"
 700   }
 701  },
 702  "nbformat": 4,
 703  "nbformat_minor": 0
 704 }