# Vending Machine

Build a function that takes a string of coins ending with an item index, and generates change as a string of coins using the least amount of coins possible.

The following are the items that can be bought (0-indexed):

[0.45, 0.60, 0.75, 0.95, 1.10, 1.25, 1.40, 1.50, 1.75, 2.00]

The following are the coins that can be used, with their abbreviations:

n = 0.05
d = 0.10
q = 0.25
D = 1.00


If an invalid item is selected, or the coins supplied are not enough to purchase the item, all $is returned in the least number of coins possible. If exact change is given, an empty string should be returned # Test Cases Dq4 = dn qqqq4 = D qqddddd10 = D qqn0 = d Dddd5 = n qq0 = n DD3 = Dn Dd4 = DDnn9 = d  Assume that input will only contain valid coin characters and will always terminate in an integer. This is my first posted question, so be please be gentle when telling me how I screwed up asking it. :) • Related Jun 9, 2017 at 17:17 • Is that a bad thing? I tried to come up with something new and pulled this from some c++ homework I did a few years ago. Jun 9, 2017 at 17:24 • Welcome to PPCG, in the future you should submit your questions to our sandbox for feedback before posting your question. That way you don't have to worry about people "being gentle" on your first post Jun 9, 2017 at 17:25 • You need to clarify the inputs here. Are there three inputs (map of coin values, list of item prices, string of coins)? – user62131 Jun 9, 2017 at 17:26 • I'm pretty sure I said the same thing to my teacher at the time and he told me that was just part of the lesson. My solution for it was to immediately check if the string contained more than one digit and then just return the$ Jun 9, 2017 at 17:39

### Python 3 - 219 213 Bytes

Fixed whitespace...

So this is awful as of right now....

def x(s):
v={'n':.05,'d':.1,'q':.25,'D':1}
r=sum([v[c]for c in s[:-1]])-[.45,.6,.75,.95,1.1,1.25,1.4,1.5,1.75,2.0][int(s[-1])]
o=''
for x in'Dqdn':
r=round(r, 2)
while v[x]<=r:
r-=v[x]
o+=x
return o


I'll go back to see if I can't get it golfed down at all...

