```--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

@list << [priority, @list.length, item]
@list.sort!
self
end

def <<(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--

```