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
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

made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript