Vending Machine

Question

The Task

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. :)

Answer 1

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...

Answer 2

Python 2, 192 176 bytes

-16 bytes thanks to @JonathanAllan

s=input()
v=0
while s[0]in'qndD':v+=[1,2,20,5][ord(s[0])%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!

Answer 3

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;
}

Answer 4

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[1]);$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[1]);
$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;
    }
  }
}

Answer 5

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>

Answer 6

C++, 375 371 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;}}

Answer 7

Jelly,  68  64 bytes

Vị“€ÐŒæı÷œ#(µ‘
ḟ®µL⁼1ȧÇ
“Þ¦£‘ɓ“Dqdn”©iЀị⁹;1,0¤S¹_<?⁸Ǥ;%\:⁹®żŒṙ

A monadic link taking and returning lists of characters.

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
       Ç - call last link as a monad                                      22        12
      ȧ  - logical and                                                    22         0

“Þ¦£‘ɓ“Dqdn”©iЀị⁹;1,0¤S¹_<?⁸Ǥ;%\:⁹®żŒṙ - Main link: list of chars, s    e.g."Dqqqq4"
“Þ¦£‘                                    - 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:
             i                           -   1st index (0 if not found)  [1,2,2,2,2,0]
                      ¤                  - nilad followed by link(s) as a nilad:
                 ⁹                       -   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
                              ¤          - nilad followed by link(s) as a nilad:
                            ⁸            -   chain's left argument = s
                             Ç           -   call last link as a monad(s)         22
                           ?             - 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"