--X1bOJ3K7DJ5YkBrT
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline


my solution(s).

g phil
--X1bOJ3K7DJ5YkBrT
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="make_change.rb"

#!/usr/bin/ruby

# ------------------------------------------------------------
# 1st approach: recursive, short, but slow
#
# def make_change(amount, coins  25, 10, 5, 1])
# 	return [amount] if coins.include?(amount)
# 	options  }
# 	coins.select { |c| c < amount }.each { |coin| options[coin]  ake_change(amount - coin, coins) }
# 	pick  ptions.values.sort { |a, b| a.size <b.size }.first
# 	([options.index(pick)] + pick).sort.reverse
# end

# ------------------------------------------------------------
# 2nd approach: much faster
# Making use of Daniel Martins's PriorityQueue from Quiz #98

class PriorityQueue

	def initialize
		@list  ]
	end

	def add(priority, item)
		@list << [priority, @list.length, item]
		@list.sort!
		self
	end

	def <<(pritem)
		add(*pritem)
	end

	def next
		#puts @list.first.inspect
		@list.shift[2]
	end

	def empty?
		@list.empty?
	end

end

def make_change(amount, coins  25, 10, 5, 1])
	return [] if amount
	pqueue  riorityQueue.new
	solution  il
	coins.sort.reverse.each { |coin| pqueue << [0, [coin, [], coin]] if coin < mount }
	until pqueue.empty?
		coin, change, sum  queue.next
		return solution if solution && change.size > solution.size
		change  hange + [coin]
		solution  hange.sort.reverse if sum
mount
		coins.each do |coin|
			priority  hange.size + amount - (sum + coin)
			pqueue << [priority, [coin, change, sum + coin]] if sum + coin < mount
		end
	end
	nil
end


--X1bOJ3K7DJ5YkBrT--