From: teespy <teespy@...>
Date: 2001-07-31T14:14:41+09:00
Subject: [ruby-talk:18863] Re: Who can count change??


--BOKacYhQ+x31HxR3
Content-Type: text/plain; charset=iso-8859-1
Content-Disposition: inline
Content-Transfer-Encoding: 8bit

Sorry for the late response, but I was playing with this a bit and I finished my ultra-slow solution. Anyways, i learned some things from it, so here it is if someone is still intrested.
I�m pretty sure there are better algorithms to do it, I�d like to take a look if you want  to show them.

And sorry for the 114 lines of code floding your mail acc.

Comments welcome, 
byez--

--teespy


--BOKacYhQ+x31HxR3
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="change4.rb"

#!/usr/local/bin/ruby

class Coin
	def initialize(ratio, acmod)
		@ratio = ratio
		@ncoins = 0
		if acmod == "increase" then @acmod = 1 else @acmod = -1 end
	end

	def setn(ncoins)
		@ncoins = ncoins
	end

	def zero
		@ncoins = 0
	end

	def access
		@ncoins += @acmod
		(@ratio * @acmod)
	end

	def value
		(@ncoins * @ratio)
	end

	def ratio
		@ratio
	end

	def num
		@ncoins
	end
end

class Change4
	def initialize(total, cash)
		@sum = 0
		@total = total         
		@cash = cash   
		@curindex = 0
		@ncoins = @cash.length
		@coins = []
	end

	def makecoins
		0.upto(@ncoins-1) do |n| 
				if (n == 0) then 
					@coins[n] = Coin.new(@cash[n], "decrease")
				       else
				        @coins[n] = Coin.new(@cash[n], "increase")
				       end
				end
	end

	def matchshow
		0.upto(@ncoins-1) {|ind| 
				 print "#{@coins[ind].num} coins of #{@coins[ind].ratio}"
				 if ind == (@ncoins-1) then print "\n" else print ", " end
				}
	end

	def makechange
		makecoins
		@curindex = 0
		@coins[0].setn(@total/@coins[0].ratio)
		@matches = 0
		@sum = @coins[0].value

		puts "#{@sum} at begining, #{@coins[0].num} coins"

		until (@coins[0].num < 0) do
			if (@sum < @total) then
				if @curindex < (@ncoins - 1) then
					@curindex += 1
					next
				else
					@sum += @coins[@curindex].access
					next 
				end
			else       # when @sum > @total	
				if (@sum == @total) then
					@matches += 1
					matchshow
				end
				if (@curindex > 0) then
					@del = 0
					@curindex.upto(@ncoins-1) {|n| @del += @coins[n].value; @coins[n].zero}
					@sum = @sum + @coins[@curindex - 1].access - @del
					@curindex -= 1
					next
				else
					@coins[@curindex].access
					@sum = @coins[0].value
					next
				end
			end
		end
		puts "Total Possible Combinations: #{@matches}"
	end
end

(puts "usage: ./change4 <total> <coin1> <coin2> ..." ;exit) if ARGV.length < 2

coins = []
@i = 0
ARGV.each { |arg| 
		     if (@i == 0) then @total = arg.to_i else coins.push(arg.to_i) end
		     @i += 1
          }

coins.sort!
change = Change4.new(@total, coins)
change.makechange


--BOKacYhQ+x31HxR3--