Coin sums

2014-09-18

Problem 031: Coin sums

Description:

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 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

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

Solution:

v#########
###

>00000000010p20p30p40p50p60p70p80p90p  "d"2*  11p921p031p 0v
v                                                         $<
             vp0p12:+1g120<  >g25**+70g5*+80g2*+90g+v
>21g0g1+21g0p>21g9-       |>10g5"d"**20g2"d"**+"d"3v>:11g\`|
p                         >^ ^6+**45g05+*"2"g04+*g0<v<
^12-1<                              v<      v       <|-g11 <
     |                           -1:<|g0:g12<p13+1g13<
     >$31g.@                         >1-21p ^

Start

Pause

Reset

Download

Output:

Stack: (0)

Explanation:

The algorithm here enumerates through every possible combination using an approach similar to counting binary:

Increment the last digit until our total sum is greater 200 (test for every combination if total sum == 200)
Then set every field from back to front to zero until you find a non-zero field
Set this field also to zero
Increment the field before ... repeat
Abort the loop when you have used every field

That is probably not the most efficient way, but I optimized this brute-force variant enough that it becomes viable.

Interpreter steps:	310 409 597
Execution time (BefunExec):	47s (6.47 MHz)
Program size:	60 x 11 (fully conform befunge-93)
Solution:	73682
Solved at:	2014-09-18