euler31.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     "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, 5, 10, 20, 50, 100, 200]"
  37       ]
  38      },
  39      "execution_count": 2,
  40      "metadata": {},
  41      "output_type": "execute_result"
  42     }
  43    ],
  44    "source": [
  45     "ways = {[0, 0] => 1}\n",
  46     "coins = [1,2,5,10,20,50,100,200]"
  47    ]
  48   },
  49   {
  50    "cell_type": "code",
  51    "execution_count": 3,
  52    "metadata": {
  53     "collapsed": false
  54    },
  55    "outputs": [
  56     {
  57      "data": {
  58       "text/plain": [
  59        "{[0, 0]=>1}"
  60       ]
  61      },
  62      "execution_count": 3,
  63      "metadata": {},
  64      "output_type": "execute_result"
  65     }
  66    ],
  67    "source": [
  68     "ways"
  69    ]
  70   },
  71   {
  72    "cell_type": "code",
  73    "execution_count": 4,
  74    "metadata": {
  75     "collapsed": false
  76    },
  77    "outputs": [
  78     {
  79      "data": {
  80       "text/plain": [
  81        "[1, 2, 5, 10, 20, 50, 100]"
  82       ]
  83      },
  84      "execution_count": 4,
  85      "metadata": {},
  86      "output_type": "execute_result"
  87     }
  88    ],
  89    "source": [
  90     "coins[0...-1]"
  91    ]
  92   },
  93   {
  94    "cell_type": "code",
  95    "execution_count": 5,
  96    "metadata": {
  97     "collapsed": false
  98    },
  99    "outputs": [
 100     {
 101      "data": {
 102       "text/plain": [
 103        ":change_count"
 104       ]
 105      },
 106      "execution_count": 5,
 107      "metadata": {},
 108      "output_type": "execute_result"
 109     }
 110    ],
 111    "source": [
 112     "def change_count(coins, ncoins, total)\n",
 113     "  puts(\"#{coins[0...ncoins]} coins finding #{total}\")\n",
 114     "  if total == 0\n",
 115     "    1\n",
 116     "  elsif total < 0\n",
 117     "    0\n",
 118     "  elsif ncoins < 0 && total > 0\n",
 119     "    0\n",
 120     "  else\n",
 121     "    change_count(coins, ncoins-1, total) + change_count(coins, ncoins, total-coins[ncoins])   \n",
 122     "  end\n",
 123     "end"
 124    ]
 125   },
 126   {
 127    "cell_type": "code",
 128    "execution_count": 6,
 129    "metadata": {
 130     "collapsed": false
 131    },
 132    "outputs": [
 133     {
 134      "name": "stdout",
 135      "output_type": "stream",
 136      "text": [
 137       "[1, 2, 5] coins finding 5\n",
 138       "[1, 2] coins finding 5\n",
 139       "[1] coins finding 5\n",
 140       "[] coins finding 5\n",
 141       "[1, 2, 5, 10, 20, 50, 100] coins finding 5\n",
 142       "[] coins finding 4\n",
 143       "[1, 2, 5, 10, 20, 50, 100] coins finding 4\n",
 144       "[] coins finding 3\n",
 145       "[1, 2, 5, 10, 20, 50, 100] coins finding 3\n",
 146       "[] coins finding 2\n",
 147       "[1, 2, 5, 10, 20, 50, 100] coins finding 2\n",
 148       "[] coins finding 1\n",
 149       "[1, 2, 5, 10, 20, 50, 100] coins finding 1\n",
 150       "[] coins finding 0\n",
 151       "[1] coins finding 3\n",
 152       "[] coins finding 3\n",
 153       "[1, 2, 5, 10, 20, 50, 100] coins finding 3\n",
 154       "[] coins finding 2\n",
 155       "[1, 2, 5, 10, 20, 50, 100] coins finding 2\n",
 156       "[] coins finding 1\n",
 157       "[1, 2, 5, 10, 20, 50, 100] coins finding 1\n",
 158       "[] coins finding 0\n",
 159       "[1] coins finding 1\n",
 160       "[] coins finding 1\n",
 161       "[1, 2, 5, 10, 20, 50, 100] coins finding 1\n",
 162       "[] coins finding 0\n",
 163       "[1] coins finding -1\n",
 164       "[1, 2] coins finding 0\n",
 165       "[1, 2, 5] coins finding -5\n"
 166      ]
 167     },
 168     {
 169      "data": {
 170       "text/plain": [
 171        "4"
 172       ]
 173      },
 174      "execution_count": 6,
 175      "metadata": {},
 176      "output_type": "execute_result"
 177     }
 178    ],
 179    "source": [
 180     "change_count(coins, 3, 5)"
 181    ]
 182   },
 183   {
 184    "cell_type": "code",
 185    "execution_count": 40,
 186    "metadata": {
 187     "collapsed": false
 188    },
 189    "outputs": [
 190     {
 191      "data": {
 192       "text/plain": [
 193        ":change_count_dp"
 194       ]
 195      },
 196      "execution_count": 40,
 197      "metadata": {},
 198      "output_type": "execute_result"
 199     }
 200    ],
 201    "source": [
 202     "def change_count_dp(coins, total, debug: false)\n",
 203     "  ncoins = coins.length - 1\n",
 204     "  ways = {}\n",
 205     "  (0..total).each do |t|\n",
 206     "    (0..ncoins).each do |n|\n",
 207     "      ways[[n, t]] = 1\n",
 208     "    end\n",
 209     "  end\n",
 210     "  \n",
 211     "  (1..total).each do |t|\n",
 212     "    (0..ncoins).each do |n|\n",
 213     "      # including this coin\n",
 214     "      if t >= coins[n]\n",
 215     "        including = ways[[n, t-coins[n]]]\n",
 216     "      else\n",
 217     "        including = 0\n",
 218     "      end\n",
 219     "      \n",
 220     "      # excluding this coin\n",
 221     "      if n >= 1\n",
 222     "        excluding = ways[[n-1, t]]\n",
 223     "      else\n",
 224     "        excluding = 0\n",
 225     "      end\n",
 226     "      \n",
 227     "      puts \"n: #{n} (#{coins[n]}p), t: #{t}, inc: #{including}, exc: #{excluding}\" if debug\n",
 228     "      ways[[n, t]] = including + excluding\n",
 229     "    end\n",
 230     "  end\n",
 231     "  \n",
 232     "  ways[[ncoins, total]]\n",
 233     "  # ways\n",
 234     "end"
 235    ]
 236   },
 237   {
 238    "cell_type": "code",
 239    "execution_count": 41,
 240    "metadata": {
 241     "collapsed": false
 242    },
 243    "outputs": [
 244     {
 245      "data": {
 246       "text/plain": [
 247        "[0, 1, 2, 3, 4, 5, 6, 7, 8]"
 248       ]
 249      },
 250      "execution_count": 41,
 251      "metadata": {},
 252      "output_type": "execute_result"
 253     }
 254    ],
 255    "source": [
 256     "(0..8).to_a"
 257    ]
 258   },
 259   {
 260    "cell_type": "code",
 261    "execution_count": 45,
 262    "metadata": {
 263     "collapsed": false
 264    },
 265    "outputs": [
 266     {
 267      "name": "stdout",
 268      "output_type": "stream",
 269      "text": [
 270       "n: 0 (1p), t: 1, inc: 1, exc: 0\n",
 271       "n: 1 (2p), t: 1, inc: 0, exc: 1\n",
 272       "n: 2 (5p), t: 1, inc: 0, exc: 1\n",
 273       "n: 3 (10p), t: 1, inc: 0, exc: 1\n",
 274       "n: 4 (20p), t: 1, inc: 0, exc: 1\n",
 275       "n: 5 (50p), t: 1, inc: 0, exc: 1\n",
 276       "n: 6 (100p), t: 1, inc: 0, exc: 1\n",
 277       "n: 7 (200p), t: 1, inc: 0, exc: 1\n",
 278       "n: 0 (1p), t: 2, inc: 1, exc: 0\n",
 279       "n: 1 (2p), t: 2, inc: 1, exc: 1\n",
 280       "n: 2 (5p), t: 2, inc: 0, exc: 2\n",
 281       "n: 3 (10p), t: 2, inc: 0, exc: 2\n",
 282       "n: 4 (20p), t: 2, inc: 0, exc: 2\n",
 283       "n: 5 (50p), t: 2, inc: 0, exc: 2\n",
 284       "n: 6 (100p), t: 2, inc: 0, exc: 2\n",
 285       "n: 7 (200p), t: 2, inc: 0, exc: 2\n",
 286       "n: 0 (1p), t: 3, inc: 1, exc: 0\n",
 287       "n: 1 (2p), t: 3, inc: 1, exc: 1\n",
 288       "n: 2 (5p), t: 3, inc: 0, exc: 2\n",
 289       "n: 3 (10p), t: 3, inc: 0, exc: 2\n",
 290       "n: 4 (20p), t: 3, inc: 0, exc: 2\n",
 291       "n: 5 (50p), t: 3, inc: 0, exc: 2\n",
 292       "n: 6 (100p), t: 3, inc: 0, exc: 2\n",
 293       "n: 7 (200p), t: 3, inc: 0, exc: 2\n",
 294       "n: 0 (1p), t: 4, inc: 1, exc: 0\n",
 295       "n: 1 (2p), t: 4, inc: 2, exc: 1\n",
 296       "n: 2 (5p), t: 4, inc: 0, exc: 3\n",
 297       "n: 3 (10p), t: 4, inc: 0, exc: 3\n",
 298       "n: 4 (20p), t: 4, inc: 0, exc: 3\n",
 299       "n: 5 (50p), t: 4, inc: 0, exc: 3\n",
 300       "n: 6 (100p), t: 4, inc: 0, exc: 3\n",
 301       "n: 7 (200p), t: 4, inc: 0, exc: 3\n",
 302       "n: 0 (1p), t: 5, inc: 1, exc: 0\n",
 303       "n: 1 (2p), t: 5, inc: 2, exc: 1\n",
 304       "n: 2 (5p), t: 5, inc: 1, exc: 3\n",
 305       "n: 3 (10p), t: 5, inc: 0, exc: 4\n",
 306       "n: 4 (20p), t: 5, inc: 0, exc: 4\n",
 307       "n: 5 (50p), t: 5, inc: 0, exc: 4\n",
 308       "n: 6 (100p), t: 5, inc: 0, exc: 4\n",
 309       "n: 7 (200p), t: 5, inc: 0, exc: 4\n"
 310      ]
 311     },
 312     {
 313      "data": {
 314       "text/plain": [
 315        "4"
 316       ]
 317      },
 318      "execution_count": 45,
 319      "metadata": {},
 320      "output_type": "execute_result"
 321     }
 322    ],
 323    "source": [
 324     "change_count_dp(coins, 5, debug: true)"
 325    ]
 326   },
 327   {
 328    "cell_type": "code",
 329    "execution_count": 43,
 330    "metadata": {
 331     "collapsed": false
 332    },
 333    "outputs": [
 334     {
 335      "data": {
 336       "text/plain": [
 337        "73682"
 338       ]
 339      },
 340      "execution_count": 43,
 341      "metadata": {},
 342      "output_type": "execute_result"
 343     }
 344    ],
 345    "source": [
 346     "change_count_dp(coins, 200)"
 347    ]
 348   },
 349   {
 350    "cell_type": "code",
 351    "execution_count": null,
 352    "metadata": {
 353     "collapsed": true
 354    },
 355    "outputs": [],
 356    "source": []
 357   }
 358  ],
 359  "metadata": {
 360   "kernelspec": {
 361    "display_name": "Ruby 2.4.0",
 362    "language": "ruby",
 363    "name": "ruby"
 364   },
 365   "language_info": {
 366    "file_extension": ".rb",
 367    "mimetype": "application/x-ruby",
 368    "name": "ruby",
 369    "version": "2.4.0"
 370   }
 371  },
 372  "nbformat": 4,
 373  "nbformat_minor": 0
 374 }