Programming Praxis

7 Responses to “Coin Change, Part 1”

1. Programming Praxis – Coin Change, Part 1 | Bonsai Code said

   May 17, 2013 at 3:06 PM

   […] today’s Programming Praxis exercise, our goal is to list all of the ways in which a target amount can be […]
2. Remco Niemeijer said

   May 17, 2013 at 3:06 PM

   My Haskell solution (see http://bonsaicode.wordpress.com/2013/05/17/programming-praxis-coin-change-part-1/ for a version with comments):

   import Data.List
   
   coins :: (Num a, Ord a) => [a] -> a -> [[a]]
   coins _  0 = [[]]
   coins xs n = [c:r | (c:cs) <- tails xs, c <= n, r <- coins (c:cs) (n-c)]
   
   count :: (Num a, Ord a) => [a] -> a -> Int
   count xs = length . coins xs
   
3. Alan S. said

   May 21, 2013 at 4:23 PM

   Here is a Ruby program with both functions

   
   

   	$ ./coin-change1.rb
   	For total = 40
   	There are 31 sets of coins
   	Set $.25 $.10 $.05 $.01
   	1: 0 0 0 40
   	2: 0 0 1 35
   	3: 0 0 2 30
   	4: 0 0 3 25
   	5: 0 0 4 20
   	6: 0 0 5 15
   	7: 0 0 6 10
   	8: 0 0 7 5
   	9: 0 0 8 0
   	10: 0 1 0 30
   	11: 0 1 1 25
   	12: 0 1 2 20
   	13: 0 1 3 15
   	14: 0 1 4 10
   	15: 0 1 5 5
   	16: 0 1 6 0
   	17: 0 2 0 20
   	18: 0 2 1 15
   	19: 0 2 2 10
   	20: 0 2 3 5
   	21: 0 2 4 0
   	22: 0 3 0 10
   	23: 0 3 1 5
   	24: 0 3 2 0
   	25: 0 4 0 0
   	26: 1 0 0 15
   	27: 1 0 1 10
   	28: 1 0 2 5
   	29: 1 0 3 0
   	30: 1 1 0 5
   	31: 1 1 1 0

   view raw
   
   coin-change1 output
   
   hosted with ❤ by GitHub

   
   

   	#!/usr/bin/env ruby
   	# coin-change1.rb
   	#
   	# count sets of coins (pennies, nickles, dimes, quarters) that
   	# add to a specific total
   	#
   	# Count the different sets of the polynomial:
   	# total = P + N*5 + D*10 * Q*25
   	#
   	# A "coin set" is a 4-tuple of [P,N,D,Q]
   	#
   	$coin_values = [ 1, 5, 10, 25 ]
   	# given a total, find the maximum number of coins for each
   	# denomination
   	def compute_max_coins(total)
   	$max_coins = $coin_values.map {|value| Integer(total / value)}
   	$max_pennies = $max_coins[0]
   	$max_nickles = $max_coins[1]
   	$max_dimes = $max_coins[2]
   	$max_quarters = $max_coins[3]
   	end
   	# get all the coin sets for a given total
   	def get_coin_sets(total)
   	coin_sets = []
   	(0..$max_quarters).each { |q|
   	break if total < q*25
   	qtotal = total – q*25
   	(0..$max_dimes).each { |d|
   	break if qtotal < d*10
   	dtotal = qtotal – d*10
   	(0..$max_nickles).each { |n|
   	break if dtotal < n*5
   	p = dtotal – n*5
   	coin_sets += [[q,d,n,p]]
   	}
   	}
   	}
   	coin_sets
   	end
   	if ARGV.size > 0
   	total = ARGV.shift.to_i
   	else
   	total = 40
   	end
   	compute_max_coins(total)
   	coin_sets = get_coin_sets(total)
   	puts "For total = #{total}"
   	puts "There are #{coin_sets.size} sets of coins"
   	puts ''
   	set = 1
   	printf "Set $.25 $.10 $.05 $.01\n"
   	coin_sets.each do |q,d,n,p|
   	printf "%3d: %4d %4d %4d %4d\n", set, q, d, n, p
   	set += 1
   	end
   	exit

   view raw
   
   coin-change1.rb
   
   hosted with ❤ by GitHub

   #!/usr/bin/env ruby
   # coin-change1.rb
   #
   # count sets of coins (pennies, nickles, dimes, quarters) that
   # add to a specific total
   #
   # Count the different sets of the polynomial: 
   #   total = P + N*5 + D*10 * Q*25
   # 
   # A "coin set" is a 4-tuple of [P,N,D,Q]
   #
    
   $coin_values = [ 1, 5, 10, 25 ]
    
   # given a total, find the maximum number of coins for each
   # denomination
    
   def compute_max_coins(total)
     $max_coins = $coin_values.map {|value| Integer(total / value)}
     $max_pennies  = $max_coins[0]
     $max_nickles  = $max_coins[1]
     $max_dimes    = $max_coins[2]
     $max_quarters = $max_coins[3]
   end
    
   # get all the coin sets for a given total
    
   def get_coin_sets(total)
     coin_sets = []
     (0..$max_quarters).each { |q|
       break if total < q*25
       qtotal = total - q*25
       (0..$max_dimes).each { |d|
         break if qtotal < d*10
         dtotal = qtotal - d*10
         (0..$max_nickles).each { |n|
           break if dtotal < n*5
           p = dtotal - n*5
           coin_sets += [[q,d,n,p]]
         }
       }
     }
     coin_sets
   end
    
   if ARGV.size > 0
     total = ARGV.shift.to_i
   else
     total = 40
   end
    
   compute_max_coins(total)
   coin_sets = get_coin_sets(total)
    
   puts "For total = #{total}"
   puts "There are #{coin_sets.size} sets of coins"
   puts ''
   set = 1
   printf "Set  $.25  $.10  $.05  $.01\n"
   coin_sets.each do |q,d,n,p| 
     printf "%3d: %4d  %4d  %4d  %4d\n", set, q, d, n, p
     set += 1
   end
    
   exit
   
4. aks said

   May 21, 2013 at 4:24 PM

   Here is the output:

   $ ./coin-change1.rb 
   For total = 40
   There are 31 sets of coins
    
   Set  $.25  $.10  $.05  $.01
     1:    0     0     0    40
     2:    0     0     1    35
     3:    0     0     2    30
     4:    0     0     3    25
     5:    0     0     4    20
     6:    0     0     5    15
     7:    0     0     6    10
     8:    0     0     7     5
     9:    0     0     8     0
    10:    0     1     0    30
    11:    0     1     1    25
    12:    0     1     2    20
    13:    0     1     3    15
    14:    0     1     4    10
    15:    0     1     5     5
    16:    0     1     6     0
    17:    0     2     0    20
    18:    0     2     1    15
    19:    0     2     2    10
    20:    0     2     3     5
    21:    0     2     4     0
    22:    0     3     0    10
    23:    0     3     1     5
    24:    0     3     2     0
    25:    0     4     0     0
    26:    1     0     0    15
    27:    1     0     1    10
    28:    1     0     2     5
    29:    1     0     3     0
    30:    1     1     0     5
    31:    1     1     1     0
   
5. Programming Praxis – Coin Change, Part 1, C# Solutions | Software Salad said

   June 10, 2013 at 11:37 PM

   […] This post presents C# solutions to a coin change problem as described in https://programmingpraxis.com/2013/05/17/coin-change-part-1. […]
6. taoufik belaidi said

   October 15, 2019 at 10:42 AM

   I have done this exercise using a simple method: I divide the total (T) by the first coin (C1). I take the integer part of this division (n1=T//c1). n1 represents the maximum number of possiblities of having c1 in any combinaison. After that, I do the same process for finding the total minus 0, 1,…, n1*c1 now using just the new set (C2, C3, C4).

   Here is the program in Python, and it works well: the result is outputed very fast.

   c1=25
   c2=10
   c3=29
   c4=3

   T=40

   C=[]
   for i in range(0, (T//c1)+1):
   if T-(ic1)==0:
   C.append([i,0,0,0])
   continue
   for j in range(0, ((T-ic1)//c2)+1):
   if T-ic1-jc2==0:
   C.append([i,j,0,0])
   continue
   for w in range(0, ((T-ic1-jc2)//c3)+1):
   if (T-ic1-jc2-wc3)%c4 == 0:
   C.append([i,j,w,(T-ic1-jc2-wc3)//c4])

   for i in C:
   print(i)
   print(len(C))
7. Modified Coin Change | Programming Praxis said

   November 19, 2019 at 10:00 AM

   […] solved the standard coin change problem in two previous exercises. The particular problem given here is to find the minumum number of coins that can be […]