Author Topic: (Challenge) Counting Change  (Read 213 times)

0 Members and 1 Guest are viewing this topic.

John Kaul (Se7en)

  • Administrator
  • Needs a day job
  • Posts: 8863
(Challenge) Counting Change
« on: December 07, 2017, 10:56:30 am »
I found this challenge in an old file of mine and I thought I'd share it however this one is obviously from a book (this was homework) so I will make two posts in this challenge; one being the challenge itself with part of the explanation and the other being the final part of the explanation/answer.

*** SICP Homework - PART ONE ***
How many different ways can we make change of $1.00, given half-dollars, quarters, dimes, nickels, and pennies? More generally, can we write a procedure to compute the number of ways to change any given amount of money?

This problem has a simple solution as a recursive procedure. Suppose we think of the types of coins available as arranged in some order. Then the following relation holds:

The number of ways to change amount a using n kinds of coins equals

    * the number of ways to change amount a using all but the first kind of coin, plus
    * the number of ways to change amount a - d using all n kinds of coins, where d is the denomination of the first kind of coin.

To see why this is true, observe that the ways to make change can be divided into two groups: those that do not use any of the first kind of coin, and those that do. Therefore, the total number of ways to make change for some amount is equal to the number of ways to make change for the amount without using any of the first kind of coin, plus the number of ways to make change assuming that we do use the first kind of coin. But the latter number is equal to the number of ways to make change for the amount that remains after using a coin of the first kind.
*** SICP Homework - PART ONE ***
“Common sense is not so common.” ~Voltaire

--> Donate to TheSwamp.org <--

John Kaul (Se7en)

  • Administrator
  • Needs a day job
  • Posts: 8863
Re: (Challenge) Counting Change
« Reply #1 on: December 07, 2017, 11:13:33 am »
Spoiler Alert!

*** SICP Homework - PART TWO ***
Thus, we can recursively reduce the problem of changing a given amount to the problem of changing smaller amounts using fewer kinds of coins. Consider this reduction rule carefully, and convince yourself that we can use it to describe an algorithm if we specify the following degenerate cases:

    * If a is exactly 0, we should count that as 1 way to make change.
    * If a is less than 0, we should count that as 0 ways to make change.
    * If n is 0, we should count that as 0 ways to make change.

we can easily translate this description into a recursive procedure:

Code - Auto/Visual Lisp: [Select]
  1. (defun count-change (amount)
  2.  (cc amount 5) )
  3. (defun cc (amount kinds-of-coins)
  4.  (setq else T)
  5.  (cond ((= amount 0) 1)
  6.        ((or (< amount 0) (= kinds-of-coins 0)) 0)
  7.        (else (+ (cc amount
  8.                     (- kinds-of-coins 1))
  9.                 (cc (- amount
  10.                        (first-denomination kinds-of-coins))
  11.                     kinds-of-coins)))))
  12. (defun first-denomination (kinds-of-coins)
  13.  (cond ((= kinds-of-coins 1) 1)
  14.        ((= kinds-of-coins 2) 5)
  15.        ((= kinds-of-coins 3) 10)
  16.        ((= kinds-of-coins 4) 25)
  17.        ((= kinds-of-coins 5) 50)) )

The first-denomination procedure takes as input the number of kinds of coins available and returns the denomination of the first kind. Here we are thinking of the coins as arranged in order from largest to smallest, but any order would do as well. We can now answer our original question about changing a dollar:

Code: [Select]
(count-change 100)
292

Count-change generates a tree-recursive process with redundancies similar to those in our first implementation of fib. (It will take quite a while for that 292 to be computed.) On the other hand, it is not obvious how to design a better algorithm for computing the result, and we leave this problem as a challenge. The observation that a tree-recursive process may be highly inefficient but often easy to specify and understand has led people to propose that one could get the best of both worlds by designing a ``smart compiler'' that could transform tree-recursive procedures into more efficient procedures that compute the same result.
*** SICP Homework - PART TWO ***
“Common sense is not so common.” ~Voltaire

--> Donate to TheSwamp.org <--

Lee Mac

  • Seagull
  • Posts: 11854
  • AutoCAD 2015 Windows 7 London, England
Re: (Challenge) Counting Change
« Reply #2 on: December 08, 2017, 12:57:43 pm »
An interesting challenge - in a similar vein to this thread.

John Kaul (Se7en)

  • Administrator
  • Needs a day job
  • Posts: 8863
Re: (Challenge) Counting Change
« Reply #3 on: December 08, 2017, 03:56:36 pm »
Oh? My apologies.
“Common sense is not so common.” ~Voltaire

--> Donate to TheSwamp.org <--

kdub

  • SuperMod
  • Swamp Rat
  • Posts: 994
  • class keyThumper<T>:ILazy<T>
Re: (Challenge) Counting Change
« Reply #4 on: December 09, 2017, 02:37:31 am »

I cheat ... just tap and go.
called Kerry in my other life

Sometimes the question is more important than the answer.

kdub

  • SuperMod
  • Swamp Rat
  • Posts: 994
  • class keyThumper<T>:ILazy<T>
Re: (Challenge) Counting Change
« Reply #5 on: December 09, 2017, 02:40:41 am »
Oh? My apologies.

We discussed this years ago John .... There will be nothing new in Lisp, just different shoulders to stand on occasionally depending on collation.
called Kerry in my other life

Sometimes the question is more important than the answer.

John Kaul (Se7en)

  • Administrator
  • Needs a day job
  • Posts: 8863
Re: (Challenge) Counting Change
« Reply #6 on: December 09, 2017, 08:34:45 pm »
These challenges used to be great teaching opportunities.
“Common sense is not so common.” ~Voltaire

--> Donate to TheSwamp.org <--

kdub

  • SuperMod
  • Swamp Rat
  • Posts: 994
  • class keyThumper<T>:ILazy<T>
Re: (Challenge) Counting Change
« Reply #7 on: December 10, 2017, 02:37:52 am »
yep.

called Kerry in my other life

Sometimes the question is more important than the answer.

Grrr1337

  • Bull Frog
  • Posts: 453
Re: (Challenge) Counting Change
« Reply #8 on: December 10, 2017, 09:30:36 am »
An interesting challenge - in a similar vein to this thread.

Wow, thats creative!

Say inside the pay desk there are coins: (<Nominal> . <Count>)
Code: [Select]
((100 . 17)(50 . 23) (20 . 0) (10 . 45) (5 . 33) (2 . 6))which means, 100 = £1 and you ran out of 20p-s.

You still could find out the change of that:
Code: [Select]
(_givechange 67 '(50 10 5 2 1))then say decrement the first list, to update whats inside of the pay desk.

So now there can be ACAD for cashiers!  :laugh: