r/dailyprogrammer • u/oskar_s • Jun 15 '12

[6/15/2012] Challenge #65 [easy]

Write a program that given a floating point number, gives the number of American dollar coins and bills needed to represent that number (rounded to the nearest 1/100, i.e. the nearest penny). For instance, if the float is 12.33, the result would be 1 ten-dollar bill, 2 one-dollar bills, 1 quarter, 1 nickel and 3 pennies.

For the purposes of this problem, these are the different denominations of the currency and their values:

Penny: 1 cent
Nickel: 5 cent
Dime: 10 cent
Quarter: 25 cent
One-dollar bill
Five-dollar bill
Ten-dollar bill
Fifty-dollar bill
Hundred-dollar bill

Sorry Thomas Jefferson, JFK and Sacagawea, but no two-dollar bills, half-dollars or dollar coins!

Your program can return the result in whatever format it wants, but I recommend just returning a list giving the number each coin or bill needed to make up the change. So, for instance, 12.33 could return [0,0,1,0,2,1,0,1,3] (here the denominations are ordered from most valuable, the hundred-dollar bill, to least valuable, the penny)

Thanks to Medicalizawhat for submitting this problem in /r/dailyprogrammer_ideas! And on behalf of the moderators, I'd like to thank everyone who submitted problems the last couple of days, it's been really helpful, and there are some great problems there! Keep it up, it really helps us out a lot!

15 Upvotes

permalink
reddit

You are about to leave Redlib

Do you want to continue?

https://www.reddit.com/r/dailyprogrammer/comments/v3a89/6152012_challenge_65_easy/
No, go back! Yes, take me to Reddit

91% Upvoted

u/emcoffey3 Jun 15 '12

So, I went really overboard on this, but I did so because I intend on using it in another application. The real meat of the class are in the private methods RecalculateDistribution() and CalcStep(). Also, I included twenties even though they weren't in the problem description.

using System;
using System.Collections.Generic;
using System.Text;
namespace RedditDailyProgrammer
{
    public class MoneyDistribution
    {
        #region Properties
        public int Hundreds { get { return distribution[100M]; } }
        public int Fifties { get { return distribution[50M]; } }
        public int Twenties { get { return distribution[20M]; } }
        public int Tens { get { return distribution[10M]; } }
        public int Fives { get { return distribution[5M]; } }
        public int Ones { get { return distribution[1M]; } }
        public int Quarters { get { return distribution[.25M]; } }
        public int Dimes { get { return distribution[.10M]; } }
        public int Nickels { get { return distribution[.05M]; } }
        public int Pennies { get { return distribution[.01M]; } }
        public decimal Total
        {
            get { return _total; }
            set { _total = value; RecalculateDistribution(); }
        }
        #endregion

        #region Fields
        private decimal _total;
        private Dictionary<decimal, int> distribution = new Dictionary<decimal, int>();
        #endregion

        #region Constructors
        public MoneyDistribution() : this(0.00M) { }
        public MoneyDistribution(decimal amount) { Total = amount; }
        #endregion

        #region Conversion Operator
        public static implicit operator MoneyDistribution(decimal amount)
        { return new MoneyDistribution(amount); }
        #endregion

        #region Public Methods
        public override string ToString()
        {
            Type type = typeof(MoneyDistribution);
            string[] props = new string[] { "Hundreds", "Fifties", "Twenties", "Tens", "Fives", "Ones", 
                "Quarters", "Dimes", "Nickels", "Pennies" };
            StringBuilder sb = new StringBuilder();
            sb.AppendLine(string.Format("Total: ${0}", Total));
            foreach (string prop in props)
            {
                int val = (int)type.GetProperty(prop).GetValue(this, null);
                if (val > 0)
                    sb.AppendLine(string.Format("{0}: {1}", prop, val));
            }
            return sb.ToString();
        }
        #endregion

        #region Private Methods
        private void RecalculateDistribution()
        {
            decimal val = Total;
            distribution = new Dictionary<decimal, int>();
            foreach (var item in new decimal[] { 100M, 50M, 20M, 10M, 5M, 1M, .25M, .10M, .05M, .01M })
                distribution.Add(item, CalcStep(ref val, item));
        }
        private int CalcStep(ref decimal val, decimal denomVal)
        {
            int count = (int)(val / denomVal);
            val = val - (count * denomVal);
            return count;
        }
        #endregion
    }
}