• Watch your whitespace. You can use tabs (although they don't show up in PPCG) and spaces alternatively also. IE, for the first level, one space. For the second level, one tab. For the third level, a tab and a space. Right now you have 5 (!) spaces for your third level. Jun 9, 2017 at 17:51
• I've never figured out how to get that to work right in tio xD Jun 9, 2017 at 17:52
• In regards to your comments about the test cases, If an invalid item is selected, or the coins supplied are not enough to purchase the item, all $is returned in the least number of coins possible. Jun 9, 2017 at 18:10 • I guess I should read more carefully Jun 9, 2017 at 18:12 • @PunPun1000 you're right, I think range(.45,1.4,.15)+range(1.5,2,.25) will help, though I know little about Python. Jun 9, 2017 at 18:39 # Python 2, 192 176 bytes -16 bytes thanks to @JonathanAllan s=input() v=0 while sin'qndD':v+=[1,2,20,5][ord(s)%11];s=s[1:] x=int(s) v-=x<10and x<=v and[9,12,15,19,21,25,28,30,35,40][x] print v/20*'D'+v%20/5*'q'+v%5/2*'d'+v%5%2*'n'  Try it online! • I may be wrong, but I think your golfed program's outputs are off for a few test cases (Dq4, qqqq4, Dd4). Sep 10, 2017 at 14:07 # Java (OpenJDK 8), 281 271 bytes -10 bytes thanks to Jonathan Allan p->{int d[]={9,12,15,19,22,25,28,30,35,40},v[]={20,5,2,1},s=0,t;String m="Dqdn",n="";for(char c:p.toCharArray())s+=(t=m.indexOf(c))<0?0:v[t];t=p.charAt(p.length()-1)-48;s-=p.matches(".*\\d\\d")|s<d[t]?0:d[t];for(t=0;s>0;)if(s>=v[t++]){n+=m.charAt(--t);s-=v[t];}return n;}  Lambda that takes and returns a String Try it online! Ungolfed: p->{ int d[]={9,12,15,19,22,25,28,30,35,40}, v[]={20,5,2,1}, s=0, t; String m="Dqdn", n=""; for(char c:p.toCharArray()) s+= (t=m.indexOf(c))<0 ? 0 : v[t]; t=p.charAt(p.length()-1)-48; s-= p.matches(".*\\d\\d") | s<d[t] ? 0 : d[t]; for(t=0;s>0;) if(s>=v[t++]){ n+=m.charAt(--t); s-=v[t]; } return n; }  • @JonathanAllan Nice catch Jun 12, 2017 at 12:03 # PHP, 258 Bytes $i=array(45,60,75,95,110,125,140,150,175,200);$c=array(D=>100,q=>25,d=>10,n=>5);$a=str_split($argv);$p=$i[array_pop($a)];foreach($a as$x){$t+=$c[$x];$p=$c[$x]?$p:0;}$p=$t<$p?0:$p;while($t>$p){foreach($c as $n=>$x){if($t-$p>=$x){$t-=$x;echo$n;break;}}}


Ungolfed:

$i=array(45,60,75,95,110,125,140,150,175,200);$c=array(D=>100,q=>25,d=>10,n=>5);
$a=str_split($argv);
$p=$i[array_pop($a)]; foreach($a as $x){$t+=$c[$x];
$p=$c[$x]?$p:0;
}
$p=$t<$p?0:$p;
while($t>$p){
foreach($c as$n=>$x){ if($t-$p>=$x){
$t-=$x;
echo $n; break; } } }  • your coin array declaration is missing quotes and$t needs to be defined before you can add to it $c=array('D'=>100,'q'=>25,'d'=>10,'n'=>5);$t=0; Once I added those I was able to run and get some good results, but qqddddd10 failed Jun 9, 2017 at 21:04
• It worked for me, but maybe there's differences in PHP versions (I'm using 5.3.29). I seem to be able to get away with not initializing variables, and it just acts like it was 0 to begin with. Maybe there's error notifications not showing because of my PHP configuration? Jun 9, 2017 at 22:08

# JavaScript (ES6), 230 219 bytes

-10 bytes thanks to @JonathanAllan's idea of dividing all values by 5.
-1 byte by moving b="Dqdn" into the empty s.pop() function call.

s=>(a=[20,5,2,1],s=s.match(/\D|\d+/g),i=[9,12,15,19,22,25,28,30,35,40][s.pop(b="Dqdn")]||0,p=s.map(c=>a[b.search(c)]).reduce((y,z)=>y+z,0),(c=p-i)<0&&(c=p),a.map(v=>(x=c/v|0,c-=x*v,x)).map((v,j)=>b[j].repeat(v)).join)


## Ungolfed

input => {
values = [20,5,2,1];
coins = "Dqdn";
input = input.match(/\D|\d+/g);
item = [9,12,15,19,22,25,28,30,35,40][input.pop()] || 0;
payment = input.map(c => values[coins.search(c)]).reduce((y,z) => y+z, 0);
change = payment - item;
if (change < 0) change = payment;
return values.map(val => {
count = change/val | 0;
change -= count * val;
return count;
}).map((count,j) => coins[j].repeat(count))
.join
}


## Test Snippet

f=
s=>(a=[20,5,2,1],s=s.match(/\D|\d+/g),i=[9,12,15,19,22,25,28,30,35,40][s.pop(b="Dqdn")]||0,p=s.map(c=>a[b.search(c)]).reduce((y,z)=>y+z,0),(c=p-i)<0&&(c=p),a.map(v=>(x=c/v|0,c-=x*v,x)).map((v,j)=>b[j].repeat(v)).join)
Input<br><input oninput="O.value=/\D+\d+/.test(I.value)?f(I.value)||<empty>:" id="I"><br>Result<br><input id="O" disabled>

