euler-031-coin-sums-20130801.ipynb

{
 "metadata": {
  "name": "euler-031-coin-sums-20130801"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "In England the currency is made up of pound, \u00a3, and pence, p, and there are eight coins in general circulation:  \n",
      "\n",
      "> 1p, 2p, 5p, 10p, 20p, 50p, \u00a31 (100p) and \u00a32 (200p).  \n",
      "\n",
      "It is possible to make \u00a32 in the following way:  \n",
      "\n",
      "> 1\u00d7\u00a31 + 1\u00d750p + 2\u00d720p + 1\u00d75p + 1\u00d72p + 3\u00d71p  \n",
      "\n",
      "How many different ways can \u00a32 be made using any number of coins?  "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "5//2"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 1,
       "text": [
        "2"
       ]
      }
     ],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def foo(n, coins):\n",
      "    total = 0\n",
      "    coins = sorted(coins, reverse=True)\n",
      "    if n == 0:\n",
      "        return 1\n",
      "    if len(coins) == 1:\n",
      "        return 1\n",
      "    for i in range(n//coins[0] + 1):\n",
      "        # print i\n",
      "        total += foo(n - i*coins[0], coins[1:])\n",
      "    return total"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%timeit foo(200, [1, 2, 5, 10, 20, 50, 100, 200])\n",
      "foo(200, [1, 2, 5, 10, 20, 50, 100, 200])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1 loops, best of 3: 231 ms per loop\n"
       ]
      },
      {
       "output_type": "pyout",
       "prompt_number": 3,
       "text": [
        "73682"
       ]
      }
     ],
     "prompt_number": 3
    }
   ],
   "metadata": {}
  }
 ]
}