Vending machine change function

Question

Write a function that takes an amount of money M, a price P and returns the change given in the smallest number of coins. The following coins are available: 1c, 5c, 10c, 25c, 50c, and $1. Time: 20min.

I'm looking for all sorts of reviews considering the time limit and environment.

Here's my code:

#include <iostream>
#include <vector>

std::vector<int> getChange(double M, double P)
{
  /*
    1c, 5c, 10c, 25c, 50c, and $1
    getChange(3.14, 1.99) should return [0,1,1,0,0,1]
    getChange(4, 3.14) should return [1,0,1,1,1,0]
    getChange(0.45, 0.34) should return [1,0,1,0,0,0]
  */

  int denominations[] = {1, 5, 10, 25, 50, 100};
  std::vector<int> r(sizeof denominations / sizeof denominations[0]);

  // I had a floating-point problem here by computing cents = (M-P)*100;
  // it took me a few minutes to figure it out
  int cents = (int)(M*100) - (int)(P*100);

  for(int i = sizeof denominations / sizeof denominations[0] - 1; i >= 0; --i){
    r[i] = cents / denominations[i];
    cents = cents % denominations[i];
  }

  return r;
}

int main()
{
  auto change = getChange(5, 0.99);
  for(auto i : change){
      std::cout << i << ", ";
  }
  std::cout << std::endl;
  return 0;
}

Answer 1

You still have a floating point problem

If you change your line to this input:

auto change = getChange(0.04, 0.03);

you will get the following output:

2, 0, 0, 0, 0, 0,

As you can see, it answers with 2 pennies instead of one. The problem is with the line that you "fixed":

// I had a floating-point problem here by computing cents = (M-P)*100;
// it took me a few minutes to figure it out
int cents = (int)(M*100) - (int)(P*100);

You did notice a problem with your floating point conversion but you came to the conclusion that it was the subtraction that was the problem. The actual problem is that a floating point value of something like 0.03 can sometimes be slightly above or slightly below the actual value of 0.03. In this case, it is slightly below. When you convert this value to cents by using (int)(P*100), you end up converting something like 2.999999 to 2 instead of 3.

One way to avoid this problem is to round instead of truncate. So you can change your line to this to fix the problem:

int cents = (int) (100*(M-P) + 0.5);

Answer 2

State your assumptions

The problem statement didn't specify the input and output formats, so document your choices. Personally, I would have chosen a fixed-point representation (e.g. a long number of cents) for input rather than floating-point, and some form of "bag" structure (e.g. std::map<int,long> representing value and quantity) for the output.

Unit tests - lots of them

You've included a single "happy-path" test, but I'd like to see a lot more.

What if P > M? Does P == M work correctly? What if P and/or M is ±infinity, or NaN?

The denominations don't need to be modifiable or local

The denominations array can be constant:

static const int denominations[] = {1, 5, 10, 25, 50, 100};

Because it is superincreasing, it may simplify the code significantly to express it sorted in the reverse order, i.e. {100, 50, 25, 10, 5, 1}, so that we can iterate over it in the natural order.

At some point, we'd be likely to pass it as a parameter (to allow for future changes to coinage, or use in other countries - e.g. in Scotland, we'd use {200, 100, 50, 20, 10, 5, 2, 1}).

---

Improved version

#include <map>

using coin_bag = std::map<unsigned int, unsigned long>;

// Calculate the change from P-M as a bag of coins
// Empty result may mean M==P or an error condition such as underpayment.
// Otherwise, it's a map of coin value => number of coins
// Note: we make no attempt to avoid or detect integer overflow.
coin_bag getChange(long M, long P)
{
    if (M <= P) {
        // no change given
        return {};
    }
    auto change = M - P;

    static const auto denominations = {100, 50, 25, 10, 5, 1};
    coin_bag coins;
    for (auto c: denominations) {
        auto q = change / c;
        if (q > 0) {
            coins[c] = q;
            change -= c * q;
        }
    }

    return coins;
}


// Test program

#include <iostream>

// helper
std::ostream& operator<<(std::ostream& os, const coin_bag& coins)
{
    const char *sep = "";
    os << "{";
    for(auto i : coins) {
        os << sep << i.second << " x " << i.first << 'c';
        sep = ", ";
    }
    os << "}";
    return os;
}


int test_change(long money, long price, const coin_bag& expected)
{
    auto actual = getChange(money, price);
    if (actual == expected) {
        // passed
        return 0;
    }

    // failed!
    std::cout << "Failed: getChange(" << money << ", " << price << ")"
              << " == " << actual << " != " << expected << std::endl;
    return 1;
}

