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 }