3
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ It is "a solution using a greedy algorithm", not "the Greedy Algorithm" itself. Greedy algorithm is a concept. \$\endgroup\$ – mmdemirbas May 4 '12 at 15:02
4
\$\begingroup\$

@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
\$\endgroup\$
  • \$\begingroup\$ Thanks for adding the use of the class and what it will output - it helped me figure out what was going on quickly. \$\endgroup\$ – Docunext Nov 7 '12 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.