Problem of the Day -- Making Change

Making Change

With all the new crypto currencies coming out I think it's time we make our own currency. Since we have such a great community and marketing team our currency really takes off and becomes the official currency of a ~~small~~ large nation. The denominations of our currency are as such:

[0.03, .08, .33, .5, 2, 10, 50, 100]

If someone comes to our store and asks for change for a $10 note. How many different ways can we offer change for the $10 note assuming with have an infinite amount of all denominations of our currency?

Permalink: http://problemotd.com/problem/making-change/

Comments:

Foppe - 10 years, 9 months ago

#! /usr/bin/pyhton

i = 0
j = 0
k = 0
l = 0
m = 0
n = 0

counter = 0

v = [0.03, 0.08, 0.33, 0.5, 2, 10]
for i in range(333):
    for j in range(120):
        for k in range(30):
            for l in range(20):
                for m in range(5):
                    for n in range(1):
                        c = i * v[0] + j * v[1] + k * v[2] + l * v[3] \
                            + m * v[4] + n * v[5]
                        if c == 10 and  c % 1 == 0:
                            counter = counter + 1
                            print(c)
                            print("%d * .03, %d * .08, %d * .33, %d * .5, \
                                %d * 2, %d * 10" % (i, j, k, l, m, n))
print(counter)

$ time python change.py
8934

real    5m43.244s
user    5m42.173s
sys 0m0.620s

reply permalink

Foppe - 10 years, 9 months ago
The range function is not inclusive so you need to add 1 to everyone of this. The final grand total is 8937

reply permalink
Max Burstein - 10 years, 9 months ago

Definitely an interesting solution. Good stuff

reply permalink
vick - 10 years, 9 months ago
I've found a small typo in line "for j in range(120):"

I think, it should be "for j in range(125 + 1):", since 10 / 0.08 = 125

Thus, grand total is 8939.

Thank you for the nice solution!

reply permalink

Foppe - 10 years, 9 months ago

The difference with the Haskell solution is due to rounding errors. When using integers I get the correct result 8954 with $10 <-> $10. Also I thought this would speed up a littlebit. #! /usr/bin/python

i = 0
j = 0
k = 0
l = 0
m = 0
n = 0

counter = 0

v = [3, 8, 33, 50, 200, 1000]
for i in range(334):
    ii = i * v[0]
    for j in range(126):
        jj = j * v[1]
        for k in range(31):
            kk = k * v[2]
            for l in range(21):
                ll = l * v[3]
                for m in range(6):
                    mm = m * v[4]
                    for n in range(2):
                        nn = n * v[5]
                        c = ii + jj + kk + ll + mm + nn
                        if c == 1000:
                            counter = counter + 1
                            # You could add a print statement here if
                            # you want to see all solutions
print(counter)

reply permalink

Foppe - 10 years, 9 months ago
Optimization: By adding lines like for k in range(31): kk = k * v[2] if ii + jj + kk > 1000: # <- Added break # <- Added in all for loops this speeds up to $ time python change.py 8954
```
real    0m9.733s
user    0m9.710s
sys 0m0.010s
```
That's from 7 minutes to 10 seconds.

reply permalink
Foppe - 10 years, 9 months ago
Formatted: for k in range(31): kk = k * v[2] if ii + jj + kk > 1000: # <- Added break # <- Added

reply permalink
Anonymous - 10 years, 9 months ago
Awesome stuff man.

reply permalink
Max! - 10 years, 9 months ago
In Wolfram Alpha : power series (1/((1-x^3)(1-x^8)(1-x^33)(1-x^50)(1-x^200)(1-x^1000)))

Then expand terms till the 1000th coefficient and I see 8954 ways. Is my combinatorial equation incorrect? I wanted to find the right solution before trying to code it up.

reply permalink
Apanatshka - 10 years, 9 months ago
That sounds about correct. My program gives back 8953, because I filtered the solution where you give back the $10 note as change.

reply permalink

Apanatshka - 10 years, 9 months ago

Haskell implementation, not as trivial as I expected:

import Data.List
import Data.Ratio

denominations = [3 % 100, 8 % 100, 33 % 100, 1 % 2, 2, 10, 50, 100]

toChange = 10 :: Ratio Int

making_change :: Ratio Int -> [Ratio Int] -> ([[(Int, Ratio Int)]], Int)
making_change todo d = (map (\l -> zip l ds) lst, ans) -- go from large to small
  where
    ds = dropWhile (>= todo) $ reverse $ sort d
    (lst, ans) = mc todo ds
    mc :: Ratio Int -> [Ratio Int] -> ([[Int]], Int)
    mc t (d:ds) = (concatMap fst tries, sum $ map snd tries)
      where
        tries :: [([[Int]], Int)]
        tries = map (\(n,t') -> let (l,m) = mc t' ds in (map (n:) l,m)) possibles -- tries to use the other denominations to make change for the amount todo
        possibles = zip [0..] $ takeWhile (>= 0) $ scanl (-) t $ repeat d -- get a list of possible left over numbers
    mc t [] = if t == 0 then ([[]],1) else ([],0)

answer = making_change toChange denominations

main = print $ snd answer

It prints 8953. If you write main = print $ fst answer you get the different ways in stead of the count.

reply permalink

btgrant - 10 years, 8 months ago

Using integers like the Haskel submission, here's a solution in Scala:

def countChange(money: Int, coins: List[Int]): Int = {
  if (coins.isEmpty || money < 0)
    0
  else if (money == 0)
    1
  else {
    countChange(money - coins.head, coins) + countChange(money, coins.tail)
  }
}
val denominations = List(3, 8, 33, 50, 200, 1000)
val changeFor = 1000
println(countChange(changeFor, denominations))

reply permalink

Problem of the Day A new programming or logic puzzle every Mon-Fri

Making Change

Comments:

Problem of the Day
A new programming or logic puzzle every Mon-Fri