d2jsp
Log InRegister
d2jsp Forums > Off-Topic > Computers & IT > Programming & Development > The Change Problem :( > All The Ways To Make Change
Prev123456Next
Add Reply New Topic New Poll
Views: 1491Replies: 54Track Topic
Member
Posts: 4,605
Joined: Sep 15 2011
Gold: 9,464.00
#31
Nov 29 2012 05:25pm
actually, aside from the duplicates (which are easy to handle), this Python code actually works:

edit:super close!

Code
def change(n):
 ret = []
 ten_cents = ["2 nickels", "1 dime"]
 five_cents = ["1 nickel"]
 twofive_cents = ["1 quarter", "2 dimes 1 nickel", "1 dime 3 nickels", "5 nickels"]

 if n == 25:
   for z in twofive_cents:
     ret.append(z)

 if n == 10:
   for z in ten_cents:
     ret.append(z)

 if n == 5:
   for z in five_cents:
     ret.append(z)


 if n > 25:
   for x in change(n-25):
     for y in change(25):
       ret.append(x + y)
     for z in twofive_cents:
       ret.append(x + z)
   return ret
 if n > 10:
   for x in change(n-10):
     for y in change(10):
       ret.append(x + y)
     for z in ten_cents:
       ret.append(x + z)
   return ret
 if n > 5:
   for x in change(n-5):
     for y in change(5):
       ret.append(x + y)
     for z in five_cents:
       ret.append(x+z)
   return ret
 else:
   return [str(n) + " pennies "]


Code
change for 4:  ['4 pennies ']
change for 9:  ['4 pennies 5 pennies ', '4 pennies 1 nickel']
change for 10:  ['2 nickels', '1 dime', '5 pennies 5 pennies ', '5 pennies 1 nickel']
change for 14:  ['4 pennies 2 nickels', '4 pennies 1 dime', '4 pennies 5 pennies 5 pennies ', '4 pennies 5 pennies 1 nickel', '4 pennies 2 nickels', '4 pennies 1 dime']
change for 20:  ['2 nickels2 nickels', '2 nickels1 dime', '2 nickels5 pennies 5 pennies ', '2 nickels5 pennies 1 nickel', '2 nickels2 nickels', '2 nickels1 dime', '1 dime2 nickels', '1 dime1 dime', '1 dime5 pennies 5 pennies ', '1 dime5 pennies 1 nickel', '1 dime2 nickels', '1 dime1 dime', '5 pennies 5 pennies 2 nickels', '5 pennies 5 pennies 1 dime', '5 pennies 5 pennies 5 pennies 5 pennies ', '5 pennies 5 pennies 5 pennies 1 nickel', '5 pennies 5 pennies 2 nickels', '5 pennies 5 pennies 1 dime', '5 pennies 1 nickel2 nickels', '5 pennies 1 nickel1 dime', '5 pennies 1 nickel5 pennies 5 pennies ', '5 pennies 1 nickel5 pennies 1 nickel', '5 pennies 1 nickel2 nickels', '5 pennies 1 nickel1 dime']


you'll obviously need to do some deduping, but that part's fairly simple

This post was edited by irimi on Nov 29 2012 05:42pm
Member
Posts: 3,210
Joined: Aug 21 2010
Gold: 152.00
#32
Nov 29 2012 05:36pm
I'm not terribly familiar with python but is ret some sort of array/string ? and I'm assuming append is a way to add to it?
Member
Posts: 4,605
Joined: Sep 15 2011
Gold: 9,464.00
#33
Nov 29 2012 05:44pm
Quote (Nom_Nomz @ Nov 29 2012 04:36pm)
I'm not terribly familiar with python but is ret some sort of array/string ?  and I'm assuming append is a way to add to it?


yes. the only thing you need to know about python code is -- if it looks like what you think it is, then it probably is what you think it is.
Member
Posts: 3,210
Joined: Aug 21 2010
Gold: 152.00
#34
Nov 29 2012 06:09pm
remember those jumps I was talking about earlier? I can actually make them with if statements in the cases by decrementin type to the appropiate case under the appropriate conditions

it working so far gonna test it more...
Member
Posts: 16,144
Joined: Mar 27 2008
Gold: 14,618.00
#35
Nov 29 2012 06:20pm
I now have a badass simple solution xD (couldn't do it recursivley... but recursively is also brute-force... and this solution is even faster ;) )

Code
#include <stdio.h>

int main() {
 int amount;
 int pos = 0;
 int i, j, k, l;

 printf("Please enter the amount you wish to check in cents: ");
 scanf("%d", &amount);

 for(i=0; i*25<=amount; i++) {
   for(j=0; j*10<=amount; j++) {
     for(k=0; k*5<=amount; k++) {
       for(l=0; l<=amount; l++) {
         if (25*i + 10*j + 5*k + l == amount)
           pos++, printf("%d %d %d %d\n",i,j,k,l);
   }}}}
 printf("There are %d ways to make change with the amount %d\n", pos, amount);
 return 0;
}



edit: There are 142511 ways to make change with the amount 1000

This post was edited by Richter on Nov 29 2012 06:30pm
Member
Posts: 632
Joined: Apr 2 2010
Gold: 50.00
#36
Nov 29 2012 06:37pm
Heh, I also came up with a similar solution but I also wrote to file for easy result reading and pasting.

Code

#include <stdio.h>
#include <stdlib.h>

FILE *file;

int main() {
   
   file = fopen("coins.txt", "w+");
   
   int amount;
   printf("Enter money to count: ");
   scanf("%d", &amount);
   
   fprintf(file, "Q\tD\tN\tP\n");
   printf("Q\tD\tN\tP\n");
   
   int i, j, k;
   
   for(i=0; i <= amount/25; i++) {
       int dimeAmount = amount-i*25;
       for(j=0; j <= dimeAmount/10; j++) {
           int nickelAmount = dimeAmount-j*10;
           for(k=0; k <= nickelAmount/5; k++) {
               int p = nickelAmount-k*5;
               fprintf(file, "%d\t%d\t%d\t%d\n", i, j, k, p);
               printf("%d\t%d\t%d\t%d\n", i, j, k, p);
           }
       }
   }
   
   fclose(file);
   
   system("PAUSE");
   return 0;
}


Code

23 cents:
Q D N P
0 0 0 23
0 0 1 18
0 0 2 13
0 0 3 8
0 0 4 3
0 1 0 13
0 1 1 8
0 1 2 3
0 2 0 3

100 cents:
Q D N P
0 0 0 100
0 0 1 95
0 0 2 90
0 0 3 85
0 0 4 80
0 0 5 75
0 0 6 70
0 0 7 65
0 0 8 60
0 0 9 55
0 0 10 50
0 0 11 45
0 0 12 40
0 0 13 35
0 0 14 30
0 0 15 25
0 0 16 20
0 0 17 15
0 0 18 10
0 0 19 5
0 0 20 0
0 1 0 90
0 1 1 85
0 1 2 80
0 1 3 75
0 1 4 70
0 1 5 65
0 1 6 60
0 1 7 55
0 1 8 50
0 1 9 45
0 1 10 40
0 1 11 35
0 1 12 30
0 1 13 25
0 1 14 20
0 1 15 15
0 1 16 10
0 1 17 5
0 1 18 0
0 2 0 80
0 2 1 75
0 2 2 70
0 2 3 65
0 2 4 60
0 2 5 55
0 2 6 50
0 2 7 45
0 2 8 40
0 2 9 35
0 2 10 30
0 2 11 25
0 2 12 20
0 2 13 15
0 2 14 10
0 2 15 5
0 2 16 0
0 3 0 70
0 3 1 65
0 3 2 60
0 3 3 55
0 3 4 50
0 3 5 45
0 3 6 40
0 3 7 35
0 3 8 30
0 3 9 25
0 3 10 20
0 3 11 15
0 3 12 10
0 3 13 5
0 3 14 0
0 4 0 60
0 4 1 55
0 4 2 50
0 4 3 45
0 4 4 40
0 4 5 35
0 4 6 30
0 4 7 25
0 4 8 20
0 4 9 15
0 4 10 10
0 4 11 5
0 4 12 0
0 5 0 50
0 5 1 45
0 5 2 40
0 5 3 35
0 5 4 30
0 5 5 25
0 5 6 20
0 5 7 15
0 5 8 10
0 5 9 5
0 5 10 0
0 6 0 40
0 6 1 35
0 6 2 30
0 6 3 25
0 6 4 20
0 6 5 15
0 6 6 10
0 6 7 5
0 6 8 0
0 7 0 30
0 7 1 25
0 7 2 20
0 7 3 15
0 7 4 10
0 7 5 5
0 7 6 0
0 8 0 20
0 8 1 15
0 8 2 10
0 8 3 5
0 8 4 0
0 9 0 10
0 9 1 5
0 9 2 0
0 10 0 0
1 0 0 75
1 0 1 70
1 0 2 65
1 0 3 60
1 0 4 55
1 0 5 50
1 0 6 45
1 0 7 40
1 0 8 35
1 0 9 30
1 0 10 25
1 0 11 20
1 0 12 15
1 0 13 10
1 0 14 5
1 0 15 0
1 1 0 65
1 1 1 60
1 1 2 55
1 1 3 50
1 1 4 45
1 1 5 40
1 1 6 35
1 1 7 30
1 1 8 25
1 1 9 20
1 1 10 15
1 1 11 10
1 1 12 5
1 1 13 0
1 2 0 55
1 2 1 50
1 2 2 45
1 2 3 40
1 2 4 35
1 2 5 30
1 2 6 25
1 2 7 20
1 2 8 15
1 2 9 10
1 2 10 5
1 2 11 0
1 3 0 45
1 3 1 40
1 3 2 35
1 3 3 30
1 3 4 25
1 3 5 20
1 3 6 15
1 3 7 10
1 3 8 5
1 3 9 0
1 4 0 35
1 4 1 30
1 4 2 25
1 4 3 20
1 4 4 15
1 4 5 10
1 4 6 5
1 4 7 0
1 5 0 25
1 5 1 20
1 5 2 15
1 5 3 10
1 5 4 5
1 5 5 0
1 6 0 15
1 6 1 10
1 6 2 5
1 6 3 0
1 7 0 5
1 7 1 0
2 0 0 50
2 0 1 45
2 0 2 40
2 0 3 35
2 0 4 30
2 0 5 25
2 0 6 20
2 0 7 15
2 0 8 10
2 0 9 5
2 0 10 0
2 1 0 40
2 1 1 35
2 1 2 30
2 1 3 25
2 1 4 20
2 1 5 15
2 1 6 10
2 1 7 5
2 1 8 0
2 2 0 30
2 2 1 25
2 2 2 20
2 2 3 15
2 2 4 10
2 2 5 5
2 2 6 0
2 3 0 20
2 3 1 15
2 3 2 10
2 3 3 5
2 3 4 0
2 4 0 10
2 4 1 5
2 4 2 0
2 5 0 0
3 0 0 25
3 0 1 20
3 0 2 15
3 0 3 10
3 0 4 5
3 0 5 0
3 1 0 15
3 1 1 10
3 1 2 5
3 1 3 0
3 2 0 5
3 2 1 0
4 0 0 0
Member
Posts: 4,605
Joined: Sep 15 2011
Gold: 9,464.00
#37
Nov 29 2012 06:41pm
Quote (Richter @ Nov 29 2012 05:20pm)
I now have a badass simple solution xD (couldn't do it recursivley... but recursively is also brute-force... and this solution is even faster ;) )


ROFL. I mean, totally respect for even thinking of doing it this way, but what that solution boils down to is a dictionary attack on the problem... which is the definition of brute force.

I'd love to see you argue this: how is a recursive solution brute force?
Member
Posts: 32,925
Joined: Jul 23 2006
Gold: 3,804.50
#38
Nov 29 2012 08:29pm
Quote (irimi @ Nov 29 2012 07:10pm)
actually this is kind of annoying.  this should be pretty easy to solve lol - kind of embarrassed that i haven't come up with a stupidly simple solution to this yet.

fucking combinatorics.


afaik it's not quite that easy. it's a partition problem, aka generating functions. iirc it's the coefficient of x^n in (1-x)(1-x^5)(1-x^10)(1-x^25), but i could be wrong. haven't done it in a couple of years so i'm rusty

/edit: hmm that can't be right. not every x^n has a coefficient. oh well

This post was edited by carteblanche on Nov 29 2012 08:35pm
Member
Posts: 16,144
Joined: Mar 27 2008
Gold: 14,618.00
#39
Nov 30 2012 08:26am
Quote (irimi @ 30 Nov 2012 01:41)
I'd love to see you argue this: how is a recursive solution brute force?

well brute-force is a word which usually sounds bad. i'd better used the word straight-forward-calculation, so my solution sounds a bit more professional ;)
actually it's not a "real" brute-force, which tests all the possibilities. it takes out some possibilities which doesn't make sense... you can see that, looking a.e. at this statement:
Code
for(k=0; k*5<=amount; k++) {

i could test all possibilities but i dont need to, because i can stop a.e. when 'k*5 equals the total money'.

The complexity of my algorithm is at least as good as a recursive algorithm (or maybe I just still don't see any version of a recursive algorithm which makes actually sense for this problem). BECAUSE, if the recursive would be better, then it has to test less possibilities while finding the same amount of solutions.
IF the recursive solution finds more solutions, which first have to be composed together, then this is an additional effort:
a.e. 6 is '5 1' or '1 5'... these must be merged to one... while my solution doesn't even think about spitting two versions out :)

we could also calculate the complexity of our algorithms, but I think we won't find a solution which has less complexity (without storing huge amount of data or another disadvantage, which makes it impractical for large sizes).
Member
Posts: 32,925
Joined: Jul 23 2006
Gold: 3,804.50
#40
Nov 30 2012 11:51am
Quote (Richter @ Nov 30 2012 10:26am)

actually it's not a "real" brute-force, which tests all the possibilities. it takes out some possibilities which doesn't make sense... you can see that, looking a.e. at this statement:
Code
for(k=0; k*5<=amount; k++) {


That's still brute force lol.

consider an algorithm to determine if n is prime. you can check every number from 1 to n. i think you'll agree that's brute force. you can trim that considerably by checking 2 to sqrt(n). but that's still brute force. or you can check 2 and the odds from 3 to sqrt(n). that's still brute force.

and a recursive solution would probably break it up into pieces. eg: how many ways can i represent x cents in quarters? now peel off a quarter and calculate how many ways to represent a quarter via dimes/nickels/pennies. now peel off a second quarter. etc
Go Back To Programming & Development Topic List
Prev123456Next
Add Reply New Topic New Poll

© 2003-2026 d2jsp  Contact