extra/project-euler/031/031.factor

   1 ! Copyright (c) 2008 Aaron Schaefer.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel math project-euler.common ;
   4 IN: project-euler.031
   5
   6 ! http://projecteuler.net/index.php?section=problems&id=31
   7
   8 ! DESCRIPTION
   9 ! -----------
  10
  11 ! In England the currency is made up of pound, £, and pence, p, and there are
  12 ! eight coins in general circulation:
  13
  14 !     1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
  15
  16 ! It is possible to make £2 in the following way:
  17
  18 !     1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
  19
  20 ! How many different ways can £2 be made using any number of coins?
  21
  22
  23
  24 ! SOLUTION
  25 ! --------
  26
  27 <PRIVATE
  28
  29 : 1p ( m -- n )
  30     drop 1 ;
  31
  32 : 2p ( m -- n )
  33     dup 0 >= [ [ 2 - 2p ] [ 1p ] bi + ] [ drop 0 ] if ;
  34
  35 : 5p ( m -- n )
  36     dup 0 >= [ [ 5 - 5p ] [ 2p ] bi + ] [ drop 0 ] if ;
  37
  38 : 10p ( m -- n )
  39     dup 0 >= [ [ 10 - 10p ] [ 5p ] bi + ] [ drop 0 ] if ;
  40
  41 : 20p ( m -- n )
  42     dup 0 >= [ [ 20 - 20p ] [ 10p ] bi + ] [ drop 0 ] if ;
  43
  44 : 50p ( m -- n )
  45     dup 0 >= [ [ 50 - 50p ] [ 20p ] bi + ] [ drop 0 ] if ;
  46
  47 : 100p ( m -- n )
  48     dup 0 >= [ [ 100 - 100p ] [ 50p ] bi + ] [ drop 0 ] if ;
  49
  50 : 200p ( m -- n )
  51     dup 0 >= [ [ 200 - 200p ] [ 100p ] bi + ] [ drop 0 ] if ;
  52
  53 PRIVATE>
  54
  55 : euler031 ( -- answer )
  56     200 200p ;
  57
  58 ! [ euler031 ] 100 ave-time
  59 ! 3 ms ave run time - 0.91 SD (100 trials)
  60
  61 ! TODO: generalize to eliminate duplication; use a sequence to specify denominations?
  62
  63 SOLUTION: euler031