5
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Related \$\endgroup\$ – L3viathan Jun 9 '17 at 17:17
  • \$\begingroup\$ 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. \$\endgroup\$ – Broom Jun 9 '17 at 17:24
  • 3
    \$\begingroup\$ 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 \$\endgroup\$ – PunPun1000 Jun 9 '17 at 17:25
  • \$\begingroup\$ You need to clarify the inputs here. Are there three inputs (map of coin values, list of item prices, string of coins)? \$\endgroup\$ – user62131 Jun 9 '17 at 17:26
  • 1
    \$\begingroup\$ 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 $ \$\endgroup\$ – Broom Jun 9 '17 at 17:39
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Stephen Jun 9 '17 at 17:51
  • \$\begingroup\$ I've never figured out how to get that to work right in tio xD \$\endgroup\$ – bendl Jun 9 '17 at 17:52
  • \$\begingroup\$ 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. \$\endgroup\$ – PunPun1000 Jun 9 '17 at 18:10
  • \$\begingroup\$ I guess I should read more carefully \$\endgroup\$ – bendl Jun 9 '17 at 18:12
  • 1
    \$\begingroup\$ @PunPun1000 you're right, I think range(.45,1.4,.15)+range(1.5,2,.25) will help, though I know little about Python. \$\endgroup\$ – Magic Octopus Urn Jun 9 '17 at 18:39
2
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ I may be wrong, but I think your golfed program's outputs are off for a few test cases (Dq4, qqqq4, Dd4). \$\endgroup\$ – Jonathan Frech Sep 10 '17 at 14:07
2
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ @JonathanAllan Nice catch \$\endgroup\$ – PunPun1000 Jun 12 '17 at 12:03
1
\$\begingroup\$

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;
    }
  }
}
\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – Broom Jun 9 '17 at 21:04
  • \$\begingroup\$ 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? \$\endgroup\$ – XMark Jun 9 '17 at 22:08
1
\$\begingroup\$

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>

\$\endgroup\$
  • \$\begingroup\$ @JonathanAllan Good thinking, that did indeed save 10 bytes. Thanks! \$\endgroup\$ – Justin Mariner Jun 11 '17 at 6:22
1
\$\begingroup\$

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;}}
\$\endgroup\$
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ – Zacharý Sep 10 '17 at 16:05
  • \$\begingroup\$ I'm assuming replacing 'D' with 68 didn't work? \$\endgroup\$ – Zacharý Sep 10 '17 at 20:25
  • \$\begingroup\$ @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 \$\endgroup\$ – HatsuPointerKun Sep 11 '17 at 5:42
0
\$\begingroup\$

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"
\$\endgroup\$
  • \$\begingroup\$ this is the largest Jelly program I've ever seen, by a significant margin \$\endgroup\$ – Skidsdev Jun 12 '17 at 12:20
  • \$\begingroup\$ @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). \$\endgroup\$ – Jonathan Allan Jun 12 '17 at 22:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.