# Greedy algorithm in Ruby - any suggestions?

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

• It is "a solution using a greedy algorithm", not "the Greedy Algorithm" itself. Greedy algorithm is a concept. May 4, 2012 at 15:02

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


@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

• Thanks for adding the use of the class and what it will output - it helped me figure out what was going on quickly. Nov 7, 2012 at 14:09