Exact change calculation

exactchange.go

/*
 * Exact change calculator (recursion learning exercice)
 * Eric Belanger // github.com/bilange // Twitter: @bilange
 * 
 * This code has been build to demonstrate how to do recursion, for people who
 * wants to know Go better via code examples. This code has been HIGHLY
 * documented to help the learning process. Feel free to fork, base upon or
 * otherwise copy this code! :-)
 *
 * This MAY be NOT the only way to do this task, so feel free to experiment!
 *
 * PS: The variables are named after the word 'denomination', as per
 * http://en.wikipedia.org/wiki/Denomination_%28currency%29
 *
 */ 

package main

import ( 
  "fmt"
  "sort"
  "math"
)

//Here, I am keeping all the valid currency denominations (still in
//circulation), you might want to change the values to reflect what's used in
//your country. Here, I have put what's used in Canada, eh. No need to put that
//in order, it'll be reordered later.
var denominations = []float64{ 
  50.00, 20.00, 10.00, 5.00, 100.00,
  2.00, 1.00, 0.25, 0.10, 0.05, 0.01,
}

//Here we keep track of how many coins/bills we need.
var denomSum = []float64{}

func main() {

  //Enter the amount due that you want to want to split in exact change here.
  var amount float64 = 438.99

  //This line has been extracted from http://golang.org/pkg/sort/#example_Interface_reverse
  //I'll attempt an explaination at the end of the code, but for now, let's
  //just say 'denominations' values will be reordered, highest first. Details
  //at the bottom of the code.
  sort.Sort(Reverse{sort.Float64Slice(denominations)})

  //That slice will keep track of how many coins/bills we need to give out.
  //Note that the order will match the order of the global 'denominations'
  //variable, order the biggest first.
  denomSum = make([]float64, len(denominations), len(denominations))

  //We call exactChange for the first time here. This will start our recursion
  //procedure. Passing the values, in order: 
  // - the (total) amount to calculate (438.99)
  // - 0, as we use that to first access denominations[0].
  exactChange(amount,  0)
  //Now, at this point in the code, denomSum contains the right amount of
  //bills/coins, and recursion has ended.

  fmt.Printf("The right quantity of coins and/or bills for %.2f$:\n", amount)
  for i := 0; i<len(denomSum); i++ {
    if denomSum[i] > 0 { 
      fmt.Printf("\t%1.0f x $%.2f\t= $%.2f\n", denomSum[i], denominations[i], denomSum[i] * denominations[i]) 
    }
  }
}

func exactChange(amount float64, denomination float64) {

  //Iterating into every coin/bill types held in the slice 'denominations'
  //If we are just getting started, we will use 0 for 'denomination' index.
  //However, this will be different if coming from recursion.
  for i := denomination; i < float64(len(denominations)); i++ {
    if denominations[int(i)] > amount { 
      //The current value held in 'i' points to a denominations[]
      //value higher than what's left to calculate anyway. Let's calculate with
      //the NEXT (+1, remember that we ordered our array accordingly in main())
      //coin or bill in our denominations[] slice.
      exactChange(amount, denomination + 1)

    } else { 
      //Our current denomination[i] can be used, as it fits what's left to calculate.

      /* 
       * As we're using floats all along, we cannot use the '%' modulo
       * operation on float types in Go. However, the fine folks at Go/Google
       * has come up with an equivalent function for floats.
       *
       *  math.Modf(): integer and fractional floating-point numbers that sum to f. 
       *      http://golang.org/pkg/math/#Modf
       *
       *  math.Mod(): Mod returns the floating-point remainder of x/y
       *      http://golang.org/pkg/math/#Mod
       */ 

      //Keeping what can possibly fit (the whole part) into the 'sum' slice
      denomSum[int(i)] , _ = math.Modf(amount / denominations[int(i)])

      //We STILL want to calculate for whatever's not fitting in our current
      //denomination. To do that, let's call the exactChange() again, but this
      //time with the "remainder", or that is the part that couldn't fit into
      //the current denomination.  
      //
      //As for the first parameter, if we were to, for example, calculate what
      //we need to give if we have an amount of 1.99$ after dealing with 1.00$,
      //we would say there's still 0.99$ left.
      //
      //As for the second parameter, we specify which index in our
      //denominations[] slice we want to start checking. It's totally useless
      //to start checking from the first, biggest denomination possible since
      //we are actually narrowing down denominations, so we're keeping track of
      //the 'current' denomination. Also, it's safe to skip the CURRENT
      //denomination (since we have calculated what can fits and what cannot
      //just above in the code execution), so we add +1 to start where we KNOW
      //there's gonna be a good chance of having a 'match'.
      exactChange(math.Mod(amount , denominations[int(i)]), denomination + 1)

      return
      //Furthermore, omitting a 'return' here will still continue in our 'for'
      //loop above, causing an endless loop.
    }
  }
}

//The following struct and function has been ripped off this URL:
//  http://golang.org/pkg/sort/#example_Interface_reverse
//
//Here's my ATTEMPTED explaination. Not for the faint of the heart. The magical line: 
//   sort.Sort(Reverse{sort.Float64Slice(denominations)})
// ...does this, kind of:
// - sort.Sort sorts, and needs an interface, that Reverse provide.
// - Reverse is a struct initialized with its only variable, a sort.Interface.
// - Reverse overrides the Interface's Less() by it's own, reversing the comparison
//   direction, causing the sort.Sort() method to re-order biggest first.
// - sort.Float64Slice()? I am missing the part (after looking at the code)
//   where I can simply pass 'denominations' as if Float64Slice was a function,
//   but since Float64Slice is a declaration of a new type this seems somehow legit 
//   see: http://golang.org/src/pkg/sort/sort.go?s=5280:5307#L223 for the code, 
//   or:  http://golang.org/ref/spec#Type_declarations for the reading
// - Float64Slice, as type of []float64, also have the methods implementing
//   Interface, defined here: http://golang.org/src/pkg/sort/sort.go?h=Interface#L11
type Reverse struct {
  sort.Interface
}

func (r Reverse) Less(i, j int) bool {
  return r.Interface.Less(j, i)
}

//On a second thought, this would have been less hassle to make a function that
//takes a float64[], iterates through every element and re-order them,
//recursively. I didn't go that route since the code in the Go's documentation
//is showing programming the "Go" way. If you want to do recursion on your own float64[], 
//this is left as homework to the reader :-)

//Thanks for reading!