[ruby-talk:18912] Re: Who can count change??

On Tue, Jul 31, 2001 at 02:14:41PM +0900, teespy wrote:
> 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.

It's always good to learn stuff :)

> I危 pretty sure there are better algorithms to do it, Iエd like to take a look if you want  to show them.

Well it's not much but here is my attempt. I gave up on it since it didn't seem
like anyone was interested in pursuing it any further. It can calculate the
number of possiblities for $100 in 1 hour 23 min. That's without initializing
the table. With the table it can do it in 0.03 secs.

And here it is

class Counter
	def initialize
		denoms = [10000, 5000, 2000, 1000, 500, 200, 100, 50, 25, 10, 
			5, 1]
		amounts = [9823546661906, 58853234019, 155848898, 3237135,
			111023, 2729, 293, 50, 13, 4, 2, 1]

		@table = {}
		@denoms = {}

		index = 0
		denoms.each do |i|
			@denoms[i] = denoms[index..-1]
			@table[i] = {}
			@table[i][i] = amounts[index]
			index = index + 1
		end
	end

	def count( amt, num_of_denoms = 10000 )
		if @table.has_key? amt
			if @table[amt].has_key? num_of_denoms
				return @table[amt][num_of_denoms]
			end
		end	

		ways = 0	

		@denoms[num_of_denoms].each do |i|
			if i > amt
				next
			elsif amt - i == 0
				ways = 1
			else
				ways += count( amt - i, i )
			end
		end
		@table[amt] = {}
		@table[amt][num_of_denoms] = ways
	end
end

counter = Counter.new
print counter.count( $*[0].to_i ), "\n"