A bunch of coin changer implementations with benchmarks and specs. Oddly, disabling the GC causes only some implementations to become faster while others slower.

coin_changer.rb

# Standard coin changer
def changer(change)
  [25,10,5,1].flat_map do |coin|
    remaining  = (change    / coin)
    change    -= (remaining * coin)
    [coin]     *  remaining
  end
end
changer(99)

# Coin changer with reduced assignment operations
def ch(amt)
  [25,10,5,1].flat_map do |coin|
    [coin] * (amt / coin)
    .tap { |rem| 
      amt -= rem * coin
     }
  end
end
ch(99)

# "Golfed" coin changer
def z(a)[25,10,5,1].flat_map{|c|[c]*(a/c).tap{|x|a-=x*c}}end
z(99)

# "No Assignment" coin changer
def chr(amt)
  [25,10,5,1].map { |x| amt / x }
             .zip([25,10,5,1])
             .flat_map{|quot, coin| [coin] * quot }
             .inject([]) { |acc, n|
               acc << n if acc.inject(n,:+) <= amt
               acc
             }
end
chr(99)

if $0 !~ /rspec/
  require 'benchmark'
  GC.disable
  Benchmark.bm(10) do |x|
    x.report('changer') { 1000.times { (0..100).each { |c| changer(c) }}}
    x.report('ch')      { 1000.times { (0..100).each { |c| ch(c)      }}}
    x.report('z')       { 1000.times { (0..100).each { |c| z(c)       }}}
    x.report('chr')     { 1000.times { (0..100).each { |c| chr(c)     }}}
  end
else
  describe "provides correct change" do
    [
      [100, [25,25,25,25]],
      [75,  [25,25,25]],
      [50,  [25,25]],
      [25,  [25]],
      [65,  [25, 25, 10, 5]],
      [37,  [25,10,1,1]]
    ].each do |amount, change|
       context "for #{amount}" do
         it "changer: #{change}" do
           changer(amount).should == change
         end
         it "chr: #{change}" do
           chr(amount).should == change
         end
         it "ch: #{change}" do
           ch(amount).should == change
         end
         it "z: #{change}" do
           z(amount).should == change
         end
       end
     end
  end
end