Project Euler Problem 31

Problem 31

22 November 2002

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

It is possible to make £2 in the following way:

1£1 + 150p + 220p + 15p + 12p + 31p

How many different ways can £2 be made using any number of coins?

Answer: 73682

 

 

C#

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace ConsoleApplication1 {
    static class Program {
        static int[] coins = { 1, 2, 5, 10, 20, 50, 100, 200 };        
        static int n(int price, int maxCoin) {
            if (price <= 1) return 1;

            int count = 0;
            foreach(var coin in coins.Reverse()) {
                if (price >= coin && coin <= maxCoin) count += n(price - coin, coin);                
            }
            return count;
        }
        static int n(int price) {
            return n(price, 200);
        }

        static void Main(string[] args) {
            //foreach(var x in Enumerable.Range(1, 200))
            //    Console.WriteLine(x + " " + n(x));
            Console.WriteLine(n(200));
        }
    }
}

Racket

 

#lang racket
(define coins '(200 100 50 20 10 5 2 1))
(define (n price)
  (let fn ([price price]
           [maxCoin 200])
    (let/ec return
      (when (<= price 1) (return 1))
      (define count 0)
      (for ([coin coins])
        (when (and (<= coin price)
                   (<= coin maxCoin))
          (set! count (+ count (fn (- price coin) coin)))))
      (return count))))

(define (problem31)
  (displayln (n 200)))
(problem31)