The following code is in my Main()...

MoneyDistribution cash = 12.33M;
Console.WriteLine(cash.ToString());

...which yields the following output:

Total: $12.33
Tens: 1
Ones: 2
Quarters: 1
Nickels: 1
Pennies: 3

u/[deleted] Jun 15 '12 edited Jun 15 '12

J magic time!

denom =. 0.01 0.05 0.1 0.25 1 5 10 50 100
split =. dyad : '(<.y1%x),(x|y1=.{:y)'
count =. monad : '(0{split/@,&y)\.denom'

count 12.33

0

u/[deleted] Jun 18 '12

2

u/[deleted] Jun 18 '12

It's not really that hard to explain. Which programming languages do you know? I could port it.
But yeah, J is great like that >:D

→ More replies (4)

u/SwimmingPastaDevil Jun 15 '12

denoms = [100,50,10,5,1,0.25,0.10,0.05,0.01]
moneys = [0,0,0,0,0,0,0,0,0]

change = 12.33

while change > 0.0:
    for i in range(len(denoms)):
        while denoms[i] < change:
            change -= denoms[i]
            moneys[i] += 1

    if change < 0.01:  
        break

print moneys

Output:

[0, 0, 1, 0, 2, 1, 0, 1, 3]

I think i am missing something here, for 112.33 it gives:

[1, 0, 1, 0, 2, 1, 0, 1, 2]

What am i doing wrong here?

1

u/oskar_s Jun 15 '12

change the "<" in the "while denoms[i] < change:" to a "<=". I'm 99% sure that will fix it, though there may also be some floating-point rounding errors going on here. I'd multiply the change by 100, round it to the nearest integer and list all the denominations in cents instead of dollars just to be sure.

→ More replies (1)

u/ashashwat Jun 16 '12

In Haskell, (awesome pattern matching here :) )

den = [10000, 5000, 1000, 500, 100, 25, 10, 5, 1]
coinChange n [] = []
coinChange n (d:ds) = n `div` d : coinChange (n `mod` d) ds 
main = print $ coinChange (floor (12.33*100)) den

u/_Daimon_ Jun 15 '12

Python

Using a greedy strategy with arbitrary coinage.

def coins(value, denominations):
    value = float(value)
    denominations = sorted(denominations, reverse = True)
    result = [0] * len(denominations)
    while value > 0.00001: # because floating points
        for index, deno in enumerate(denominations):
            if deno <= value:
                value -= deno
                result[index] += 1
                break
    return result

standard_us_coinage = [0.01, 0.05, 0.1, 0.25, 1.0, 5.0, 10.0, 50.0, 100.0]
print coins(12.33, standard_us_coinage)

→ More replies (2)

u/ixid Jun 15 '12 edited Jun 15 '12

D language, a flexible version that will deal with any set of notes and coins but defaults to the listed set.

module main; import std.stdio;

uint[] getCash(float money,
               float[] denominations = [100, 50, 10, 5, 1, 0.25, 0.1, 0.05, 0.01])
{   uint[] notesandcoins;
    notesandcoins.length = denominations.length;
    foreach(i, n;denominations) {
        notesandcoins[i] = cast(uint) (money / n);
        money -= notesandcoins[i] * n;
    }
    return notesandcoins;
}

void main()
{   float money = 12.333;
    money.getCash.writeln;
}

u/[deleted] Jun 15 '12 edited Jun 16 '12

public static void easy65(double n) {
	int pennies = (int)(n * 100);
	int[] d = { 10000, 5000, 1000, 500, 100, 25, 10, 5, 1 };
	int[] counts = new int[d.length];
	
	int i = 0;
	
	while(pennies > 0) {
		while(pennies >= d[i]) { 
			pennies -= d[i];
			counts[i]++;
		}
		i++;
	}
	
	double[] vals = { 100, 50, 10, 5, 1, 0.25, 0.10, 0.05, 0.01 };
	for(int j = 0; j < counts.length; j++) {
		System.out.println("$" + vals[j] + ": " + counts[j]);
	}
}

u/pbl24 Jun 15 '12

Python. Stupid floating point issues. Probably would've been easier using an iterative solution, but I did it using recursion anyways.

