# Where are my pennies?

Given string S representing a dollar amount, make change for that amount of money use the least number of coins to make the change and record the amount of each coin in a list. Here are the coins available to use and their value.

Coin : Value
Dollar Coins : $1.00 Quarters:$0.25
Dimes: $0.10 Nickels:$0.05

## Output

List of coin numbers separated by a space character " ". The list must be in this order: Dollar coins, quarters, dimes, nickels, pennies.

## Constraints

• $0.00 < S <$10.00
• S is given to two decimal places.
• make change for that amount of money use the least number of coins

## Example Input

$4.58 $9.99

## Output

4 2 0 1 3

9 3 2 0 4

## Win Condition

shortest bytes win.

• Do we have to get the $ sign in the input? I suggest allowing the number itself, either as a number or a string (optional). Apr 16 '18 at 18:48 • Knapsack problem, possible duplicate of codegolf.stackexchange.com/questions/162158/knapsack-problem – Angs Apr 16 '18 at 18:57 • @0x45 I'd upvote this if you remove the $-sign requirement in the input, and make the output format optional... Apr 16 '18 at 19:03
• Fair enough... You might want to read this. Apr 16 '18 at 19:16
• On further thought, this input format isn't interesting either. Because the format is always $d.dd, the symbols give no information and so just need to be stripped away or ignored. – xnor Apr 16 '18 at 23:39 ## 8 Answers # 05AB1E, 24 17 bytes ¦'.¡25‰10‰5‰r5F?' ?} ¦'.¡25‰T‰5‰ðý  Try it online! My first attempt at it. It's very verbose in my opinion and I'll look at further revising this answer. Maybe somebody better than me will figure it out. Explanation ¦ # Remove '$' from input
'.¡           # Push '.' and split string on that. (dollar),(cents) is result
25‰          # Push all items onto stack and mod top by 25
T‰           # Push all items onto stack and mod top by 10
5‰           # Push all items onto stack and mod top by 5
r            # Push all items onto stack and reverse stack
ðý            # Loop through stack and print each element with space


-7 bytes thanks to Emigna

• Some quick gains: Replace 10 with T and r5F?' ?} with ðý. Apr 16 '18 at 19:55
• @Emigna How did you go about translating the r5F?' ?} to ðý if you don't mind so that I can know for future challenges. Apr 16 '18 at 20:00
• ðý means join by space, which gives the same result as the print each with a space after that you were doing (except with a trailing newline instead of a trailing space) Apr 16 '18 at 20:19
• @Emigna Oh! I see now. I thought i was some sort of weird encoding, but it is literally push space and b.join(a). I got it now. Thanks :) Apr 16 '18 at 21:01

# Python 2, 7972 71 bytes

s=input()
d=int(s[1]+s[3:])
for c in(100,25,10,5,1):print d/c,;d-=d/c*c


Try it online!

Saved 7 bytes thanks, in part, to Chas Brown

Saved a byte thanks to Jo King

• Save 6 via s=input();d=int(s[1]+s[-2:]). Apr 17 '18 at 3:13
• Thanks, I totally overlooked that the input was less than $10, though my previous was flexible. :$ Apr 17 '18 at 15:03
• What's the ~~ for?
– Jo King
Apr 19 '18 at 21:27
• @JoKing The ~ does a bitwise two's complement, and two of them reverses it, but essentially performs a Math.floor in many languages. And now I realize that the / operator does just that in Python 2 in this case. Thanks for pointing that out! Saved a byte. Apr 20 '18 at 13:53

# Hexagony, 353228 27 bytes

]{=?2'?!/@[1[5/P0;:!%'[01[5


Try it online!

There are no no-ops . now, so it must be optimal.

• -1 byte. This way of using "functions" in Hexagony is very interesting
– Jo King
Apr 17 '18 at 13:20

# R, 81 bytes

x=as.double(substr(scan(,""),2,6));for(i in 1/c(1,4,10,20,100))x=x-i*print(x%/%i)


Try it online!

26 bytes ensuring the data are a double rather than a string, very nearly a third of the program! That's lame, to say the least.

# Stax, 18 17 bytes

ä┐¢6ⁿ≡♠₧ç7╦Δ╛XÄR│


Run and debug it

# Ruby, 74 bytes

->s{n=s.delete("\$.").to_i;["%s"]*5*" "%[n/100,n/25%4,(m=n/5%5)/2,m%2,n%5]}


Try it online!

Converts input to an integer containing number of pennies, then applies formulas in the [] at the end.

5 bytes standard Ruby boilerplate ->s{}
34 bytes on solving the problem
35 bytes on formatting


# Java 8, 138 bytes

s->{long p=new Long(s.replaceAll("\\D","")),c,i=100;for(s="";i>0;s+=c+" ",i=i>25?25:i>10?10:i>5?5:i>1?1:0)for(c=0;p>=i;p-=i)c++;return s;}


Explanation:

Try it online.

s->{              // Method with String as both parameter and return-type
long p=new Long(s.replaceAll("\\D","")),
//  Remove all non-digits, and convert it to a number
c,         //  Count-integer
i=100;     //  Amount integer, starting at 100
for(s="";       //  Set the input to an empty String, because we no longer need it
i>0         //  Loop as long as i is not 0
;           //    After every iteration:
s+=c+" ",  //     Append the count and a space to s
i=i>25?    //     If i is 100:
25      //      Change it to 25
:i>10?   //     Else-if i is 25:
10      //      Change it to 10
:i>5?    //     Else-if i is 10:
5       //      Change it to 5
:i>1?    //     Else-if i is 5:
1       //      Change it to 1
:        //     Else (i is 1)
0)      //      Change it to 0
for(c=0;      //   Reset the count c to 0
p>=i;     //   Inner loop as long as p is larger than or equal to i
p-=i)     //     After every iteration: subtract i from p
c++;        //    Increase the count c by 1
return s;}      //  Return the result