How many ways can one make a single US dollar from exactly 10 coins? Write a program that calculates the answer to this. For bonus points, write one that can calculate the answer for any amount of money and any amount of coins.
50 cent pieces, quarters, dimes, nickels, and pennies are allowed.
The answer to the problem is 6. ENTERPRISE C SOLUTION in the next post.
Name:
Anonymous2010-01-10 4:36
#include <stdio.h>
int main(void) { printf("6\n"); return 0; }
/**********************************************************************
* Fuck y'all niggas, I'm not using the 80 character width standard *
* And you'd better set your tab width to 4 spaces *
**********************************************************************/
#include <stdio.h>
int debug = 0;
int money, coinmax;
int calc()
{
int valids = 0;
int halfds, quarters, dimes, nickels, pennies;
>>3 /**********************************************************************
* Fuck y'all niggas, I'm not using the 80 character width standard *
* And you'd better set your tab width to 4 spaces *
**********************************************************************/
I like the way you think, OP.
Interesting. After some examination, you can break a half dollar into two variations of five coins: quarter dime dime nickel nickel nickel, and dime dime dime dime dime.
Never noticed that before.
Name:
Anonymous2010-01-10 14:55
Can this be done recursively?
Name:
Anonymous2010-01-10 14:56
>>10
And that's the sound of me failing. That should just be:
>> quarter dime nickel nickel nickel
>>13
I did it in C# recursively. I can't see why memory should be a problem - unless I'm mistaken the stack depth shouldn't be more than the amount of coins?
I made it a bit more dynamic. You can change the values for amount of money, amount of coins and the amount and types of coins.
using System;
namespace ValueSplit
{
class Program
{
//change these values to fit another problem
static int amountOfMoney = 100, amountOfCoins = 10;
static int[] coins = new int[] { 50, 25, 10, 5, 1};
>>23 Especially not classes. Nor type names of any kind. Nor anything.
Name:
Anonymous2010-01-11 1:28
Obligatory Java. The actual algorithm is the coinTrick() and writeCoupon() methods. You can adjust the contents of the purse (what coins and how much they are worth) but I have not written the user-level method to do that; all methods assume they are working with initially unknown pocket change.
writeCoupon() ensures that only unique solutions are counted. The program accrues extra work load transforming the unique solutions into user-friendly strings for console display in finalResults() and printChange().
public class TheTrick
{
public static void main(String[] args)
{
CoinTrick trick = new CoinTrick(10, 1.00d);
trick.play();
}
}
class CoinTrick
{
private String purse = "pndqh";
private int[] purse_worth = { 1, 5, 10, 25, 50 };
private int draw = purse.length() - 1;
public int numOfCoins;
public double amount;
public int clen = 0;
public String coupon = new String("");
// Start the program
public void play()
{
String coins = new String("");
this.coupon = new String("");
this.clen = 0;
for(; draw >= 0; draw--)
{
coins = "" + this.initAmount((int)(this.amount*100), draw);
this.coinTrick(coins, coins.length());
}
this.finalResults();
}
// Produce a basic group of coins equal to 'amt'
// Higher-value coins are prioritized
// If you get more coins than you are allowed
protected String initAmount(int amt, int n)
{
String str = new String("");
int len = purse.length() - 1, draws = n;
if(len < draws) { draws = len; }
// Used to exchange larger coins for smaller coins
protected String makeChange(char c)
{
switch(c)
{
case 'h': return "qq";
case 'q': return "ddn";
case 'd': return "nn";
case 'n': return "ppppp";
default: return ("" + c);
}
}
// Outputs information ONLY regarding unique solutions
protected void finalResults()
{
System.out.println("Using "+this.numOfCoins+" coins, I have found "+this.clen+" unique ways to produce $"+this.amount+".");
String[] output = coupon.split("\\s");
int i = 0, j = output.length;
for(; i < j; i++)
{
this.printChange(output[i]);
}
}
// Has a branched output depending on input
// The "true" branch involves unique solutions
// The "false" branch involves raw solutions
protected void printChange(String str)
{
int i = 0, j = 0, n = 0, p = purse.length() - 1;
if(str.indexOf(",") != -1)
{
String[] bStr = str.split(",");
j = bStr.length;
for(; i < j; i++)
{
n = Integer.parseInt(bStr[i]);
while(n-- > 0)
{
System.out.print(""+this.purse_worth[(p - i)]+" ");
}
}
}
else
{
j = str.length();
for(; i < j; i++)
{
System.out.print("" + purse_worth[purse.indexOf(str.charAt(i))]+ " ");
}
}
System.out.println("");
}
}
Name:
Anonymous2010-01-11 10:30
Where are all the good languages? I expected to see some interesting Perl at the least. Instead two of the languages /prog/ deems as jokes have posted solutions.
Name:
Anonymous2010-01-11 10:37
>>26
``There are the languages everyone complains about, and there are the languages no one uses.'
>>26
Too busy writing real code, which doesn't leave enough time to solve toy problems on /prog/.
Name:
Anonymous2010-01-11 11:08
>>28
Why would such Real Good Programmers visit /prog/?
Name:
Anonymous2010-01-11 11:42
>>26
I didn't post a solution because this is a trivial problem. Everyone who has read their SICP today is familiar with it, and it has been discussed to death on /prog/ already.
(define (coin-combinations n d coins)
(cond ((negative? d) 0)
((negative? n) 0)
((and (zero? n) (zero? d)) 1)
(else
(do ((c coins (cdr c))
(a 0 (+ a (coin-combinations (- n 1) (- d (car c)) c))))
((null? c) a)))))