On Jan 25, 8:50=A0am, Ruby Quiz <ja... / grayproductions.net> wrote:
> This week's Ruby Quiz is to complete a change making function with this
> skeleton:
>
> =A0 =A0 =A0 =A0 def make_change(amount, coins =3D [25, 10, 5, 1])
>
> =A0 =A0 =A0 =A0 end

Here's my solution. Unlike greedy or giving algorithms that round one
way or the other if the exact change cannot be made, mine explicitly
returns nil.

I added an optional argument to choose how to break ties. I figure
this is legal, since it duck types with the method 'signature' above.


# If multiple solutions exist that have the same number of coins,
# the winning answer is determined by the value of 'avoid_pennies':
#   If true, whichever answer gives the biggest of the small change is
used.
#   If false, whichever answer gives the biggest of the large change
is used.
def make_change( amount, coins=3D[25,10,5,1], avoid_pennies=3Dtrue,
recursing=3Dfalse )
  # Don't sort in place, in case the user wants to preserve the coin
array
  coins  =3D coins.sort_by{ |coin| -coin }
  owed   =3D amount
  change =3D []
  coins.each{ |coin|
    while owed >=3D coin
      owed -=3D coin
      change << coin
    end
  }
  change =3D nil unless owed =3D=3D 0

  if recursing
    change
  else
    answers =3D [ change ]
    while coins.shift
      answers << make_change( amount, coins, avoid_pennies, true )
    end
    answers.compact.sort_by{ |answer|
      [
        answer.length,
        -answer.send( avoid_pennies ? :last : :first )
      ]
    }.first
  end
end