Problem 031: Coin sums
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?
>00000000010p20p30p40p50p60p70p80p90p "d"2* 11p921p031p 0v
p >^ ^6+**45g05+*"2"g04+*g0<v<
^12-1< v< v <|-g11 <
>$31g.@ >1-21p ^
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)|