Representing an amount of money with specific bills

Question

I want to write a function in Racket which takes an amount of money and a list of specific bill-values, and then returns a list with the amount of bills used of every type to make the given amount in total. For example (calc 415 (list 100 10 5 2 1)) should return '(4 1 1 0 0).

I tried it this way but this doesn't work :/ I think I haven't fully understood what you can / can't do with set! in Racket, to be honest.

(define (calc n xs)
  (cond ((null? xs) (list))
        ((not (pair? xs)) 
          (define y n) 
          (begin (set! n (- n (* xs (floor (/ n xs)))))
                 (list (floor (/ y xs))) ))
        (else (append (calc n (car xs))
                      (calc n (cdr xs))))))

Gangway

check out this question about making a change for a given sum, which is exactly the same problem. (it's not a duplicate). see if my answer there helps. – Appellate

did you mean "set ", or did you mean "set!"? – Appellate

set! mb I miswrote – Gangway

@WillNess sry I still don't really get it :/ I feel like my problem is that I can't reduce my n while still holding on, on how many bills I used to reduce it. I mean maybe I am missing the point completely and this is far away fromt he actual solution... – Gangway

if you need to take a bite off your cake, and still hold on to it, maybe you need two hands, to hold each thing in each hand. or variable. that is, two variables. :) Or more, as much as needed. you have target sum, current sum, rest-of-sum-to-make-up, list of available bills.... some of these may be redundant, but better write right, at first, optimize only later. "premature optimization is mother of all evil", as the saying goes.... that is, don't try to be succinct right away - you can always optimize later! – Appellate

Answer 1

This problem calls for some straightforward recursive non-deterministic programming.

