Coin sums

Fork me on GitHub

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
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 ^
Stack:   (0)


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