int main()
{
    return test_change(0, 0, {})
        +  test_change(-1, 0, {})
        +  test_change(0, 1, {}) // underpaid
        +  test_change(0, -1, {{1, 1}}) // refund
        +  test_change(9, 0, {{5, 1}, {1, 4}})
        // and the examples from the original comments:
        +  test_change(314, 199, {{100, 1}, {10, 1}, {5, 1}})
        +  test_change(400, 314, {{50, 1}, {25, 1}, {10, 1}, {1, 1}})
        +  test_change(45, 34, {{10, 1}, {1, 1}})
        ;
}

---

Enhancement: show coin names

#include <map>
#include <functional>

using coin_bag = std::map<unsigned int, unsigned long>;

static const std::map<unsigned int, const char*, std::greater<unsigned int>>
us_coins = {{100, "$1"}, {50, "50¢"}, {25, "25¢"}, {10, "10¢"}, {5, "5¢"}, {1, "1¢"}};


// Calculate the change from P-M as a bag of coins
// Empty result may mean M==P or an error condition such as underpayment.
// Otherwise, it's a map of coin value => number of coins
// Note: we make no attempt to avoid or detect integer overflow.
coin_bag getChange(long M, long P)
{
    if (M <= P) {
        // no change given
        return {};
    }
    auto change = M - P;

    coin_bag coins;
    for (auto c: us_coins) {
        auto q = change / c.first;
        if (q > 0) {
            coins[c.first] = q;
            change -= c.first * q;
        }
    }

    return coins;
}


// Test program

#include <iostream>

// helper
std::ostream& operator<<(std::ostream& os, const coin_bag& coins)
{
    const char *sep = "";
    os << "{";
    for(auto i : coins) {
        os << sep << i.second << " x " << us_coins.at(i.first);
        sep = ", ";
    }
    os << "}";
    return os;
}


int test_change(long money, long price, const coin_bag& expected)
{
    auto actual = getChange(money, price);
    if (actual == expected) {
        // passed
        return 0;
    }

    // failed!
    std::cout << "Failed: getChange(" << money << ", " << price << ")"
              << " == " << actual << " != " << expected << std::endl;
    return 1;
}

int main()
{
    return test_change(0, 0, {})
        +  test_change(-1, 0, {})
        +  test_change(0, 1, {}) // underpaid
        +  test_change(0, -1, {{1, 1}}) // refund
        +  test_change(9, 0, {{5, 1}, {1, 4}})
        // and the examples from the original comments:
        +  test_change(314, 199, {{100, 1}, {10, 1}, {5, 1}})
        +  test_change(400, 314, {{50, 1}, {25, 1}, {10, 1}, {1, 1}})
        +  test_change(45, 34, {{10, 1}, {1, 1}})
        ;
}

Answer 3

General approach looks good. But loop in the getChange I really do not like... So I have modified your code adding comments about every change I made. To make it easier to find - I have removed your comments - it is not indication that they not belong - just temporal workaround...

std::vector<int> getChange(double M, double P)
{
    //use vector instead of C-array
    //add const
    //reverse order of values
    const std::vector<int>  denominations = {100,50,25,10,5,1};
    std::vector<int> r;//init empty vector - plan to use emplace_back

    //since the final size is known - 
    //set the proper capacity to avoid copying when resizing
    r.reserve(denominations.size());

    //use static_cast instead of C-style cast
    //adding rounding fix
    int cents = static_cast<int>(M*100+.5) - static_cast<int>(P*100+.5);

    for(auto val:denominations) { //get rid of horrible index loop
        //since we do not have index - use emplace_back
        r.emplace_back( cents / val); 
        cents %= val;
    }

    return r;
}

Now the function logic is the same - just the order of values in the result is opposite. I feel like code looks cleaner like this.

For the main - - it is just a preference - I would want to see count of coins with names. So I have extended the loop in main to add this functionality - but this modification is completely optional.

#include <iostream>
#include <vector>
#include <string>

int main()
{
    auto change = getChange(3.14, 1.99);

    //create parallel vector of names
    const std::vector<std::string>  den_names = {"1$","50c","25c","10c","5c","1c"};

    //go over 2 vectors in parallel using const iterator
    auto it2 = den_names.cbegin();
    for(auto it = change.cbegin(); it != change.cend(); ++it,++it2) {
        if(*it > 0) {//skip zeros
            //show both - count of coins and coin name
            std::cout << *it << "*" << *it2 << ", "; 
        }
    }
    std::cout << std::endl;
    return 0;
}