• @JonathanAllan Good thinking, that did indeed save 10 bytes. Thanks! Jun 11, 2017 at 6:22

## C++, 375371 370 bytes

-5 bytes thanks to Zacharý

#include<map>
#include<vector>
#include<string>
std::map<int,int>c={{'n',1},{'d',2},{'q',5},{68,20}};void v(std::string&e){int m=0,i=0,h=0;for(;i<e.size();++i)h+=e[i]>47&&e[i]<58;m=i=0;for(;i<e.size()-1;++i)m+=c[e[i]];if(h==1){i=std::vector<int>{9,12,15,19,22,25,28,30,35,40}[e[e.size()-1]-48];m-=(m>=i)*i;}e="";for(auto&g:{68,113,100,110})while(m>=c[g]){m-=c[g];e+=g;}}

• h+=(e[i]>47&&e[i]<58) can be h+=e[i]>47&&e[i]<58, since && has higher priority than assignment/modified assignment. m=(i=0) can be m=i=0 since assignment's associativity is right-to-left, and I also think that can be moved into the for-loop that follows it. And also, can the 'D' become 68? Sep 10, 2017 at 16:05
• I'm assuming replacing 'D' with 68 didn't work? Sep 10, 2017 at 20:25
• @Zacharý Replacing 'D' alone with 68 does not work, because of the auto keyword usage, if you have 2 different types ( even implicitly cast-able, like int and short ), the compiler can't guess what type you want and will return an error. It's the same rules as c++ template type argument declaration, where all types must match exactly. I switched all list from char to int Sep 11, 2017 at 5:42
• 264 bytes Jan 10, 2021 at 4:41

# Jelly,  68  64 bytes

Vị“€ÐŒæı÷œ#(µ‘
ḟ®µL⁼1ȧÇ


Try it online! or see the test suite.

### How?

Vị“€ÐŒæı÷œ#(µ‘ - Link 1, item price / 5: list of digit characters, d  e.g."4"   or "10"
V              - evaluate d as Jelly code                                  4        10
“€ÐŒæı÷œ#(µ‘ - code page indexes = [12,15,19,22,25,28,30,40,9]
ị             - index into (1-indexed and modular)                       22        12

ḟ®µL⁼1ȧÇ - Link 2, item price / 5: list of characters, s              e.g."Dq4" or "Dq10"
®       - recall register value = "Dqdn" (see Main)
ḟ        - filter discard from s                                          "4"      "10"
µ      - monadic chain separation, call that d
L⁼1   - length equals 1?                                                1         0
ȧ  - logical and                                                    22         0

“Þ¦£‘                                    - code page indexes = [20,5,2]
ɓ                                   - dyadic chain separation, left=s right=that
“Dqdn”                             - literal = "Dqdn"
©                            - copy to register and yield
Ð€                         - map across c in s:
⁹                       -   chain's right argument = [20,5,2]
1,0                   -   1 pair 0 = [1,0]
;                      -   concatenate = [20,5,2,1,0]
ị                        - index into (1-indexed)       [20,5,5,5,5,0]
S                 - sum                                    40
⁸            -   chain's left argument = s
?             - if:
<              -          less than (coins not enough?)  0
¹                - ...then: identity (do nothing, would be 40)
_               - ...else: subtract                      18
;         - concatenate with right          [18,20,5,2]
\       - cumulative reduce by
%        -   modulo                        [18,18,3,1]
⁹     -   chain's right argument = [20,5,2]
:      - integer division                [ 0, 3,1,1]
®    - recall register value = "Dqdn"
ż   - zip       [['D',0],['q',3],['d',1],['n',1]]
Œṙ - run-length decode                   "qqqdn"

• this is the largest Jelly program I've ever seen, by a significant margin Jun 12, 2017 at 12:20
• @Mayube Prospective meme re-tag: "longest Jelly". Google search (this submission actually does have less in the way of bytes used for compressed data than many I believe). Jun 12, 2017 at 22:26