How to resolve the algorithm Count the coins step by step in the EchoLisp programming language

Published on 12 May 2024 09:40 PM
#Echolisp

How to resolve the algorithm Count the coins step by step in the EchoLisp programming language

Table of Contents

Problem Statement

There are four types of common coins in   US   currency:

There are six ways to make change for 15 cents:

How many ways are there to make change for a dollar using these common coins?     (1 dollar = 100 cents).

Less common are dollar coins (100 cents);   and very rare are half dollars (50 cents).   With the addition of these two coins, how many ways are there to make change for $1000? (Note:   the answer is larger than   232).

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Count the coins step by step in the EchoLisp programming language

Source code in the echolisp programming language

(lib 'compile) ;; for (compile)
(lib 'bigint)  ;; integer results > 32 bits
(lib 'hash)    ;; hash table

;; h-table
(define Hcoins (make-hash))

;; the function to memoize
(define (sumways cents coins)
	(+ (ways cents (cdr coins)) (ways (- cents (car coins)) coins)))
	
;; accelerator : ways (cents, coins) = ways ((cents  - cents % 5) , coins)
(define (ways cents coins)
  (cond ((null? coins) 0)
        ((negative? cents) 0)
        ((zero? cents) 1)
        ((eq? coins c-1) 1) ;; if coins = (1) --> 1
        (else (hash-ref! Hcoins (list (- cents (modulo cents 5)) coins) sumways))))

(compile 'ways) ;; speed-up things


(define change '(25 10 5 1))
(define c-1 (list-tail change -1)) ;; pointer to (1)
(ways 100 change)
    → 242

(define change '(100 50 25 10 5 1))
(define c-1 (list-tail change -1))
(for ((i (in-range 0 200001 20000))) 
    (writeln i (time (ways i change)) (hash-count Hcoins)))


;; iterate cents = 20000, 40000, ..
;; cents ((time (msec) number-of-ways) number-of-entries-in-h-table

20000      (350 4371565890901)         9398    
40000      (245 138204514221801)       18798    
60000      (230 1045248220992701)      28198    
80000      (255 4395748062203601)      37598    
100000     (234 13398445413854501)     46998    
120000     (230 33312577651945401)     56398    
140000     (292 71959878152476301)     65798    
160000     (736 140236576291447201)     75198    
180000     (237 252625397444858101)     84598    
200000     (240 427707562988709001)     93998    

;; One can see that the time is linear, and the h-table size reasonably small

change 
    → (100 50 25 10 5 1)
(ways 100000 change)
    → 13398445413854501

You may also check:How to resolve the algorithm Sorting algorithms/Pancake sort step by step in the C++ programming language
You may also check:How to resolve the algorithm Knight's tour step by step in the Fōrmulæ programming language
You may also check:How to resolve the algorithm Solve a Hidato puzzle step by step in the D programming language
You may also check:How to resolve the algorithm String append step by step in the Sidef programming language
You may also check:How to resolve the algorithm Sum of a series step by step in the EchoLisp programming language