In Golfenhagen, The people are allowed, and encouraged, to melt down old coins for scrap metal, if the smelter can make a profit off of it. There are 5 coins that make the Golfenhagen mint. The half-penny(0.5)(H), the penny(1)(P), the tea (5)(T), the flag (10)(F), and the driver (25)(D). Golfenhagen also mints bills, in the form of 100(O), 500(E), 1000(N), and 2500(Y). Recently, the price of metals has plumetted to an all time low, and so everybody is trying to give their coins away, as they are worth less than the bills.

A humble software engineer decides to write a program that will guarantee that those who pay with cash will always get at least 9 coins back on any purchase whose net difference is bigger than 3 cents.

Your challenge:

Take on the role of developer, and write a program that takes one input (the net difference of the money handed out and the purchase total) and outputs the correct change.

You must:

  • Make your program put out a nominal of 9 coins with any decimal, except where the difference is less than 5 cents (5).
  • Make your program output a diverse set of coins, all coins MUST be able to be outputted by your program. no giving change in exclusively in halfcents.
  • Use the dollar bills where applicable.
  • This is a golf, the shortest code wins



This is a valid output. There are two dollars ("OO"), and 9 coins ("DDDTTTTTP ").


This is also valid output, as it specifies the currency type and quantities, and has 10 coins.


This is not valid output, as it only uses 3 coins.


This is not valid, see the second rule

Code example of a change counter for the least change possible. (as requested per cold golf)

package lookup;

public class Main {

    static void main(String[]s) {

        int changeincents = 53;
        int quartercount  =  0;
        int dimecount     =  0;
        int nickelcount   =  0;
        int pennycount    =  0;
        while(changeincents >= 25){//value of a quarter
        while(changeincents >= 10){
        while(changeincents >= 5){
        while(changeincents >= 1){

Good luck!

  • \$\begingroup\$ Use the dollar bills where applicable How will you ensure this rule is followed? Is there a way to calculate that using dollar bills is better in a specific situation? \$\endgroup\$ Commented Aug 22, 2016 at 18:45
  • 1
    \$\begingroup\$ I don't understand how one option is chosen when there's multiple choices. \$\endgroup\$
    – xnor
    Commented Aug 22, 2016 at 18:46
  • \$\begingroup\$ @ColdGolf well, aside from the 9 coins, the consumers typically want the least ammount of change possible. \$\endgroup\$
    – user56309
    Commented Aug 22, 2016 at 18:49
  • \$\begingroup\$ Is there a way to calculate "the least amount of change possible" in a given situation? \$\endgroup\$ Commented Aug 22, 2016 at 18:52
  • 2
    \$\begingroup\$ I also don’t really understand the question as it’s currently written. AIUI, there is some leeway, and there are multiple valid outputs for each input; is that right? \$\endgroup\$
    – lynn
    Commented Aug 22, 2016 at 22:11

1 Answer 1


Haskell, 177 165 bytes

Thanks to @Lynn.

f n|n>2504='Y':f(n-2500)|n>1004='N':f(n-1000)|n>504='E':f(n-500)|n>104='O':f(n-100)|n>29='D':f(n-25)|n>14='F':f(n-10)|n>9='T':f(n-5)|n>6='P':f(n-1)|0<1=[1..2*n]>>"H"

In a readable format:

f n
  | n > 2504 = "Y" ++ f(n-2500)
  | n > 1004 = "N" ++ f(n-1000)
  | n > 504 = "E" ++ f(n-500)
  | n > 104 = "O" ++ f(n-100)
  | n > 29 = "D" ++ f(n-25)
  | n > 14 = "F" ++ f(n-10)
  | n > 9 = "T" ++ f(n-5)
  | n > 6 = "P" ++ f(n-1)
  | 0 < 1 = replicate (2*n) 'H'

Just give out the biggest denomination which still leaves more than 5 cents to fill with halfcoins.

  • \$\begingroup\$ Some tips: replicate(2*n)'H' is [1..2*n]>>"H", and "A"++b is 'A':b. \$\endgroup\$
    – lynn
    Commented Aug 22, 2016 at 22:07