def run(num):
	bling = [ 100.0, 50.0, 10.0, 5.0, 1.0, .25, .10, .05, .01 ]
	ret = [x * 0 for x in range(len(bling))]
	print build(num, bling, 0, ret)

def build(num, l, idx, ret):
	
	if idx == len(l):
		return ret

	res = float(round(num, 2) / l[idx])

	if res >= 1:
		ret[idx] = int(math.floor(res))
		return build(num - (l[idx] * math.floor(res)), l, idx + 1, ret)
	else:
		return build(num, l, idx + 1, ret)

Output:

12.33  -> [0, 0, 1, 0, 2, 1, 0, 1, 3]
120.33 -> [1, 0, 2, 0, 0, 1, 0, 1, 3]
75.43  -> [0, 1, 2, 1, 0, 1, 1, 1, 3]

u/xjtian Jun 15 '12

Recursive solution that allows you to specify denominations.

Python 2.7:

def calculate_change(money, denom):
	if len(denom) == 1:
		return [money / denom[0]]
	else:
		prev_list = calculate_change(money % denom[-1], denom[:-1])
		prev_list.append(money / denom[-1])
		return prev_list
		
def get_change(money, user_denoms):
	m = int(money * 100)
	denoms = []
	for i, v in enumerate(user_denoms):
		denoms.append(int(v*100))
	return calculate_change(m, denoms)

u/bengarrr Jun 15 '12

Python 2.7

try:
	num = float(raw_input("Enter a number: "))
except ValueError:
	print "Not a number"

coinage = []
key_coins = [100.00, 50.00, 10.00, 5.00, 1.00, .25, .10, .05, .01]
i = 0

while i < 9:
	if (num / key_coins[i]) >= 1:
		coinage.append(round(num / key_coins[i]))
		if num - (coinage[i] * key_coins[i]) < 0:
			coinage[i] -= 1
		num -= (coinage[i] * key_coins[i])
	else:
		coinage.append(0)
	i += 1
	print num

print coinage

Here's my output for 12.33: [0, 0, 1.0, 0, 2.0, 1.0, 0, 1.0, 3.0]

Here's my output for 112.33: [1.0, 0, 1.0, 0, 2.0, 1.0, 0, 1.0, 2.0]