• We start with a given amount, and a given list of bill denominations, with unlimited amounts of each bill, apparently (otherwise, it'd be a different problem).
• At each point in time, we can either use the biggest bill, or not.
• If we use it, the total sum lessens by the bill's value.
• If the total is 0, we've got our solution!
• If the total is negative, it is invalid, so we should abandon this path.

The code here will follow another answer of mine, which finds out the total amount of solutions (which are more than one, for your example as well). We will just have to mind the solutions themselves as well, whereas the code mentioned above only counted them.

We can code this one as a recursive-backtracking procedure, calling a callback with each successfully found solution from inside the deepest level of recursion (tantamount to the most deeply nested loop in the nested loops structure created with recursion, which is the essence of recursive backtracking):

(define (change sum bills callback)
  (let loop ([sum sum] [sol '()] [bills bills])    ; "sol" for "solution"
    (cond
       ((zero? sum)   (callback sol))              ; process a solution found
       ((< sum 0)      #f)
       ((null? bills)   #f)
       (else
        (apply
          (lambda (b . bs)                         ; the "loop":
              ;; 1.                                ; either use the first
            (loop (- sum b) (cons b sol) bills)    ;   denomination,
              ;; 2.                                ;   or,
            (loop    sum            sol     bs))   ;   after backtracking, don't!
          bills)))))

It is to be called through e.g. one of

;; construct `the-callback` for `solve` and call 
;;       (solve ...params the-callback)
;; where `the-callback` is an exit continuation

(define (first-solution solve . params)
  (call/cc (lambda (return)
      (apply solve (append params         ; use `return` as
                     (list return))))))   ; the callback

(define (n-solutions n solve . params)    ; n assumed an integer
  (let ([res '()])                        ; n <= 0 gets ALL solutions
    (call/cc (lambda (break)
        (apply solve (append params
                       (list (lambda (sol)
                               (set! res (cons sol res))
                               (set! n (- n 1))
                               (cond ((zero? n) (break)))))))))
    (reverse res)))

Testing,

> (first-solution change 406 (list 100 10 5 2))

'(2 2 2 100 100 100 100)

> (n-solutions 7 change 415 (list 100 10 5 2 1))

'((5 10 100 100 100 100)
  (1 2 2 10 100 100 100 100)
  (1 1 1 2 10 100 100 100 100)
  (1 1 1 1 1 10 100 100 100 100)
  (5 5 5 100 100 100 100)
  (1 2 2 5 5 100 100 100 100)
  (1 1 1 2 5 5 100 100 100 100))

---

Regarding how this code is structured, cf. How to generate all the permutations of elements in a list one at a time in Lisp? It creates nested loops with the solution being accessible in the innermost loop's body.

Regarding how to code up a non-deterministic algorithm (making all possible choices at once) in a proper functional way, see How to do a powerset in DrRacket? and How to find partitions of a list in Scheme.

Appellate

Thx a lot for the help! I will definitely have a closer look on your solution in the future however I just started with racket and not even know how loops work so it's a little bit too confusing :/. Even tho it gave me some ideas on how I can tackl the problem and I have a solution now ^^ – Gangway

"loop" is just a name. it could be "g" just as well. look up "named let", here on SO as well, but it is just equivalent to the internal define. – Appellate

Answer 2

Your procedure does too much and you use mutation which is uneccesary. If you split the problem up.

(define (calc-one-bill n bill)
  ...)

;; test 
(calc-one-bill 450 100) ; ==> 4
(calc-one-bill 450 50)  ; ==> 9

Then you can make:

(define (calc-new-n n bill amount)
  ...)

(calc-new-n 450 100 4) ; ==> 50
(calc-new-n 450 50 9)  ; ==> 0

Then you can reduce your original implememntation like this:

(define (calc n bills)
  (if (null? bills)
      (if (zero? n)
          '()
          (error "The unit needs to be the last element in the bills list"))
      (let* ((bill (car bills))
             (amount (calc-one-bill n bill)))
        (cons amount
              (calc (calc-new-n n bill amount)
                    (cdr bills))))))

This will always choose the solution with fewest bills, just as your version seems to do. Both versions requires that the last element in the bill passed is the unit 1. For a more complex method, that works with (calc 406 (list 100 10 5 2)) and that potentially can find all combinations of solutions, see Will's answer.

Mannerheim

you seem to refer to the code in the question, but they have posted an answer as well, which I think does exactly what you suggest here. and it can't solve the (calc 406 (list 100 10 5 2)) case. – Appellate

@WillNess Your solution is a far more complex than required by the example provided. For a beginner it would be far more difficult to grasp and judging from OPs effort I's say they are not ready for continuations. Your solution would be indistinguishable with magic :-p – Mannerheim

continuations aren't essential here, as discussed. complex or simple, it must be correct first. better to fail than return a wrong answer... – Appellate

@WillNess I agree. I actually made a change that makes it fail in your case on the last edit. – Mannerheim

Answer 3

I solved it this way now :)

(define (calc n xs)
  (define (calcAssist n xs usedBills)
    (cond ((null? xs) usedBills)
          ((pair? xs) 
            (calcAssist (- n (* (car xs) (floor (/ n (car xs))))) 
                        (cdr xs) 
                        (append usedBills 
                                (list (floor (/ n (car xs)))))))
          (else 
            (if ((= (- n (* xs (floor (/ n xs)))) 0)) 
               (append usedBills (list (floor (/ n xs))))
               (display "No solution")))))

  (calcAssist n xs (list)))

Testing:

> (calc 415 (list 100 10 5 2 1))
'(4 1 1 0 0)

Gangway

your solution is "greedy". it means it won't always find a solution even if there are many. in theory, that is. also, the cond's 3rd clause will never fire. – Appellate

for example, (calc 406 (list 100 10 5 2)). it should fail with your code ( but it incorrectly reports '(4 0 1 0) as the solution). the correct one is '(4 0 0 3) of course; as well as '(3 10 0 3), '(3 0 20 3), etc.. – Appellate

Answer 4

I think this is the first program I wrote when learning FORTRAN! Here is a version which makes no bones about using everything Racket has to offer (or, at least, everything I know about). As such it's probably a terrible homework solution, and it's certainly prettier than the FORTRAN I wrote in 1984.

Note that this version doesn't search, so it will get remainders even when it does not need to. It never gets a remainder if the lowest denomination is 1, of course.

(define/contract (denominations-of amount denominations)
  ;; split amount into units of denominations, returning the split
  ;; in descending order of denomination, and any remainder (if there is
  ;; no 1 denomination there will generally be a remainder).
  (-> natural-number/c (listof (integer-in 1 #f))
      (values (listof natural-number/c) natural-number/c))
  (let handle-one-denomination ([current amount]
                                [remaining-denominations (sort denominations >)]
                                [so-far '()])
    ;; handle a single denomination: current is the balance,
    ;; remaining-denominations is the denominations left (descending order)
    ;; so-far is the list of amounts of each denomination we've accumulated
    ;; so far, which is in ascending order of denomination
    (if (null? remaining-denominations)
        ;; we are done: return the reversed accumulator and anything left over
        (values (reverse so-far) current)
        (match-let ([(cons first-denomination rest-of-the-denominations)
                     remaining-denominations])
          (if (> first-denomination current)
              ;; if the first denomination is more than the balance, just
              ;; accumulate a 0 for it and loop on the rest
              (handle-one-denomination current rest-of-the-denominations
                                       (cons 0 so-far))
              ;; otherwise work out how much of it we need and how much is left
              (let-values ([(q r)
                            (quotient/remainder current first-denomination)])
                ;; and loop on the remainder accumulating the number of bills
                ;; we needed
                (handle-one-denomination r rest-of-the-denominations
                                         (cons q so-far))))))))

Cogan

1. when I copy it into DrRacket window under #lang racket and load it, I get some kind of error (my Racket is a bit out of date, maybe that's why?...). 2. this seems to be doing what the OP's answer is doing, too... I don't think it can solve the 406 '(100 10 5 2) case. – Appellate

Are you using #lang racket? I don't think it will work in racket/base for instance, which doesn't have define/contract. I'm using 6.12, which I think is current, but I think this should all work in anything recent. No, it does not search so it gets a remainder of 1 in your case. I suspect the answers people look for don't search, as you never need to search if the lowest denomination is 1, and it always is. But a version that does search is obviously cooler. I just wrote it because it brought back memories. – Cogan

#lang racket, but my minor version number is way lower than 12. yep, integer-in expects two exact-integer?s for my version. outdated! --- have you coded it in FORTRAN in the same way as here? it's incorrect, you know. you must be able to backtrack... So that's what you meant by "getting a remainder", now I understand. :) – Appellate

You may be able to use exact-positive-integer? instead of (integer-in 1 #f). It's only incorrect if the smallest denomination is not 1 (which in real currencies it usually is). And if the smallest denomination is not 1 there is always a case where there's no solution even with search (namely 1!). I'm not trying to argue that backtracking is not a good thing, just that I very much doubt the original homework (I presume) question required it. I have no memory of what my FORTRAN one looked like, but it probably did not search: just getting anything to work in a F77 subset was hard enough. – Cogan

I just used 10000000 instead of #f. :) --- detecting no solutions are possible is in itself a valid answer, too. backtracking is only one strategy for search; you could maintain a stack, and put into it e.g. for the 406 / (100 10 5 2), not just 100:(4) as you do now, but 100:(4 3 2 1 0) instead, then pop the first one and continue. this would perform a DFS search in the solution space. and it would always find a solution, if there is one. – Appellate

It's OK, I do know how to write search algorithms: I just didn't bother in this case! – Cogan

well, I wasn't implying anything, just thinking out loud. – Appellate

That's fine, sorry I wasn't trying to be antagonistic. A solution that searches like yourse is clearly better, I was just lazy (also I always try and do these with continuations & often get confused doing so, & when I don't I worry about whether using the nuclear weapon of call/cc to hammer in a nail is really right) – Cogan

the advantage of writing a code for an SO answer is that it is not a real code. :) but seriously, when it is actually used as just a plain exit continuation, I'd expect a compiler to compile it down to a simple jump. what's the point of having a compiler, otherwise. :) --- what I liked about the code in my answer, as I was writing it, is how simple it turned out to be. Do this, then do that. Simple. "Imperative" thinking has its place after all, it seems. – Appellate