euler43.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 'array-numbers.rb'"
  23    ]
  24   },
  25   {
  26    "cell_type": "markdown",
  27    "metadata": {},
  28    "source": [
  29     "* d2d3d4=406 is divisible by 2\n",
  30     "* d3d4d5=063 is divisible by 3\n",
  31     "* d4d5d6=635 is divisible by 5\n",
  32     "* d5d6d7=357 is divisible by 7\n",
  33     "* d6d7d8=572 is divisible by 11\n",
  34     "* d7d8d9=728 is divisible by 13\n",
  35     "* d8d9d10=289 is divisible by 17"
  36    ]
  37   },
  38   {
  39    "cell_type": "code",
  40    "execution_count": 2,
  41    "metadata": {
  42     "collapsed": false
  43    },
  44    "outputs": [
  45     {
  46      "data": {
  47       "text/plain": [
  48        ":pluck"
  49       ]
  50      },
  51      "execution_count": 2,
  52      "metadata": {},
  53      "output_type": "execute_result"
  54     }
  55    ],
  56    "source": [
  57     "def pluck(items)\n",
  58     "  plucked = []\n",
  59     "  items.each_index do |i|\n",
  60     "    plucked << [items[i], items[0, i] + items[i+1..-1]]\n",
  61     "  end\n",
  62     "  plucked\n",
  63     "end"
  64    ]
  65   },
  66   {
  67    "cell_type": "code",
  68    "execution_count": 3,
  69    "metadata": {
  70     "collapsed": false
  71    },
  72    "outputs": [
  73     {
  74      "data": {
  75       "text/plain": [
  76        "[[0, [1, 2, 3, 4]], [1, [0, 2, 3, 4]], [2, [0, 1, 3, 4]], [3, [0, 1, 2, 4]], [4, [0, 1, 2, 3]]]"
  77       ]
  78      },
  79      "execution_count": 3,
  80      "metadata": {},
  81      "output_type": "execute_result"
  82     }
  83    ],
  84    "source": [
  85     "pluck([0,1,2,3,4])"
  86    ]
  87   },
  88   {
  89    "cell_type": "code",
  90    "execution_count": 4,
  91    "metadata": {
  92     "collapsed": false
  93    },
  94    "outputs": [
  95     {
  96      "data": {
  97       "text/plain": [
  98        ":choices"
  99       ]
 100      },
 101      "execution_count": 4,
 102      "metadata": {},
 103      "output_type": "execute_result"
 104     }
 105    ],
 106    "source": [
 107     "def choices(partial_solution)\n",
 108     "  choices = []\n",
 109     "  pluck(partial_solution[:remaining]).each do |digit, remaining|\n",
 110     "    choices << {digits: partial_solution[:digits] + [digit], remaining: remaining}\n",
 111     "  end\n",
 112     "  choices\n",
 113     "end  "
 114    ]
 115   },
 116   {
 117    "cell_type": "code",
 118    "execution_count": 5,
 119    "metadata": {
 120     "collapsed": false
 121    },
 122    "outputs": [
 123     {
 124      "data": {
 125       "text/plain": [
 126        "{:digits=>[], :remaining=>[0, 1, 2, 3]}"
 127       ]
 128      },
 129      "execution_count": 5,
 130      "metadata": {},
 131      "output_type": "execute_result"
 132     }
 133    ],
 134    "source": [
 135     "initial = {digits: [], remaining: (0..3).to_a}"
 136    ]
 137   },
 138   {
 139    "cell_type": "code",
 140    "execution_count": 6,
 141    "metadata": {
 142     "collapsed": false
 143    },
 144    "outputs": [
 145     {
 146      "data": {
 147       "text/plain": [
 148        "[{:digits=>[0], :remaining=>[1, 2, 3]}, {:digits=>[1], :remaining=>[0, 2, 3]}, {:digits=>[2], :remaining=>[0, 1, 3]}, {:digits=>[3], :remaining=>[0, 1, 2]}]"
 149       ]
 150      },
 151      "execution_count": 6,
 152      "metadata": {},
 153      "output_type": "execute_result"
 154     }
 155    ],
 156    "source": [
 157     "choices(initial)"
 158    ]
 159   },
 160   {
 161    "cell_type": "code",
 162    "execution_count": 7,
 163    "metadata": {
 164     "collapsed": false
 165    },
 166    "outputs": [
 167     {
 168      "data": {
 169       "text/plain": [
 170        "[{:digits=>[0, 1], :remaining=>[2, 3]}, {:digits=>[0, 2], :remaining=>[1, 3]}, {:digits=>[0, 3], :remaining=>[1, 2]}, {:digits=>[1, 0], :remaining=>[2, 3]}, {:digits=>[1, 2], :remaining=>[0, 3]}, {:digits=>[1, 3], :remaining=>[0, 2]}, {:digits=>[2, 0], :remaining=>[1, 3]}, {:digits=>[2, 1], :remaining=>[0, 3]}, {:digits=>[2, 3], :remaining=>[0, 1]}, {:digits=>[3, 0], :remaining=>[1, 2]}, {:digits=>[3, 1], :remaining=>[0, 2]}, {:digits=>[3, 2], :remaining=>[0, 1]}]"
 171       ]
 172      },
 173      "execution_count": 7,
 174      "metadata": {},
 175      "output_type": "execute_result"
 176     }
 177    ],
 178    "source": [
 179     "choices(initial).flat_map {|s| choices(s)}"
 180    ]
 181   },
 182   {
 183    "cell_type": "code",
 184    "execution_count": 8,
 185    "metadata": {
 186     "collapsed": false
 187    },
 188    "outputs": [
 189     {
 190      "data": {
 191       "text/plain": [
 192        ":solve0"
 193       ]
 194      },
 195      "execution_count": 8,
 196      "metadata": {},
 197      "output_type": "execute_result"
 198     }
 199    ],
 200    "source": [
 201     "def solve0()\n",
 202     "  initial = {digits: [], remaining: (0..9).to_a}\n",
 203     "  d0s = choices(initial)\n",
 204     "  d1s = d0s.flat_map {|s| choices(s)}\n",
 205     "  d2s = d1s.flat_map {|s| choices(s)}\n",
 206     "  d3s = d2s.flat_map {|s| choices(s)}.select {|s| s[:digits][-3..-1].to_i % 2 == 0}\n",
 207     "  d4s = d3s.flat_map {|s| choices(s)}.select {|s| s[:digits][-3..-1].to_i % 3 == 0}\n",
 208     "  d5s = d4s.flat_map {|s| choices(s)}.select {|s| s[:digits][-3..-1].to_i % 5 == 0}\n",
 209     "  d6s = d5s.flat_map {|s| choices(s)}.select {|s| s[:digits][-3..-1].to_i % 7 == 0}\n",
 210     "  d7s = d6s.flat_map {|s| choices(s)}.select {|s| s[:digits][-3..-1].to_i % 11 == 0}\n",
 211     "  d8s = d7s.flat_map {|s| choices(s)}.select {|s| s[:digits][-3..-1].to_i % 13 == 0}\n",
 212     "  d9s = d8s.flat_map {|s| choices(s)}.select {|s| s[:digits][-3..-1].to_i % 17 == 0}\n",
 213     "  # puts \"0: #{d0s.length}, 1: #{d1s.length}, 2: #{d2s.length}, 3: #{d3s.length}, 4: #{d4s.length}, 5: #{d5s.length}, 6: #{d6s.length}, 7: #{d7s.length}, 8: #{d8s.length}, 9: #{d9s.length}\"\n",
 214     "  d9s.map {|s| s[:digits].to_i}.sum\n",
 215     "end"
 216    ]
 217   },
 218   {
 219    "cell_type": "code",
 220    "execution_count": 9,
 221    "metadata": {
 222     "collapsed": false
 223    },
 224    "outputs": [
 225     {
 226      "data": {
 227       "text/plain": [
 228        ":solve_step"
 229       ]
 230      },
 231      "execution_count": 9,
 232      "metadata": {},
 233      "output_type": "execute_result"
 234     }
 235    ],
 236    "source": [
 237     "def solve_step(partial_solutions, divisor)\n",
 238     "  solns = partial_solutions.flat_map {|s| choices(s)}\n",
 239     "  if divisor == 1\n",
 240     "    solns\n",
 241     "  else\n",
 242     "    solns.select {|s| s[:digits][-3..-1].to_i % divisor == 0}\n",
 243     "  end\n",
 244     "end"
 245    ]
 246   },
 247   {
 248    "cell_type": "code",
 249    "execution_count": 10,
 250    "metadata": {
 251     "collapsed": false
 252    },
 253    "outputs": [
 254     {
 255      "data": {
 256       "text/plain": [
 257        ":solve"
 258       ]
 259      },
 260      "execution_count": 10,
 261      "metadata": {},
 262      "output_type": "execute_result"
 263     }
 264    ],
 265    "source": [
 266     "def solve()\n",
 267     "  initial = {digits: [], remaining: (0..9).to_a}\n",
 268     "  solutions = choices(initial)\n",
 269     "  [1, 1, 2, 3, 5, 7, 11, 13, 17].each do |d|\n",
 270     "    # puts \"#{d}, #{solutions.length}, #{solutions[0][:digits].length}\"\n",
 271     "    solutions = solve_step(solutions, d)\n",
 272     "  end\n",
 273     "  solutions.map {|s| s[:digits].to_i}.sum\n",
 274     "end"
 275    ]
 276   },
 277   {
 278    "cell_type": "code",
 279    "execution_count": 11,
 280    "metadata": {
 281     "collapsed": false
 282    },
 283    "outputs": [
 284     {
 285      "data": {
 286       "text/plain": [
 287        "16695334890"
 288       ]
 289      },
 290      "execution_count": 11,
 291      "metadata": {},
 292      "output_type": "execute_result"
 293     }
 294    ],
 295    "source": [
 296     "solve0"
 297    ]
 298   },
 299   {
 300    "cell_type": "code",
 301    "execution_count": 12,
 302    "metadata": {
 303     "collapsed": false
 304    },
 305    "outputs": [
 306     {
 307      "data": {
 308       "text/plain": [
 309        "16695334890"
 310       ]
 311      },
 312      "execution_count": 12,
 313      "metadata": {},
 314      "output_type": "execute_result"
 315     }
 316    ],
 317    "source": [
 318     "solve"
 319    ]
 320   },
 321   {
 322    "cell_type": "code",
 323    "execution_count": null,
 324    "metadata": {
 325     "collapsed": true
 326    },
 327    "outputs": [],
 328    "source": []
 329   }
 330  ],
 331  "metadata": {
 332   "kernelspec": {
 333    "display_name": "Ruby 2.4.0",
 334    "language": "ruby",
 335    "name": "ruby"
 336   },
 337   "language_info": {
 338    "file_extension": ".rb",
 339    "mimetype": "application/x-ruby",
 340    "name": "ruby",
 341    "version": "2.4.0"
 342   }
 343  },
 344  "nbformat": 4,
 345  "nbformat_minor": 0
 346 }