Greedy algorithm in Ruby - any suggestions?

Question

Here is my implementation of the greedy algorithim in Ruby. Do you have any suggestions?

class Greedy
 def initialize(unit, total, *coins)
 @total_coins = 0
 @unit = unit
 @total = total
 @currency = coins.sort
 @currency = @currency.reverse
 unless @currency.include?(1)
 @currency.push(1)
 end
 end
 def sort_coins
 @currency.each do |x|
 @pos = @total / x
 @pos = @pos.floor
 @total_coins += @pos
 @total -= x * @pos
 puts "#{@pos}: #{x} #{@unit}"
 end
 puts "#{@total_coins} total coins"
 end
end

• mmdemirbas: It is "a solution using a greedy algorithm", not "the Greedy Algorithm" itself. Greedy algorithm is a concept.

Answer 1

@currency could be renamed @currencies, or perhaps better, @denominations. Naming an array in the plural leads to easy naming when iterating, e.g.:

@currencies.each do |currency|

instead of:

@currency.each do |x|

The name of method sort_coins doesn't match what it's doing. Whether or not it's sorting, it's also printing. A better name might be print_coins.

@quotient might be a better name for @pos.

Most of the variables in sort_coins do not need to be member variables: @pos and @total_coins should lose the @. And, if you decide to make it an argument to sort_coins (see below), @total as well.

This:

@currency = coins.sort
@currency = @currency.reverse

Could be this:

@currency = coins.sort.reverse

The initialization of @total_coins needs to move from the constructor to sort_coins. This prevents a bug triggered by calling sort_coins more than once.

Consider passing total to sort_coins rather than to the constructor. This would allow sort_coins to be called on an instance of Greedy with a different total each time, and no need to create a new instance of Greedy for each. It would also get the variable's initialization closer to where it is used, making for simpler code.

Consider the constructor argument for the set of coins bing simply coins rather than *coins, because it makes the calling code easier to understand. E.g.,

Greedy.new('cents', 71, 1, [5, 10, 25, 50]).sort_coins

vs.

Greedy.new('cents', 71, 1, 5, 10, 25, 50).sort_coins

Put a line of white space between methods, and at the top and bottom of the class definition.

---

If all acted upon, these suggestions yield:

class Greedy
 def initialize(unit, coins)
 @unit = unit
 @demoninations = coins.sort.reverse
 unless @demoninations.include?(1)
 @demoninations.push(1)
 end
 end
 def print_coins(total)
 total_coins = 0
 @demoninations.each do |demonination|
 quotient = (total / demonination).floor
 total_coins += quotient
 total -= demonination * quotient
 puts "#{quotient}: #{demonination} #{@unit}"
 end
 puts "#{total_coins} total coins"
 end
end
Greedy.new('cents', [1, 5, 10, 25, 50]).print_coins(72)
#=> 1: 50 cents
#=> 0: 25 cents
#=> 2: 10 cents
#=> 0: 5 cents
#=> 2: 1 cents
#=> 5 total coins

• Docunext: Thanks for adding the use of the class and what it will output - it helped me figure out what was going on quickly.