Topic: -={ Challenge }=- Give Change

[David Bethel]

Maybe for us simple minded folks

Code: [Select]

(defun givechange (a dl / d q c)

(defun remove (expr lst);;;TonyT or VNesterowski
  (apply 'append (subst nil (list expr) (mapcar 'list lst))))

  (while (and (> a 0)
              (> (length dl) 0))
         (setq d (apply 'max dl)
               q (fix (/ a d))
               a (- a (* d q))
               dl (remove d dl))
          (if (> q 0)
              (setq c (cons (cons d q) c))))
  (reverse c))


[Lee Mac]

A simple approach David, but the greedy algorithm will have trouble with examples such as (givechange 40 '(25 20 10 5 1)) 

[ElpanovEvgeniy]

Another optimisation:

Code: [Select]

...

my answer:

Code: [Select]

(defun change_v5 (n l / i)
  (cond ((or (not l) (< n 0)) '(32767 nil))
        ((< n (car l)) (change_v5 n (cdr l)))
        ((zerop (rem n (car l))) (list (setq i (/ n (car l))) (cons (car l) i)))
        ((f1 (f2 n (cdr l)) (change_v5 (- n (car l)) l) (car l)))
  )
)
(defun f1 (a b c)
  (cond ((not a) (f3 n l))
        ((< (car a) (1+ (car b))) a)
        ((= (caadr b) c) (cons (1+ (car b)) (cons (cons c (1+ (cdadr b))) (cddr b))))
        ((cons (1+ (car b)) (cons (cons c 1) (cdr b))))
  )
)
(defun f2 (n l / i)
  (setq i 0
        l (mapcar '(lambda (a / b c)
                     (setq b n
                           n (rem n a)
                           c (/ b a)
                           i (+ i c)
                     )
                     (cons a c)
                   )
                  (vl-sort l '>)
          )
  )
  (if (= n 0)
    (cons i l)
  )
)
(defun f3 (n l / i)
  (cond ((or (not l) (< n 0)) '(32767 nil))
        ((< n (car l)) (change_v5 n (cdr l)))
        ((zerop (rem n (car l))) (list (setq i (/ n (car l))) (cons (car l) i)))
        ((f1 (f3 n (cdr l)) (change_v5 (- n (car l)) l) (car l)))
  )
)

[Lee Mac]

Give me a minute, I think my head just exploded 

[David Bethel]

A simple approach David, but the greedy algorithm will have trouble with examples such as (givechange 40 '(25 20 10 5 1)) 

We Yanks don't have a 20p.  Maybe the Founding Fathers were mathematicians as well and we didn't know it!  -David

[Lee Mac]

A simple approach David, but the greedy algorithm will have trouble with examples such as (givechange 40 '(25 20 10 5 1)) 

We Yanks don't have a 20p.  Maybe the Founding Fathers were mathematicians as well and we didn't know it!  -David

We Brits don't have 25p, I was just looking to the general case for an arbitrary set of denominations for which dynamic programming must be used   

Coincidentally, the greedy algorithm will produce the optimal result for the US currency system. 

[Jürg Menzi]

A little bit offtopic...

Hi Lee
Great solution, thanks!

Had this problem:
http://www.theswamp.org/index.php?topic=42146.0
So I used your solution a little bit modified:

Code - Auto/Visual Lisp: [Select]

1. ...
2.  (while (and (setq e (nth c b)) (< c n))
3.   (setq h (assoc++ e h) c (+ c e))
4.  )
5.  (cons (- n c) h)
6. )

The problem was, that my application requires the ability to get a remainder.

Thanks again and have a good day
Cheers

[Lee Mac]

Thank you Jürg! I'm pleased that my solution was useful in applications other than this challenge