I understand not :(

2

u/SwimmingPastaDevil Jun 16 '12

Probably floating point inaccuracies. Converting num and key_coins into cents should fix that.

→ More replies (1)

u/kohjingyu Jun 16 '12

Python:

n = float(input())

denominations = [100, 50, 10, 5, 1, 0.25, 0.1, 0.05, 0.01]
result = [0] * len(denominations)

for i in range(0, len(denominations)):
    while denominations[i] < n:
        n -= denominations[i]
        result[i] += 1

print(result)

u/loonybean Jun 16 '12

Python:

def getDenoms(num):
    denoms = [10000,5000,1000,500,100,25,10,5,1]
    denomList = []
    num = int(num * 100)
    for i in range(0, len(denoms)):
        denomList.append(num/denoms[i])
        num %= denoms[i]
    return denomList

u/Xadoo Jun 16 '12

Dat Ruby

puts "How much Money? "
money = gets.to_f

denom = [10000, 5000, 1000, 500, 100, 25, 10, 5, 1]
denomAnswer = []
money = money * 100
i = 0
denom.each{|a|
denomAnswer[i] = (money / a).to_i
money = money % denom[i]
i = i + 1
}
puts denomAnswer.join(",")

u/[deleted] Jun 16 '12

Perl!

@a = (10000,5000,1000,500,100,25,10,5,1);
$b = $ARGV[0]*100;
foreach(@a){
	print("# of ". $_/100 ." = ". int($b/$_) . "\n");
    $b=$b % $_;
}

u/bradengroom Jun 16 '12

$b = <>*100;
print("# of ",$_/100," = ",int($b/$_),$/),$b%=$_ foreach(10000,5000,1000,500,100,25,10,5,1)

perl golf?

u/cdelahousse Jun 18 '12

Javascript:

function makeChange(amt, denom) {
	var len = denom.length,
			count,str = "";

	//Sort descending
	denom.sort(function (a,b) {return b-a});

	
	for (var i = 0; i < len; i++) {
		count = 0;
		while (amt >= denom[i]) {
			amt -= denom[i];
			count++;
		}
		str += count +"x" + denom[i] + "$ + ";
	}

	return str.slice(0,-3); //Remove last lil bit
}
console.log(makeChange( 12.33,[100,50,10,5,1,0.25, 0.10,0.05,0.01]));

→ More replies (1)

u/weedpatch2 Jun 18 '12

Powershell:

$moneyz = 0,0,0,0,0,0,0,0,0,0
[Decimal]$fl_input = 177.559

if (!$fl_input) {
    [Decimal]$fl_input = Read-Host "Enter a dollar amount: "
}
$fl_input = $fl_input.ToString("f2")
while ($fl_input -ne 0) {
    if ($fl_input -ge 100) {
        $moneyz[0] = [Math]::Floor($fl_input / 100)
        $fl_input %= 100
    } elseif ($fl_input -ge 50) {
        $moneyz[1] = [Math]::Floor($fl_input / 50)
        $fl_input %= 50
    } elseif ($fl_input -ge 20) {
        $moneyz[2] = [Math]::Floor($fl_input / 20)
        $fl_input %= 20
    } elseif ($fl_input -ge 10) {
        $moneyz[3] = [Math]::Floor($fl_input / 10)
        $fl_input %= 10
    } elseif ($fl_input -ge 5) {
        $moneyz[4] = [Math]::Floor($fl_input / 5)
        $fl_input %= 5
    } elseif ($fl_input -ge 1) {
        $moneyz[5] = [Math]::Floor($fl_input / 1)
        $fl_input %= 1
    } elseif ($fl_input -ge .25) {
        $moneyz[6] = [Math]::Floor($fl_input / .25)
        $fl_input %= .25
    } elseif ($fl_input -ge .1) {
        $moneyz[7] = [Math]::Floor($fl_input / .1)
        $fl_input %= .1
    } elseif ($fl_input -ge .05) {
        $moneyz[8] = [Math]::Floor($fl_input / .05)
        $fl_input %= .05
    } elseif ($fl_input -ge .01) {
        $moneyz[9] = [Math]::Floor($fl_input / .01)
        $fl_input %= .01
    }
}
$moneyz

If anyone has a better way to do this in Powershell, please let me know.

u/Okashu Jun 24 '12 edited Jun 24 '12

I managed to do this, but used polish currency and language. Linking to pastebin because it's pretty long: http://pastebin.com/kLPjM7zz

Also, I'd be happy to recieve feedback on what could I improve in, it's my second program bigger than 10 lines, and the first one completed.

u/Jamdod Jun 26 '12

Actionscript 3:

var cashAmount:Number = (12.33)*100;
var currencyAmounts:Array = new Array(10000,5000,1000,500,100,25,10,5,1);
var currencyCount:Array = new Array;
var count:int = 0;

for each (var i in currencyAmounts)
{
    while (cashAmount >= i)
    {
        count += 1;
        cashAmount -= i;
    }
    currencyCount.push(count);
    count = 0;
}

trace(currencyCount);   // result "0,0,1,0,2,1,0,1,3"

u/Arthree Jun 15 '12 edited Jun 16 '12

autohotkey:

change(money)
{
    coins := 100 * (money - floor(money))
    money //= 1
    result .= money // 100 ? money // 100 . " hundreds`n" : ""
    money := mod(money,100)
    result .= money // 50 ? money // 50 . " fifties`n" : ""
    money := mod(money,50)
    result .= money // 10 ? money // 10 . " fifties`n" : ""
    money := mod(money,10)
    result .= money // 5 ? money // 5 . " fives`n" : ""
    money := mod(money,5)
    result := money ? money . " ones`n" : ""
        
    result .= coins // 25 ? coins // 25 . " quarters`n" : ""
    coins := mod(coins,25)
    result . = coins // 10 ? coins // 10 . " dimes`n" : ""
    coins := mod(coins,10)
    result .= coins // 5 ? coins // 5 . " nickels`n" : ""
    coins := mod(coins,10)
    result .= coins ? coins . " pennies`n" : ""
    
    return result
}

u/[deleted] Jun 29 '12

→ More replies (1)

[6/15/2012] Challenge #65 [easy]

You are about to leave Redlib