4
\$\begingroup\$

I would like to know if this function is correct (I know that it works, but I have not got enough knowledge so as to demonstrate that it is correct).

Indication: a colleccio is defined as a vector< int > always of size 12, so I can represent the number of banknotes and/or coins of value 50, 20, 10, 5, 2, 1, 0.50, 0.20, 0.10, 0.05, 0.02, 0.01 € in positions 0..11.

Example: if I want to store 5 x 50€ + 2 x 20€ + 0 x 10€ + 1 x 5€ +... et cetera, I would type: colleccio v(12); v[0]=5; v[1]=2; v[2]=0; and so on.

Pre:

  • No money exchange has been done before the function.
  • machine is a valid colleccio: it is the content of the machine (how many banknotes and/or coins has inside).
  • paid is another valid colleccio but, in this case, it is what the user has paid.
  • possible_change is an empty colleccio.
  • numeric_change is a valid currency (X.XX€, two decimals, positive value). Its value is the price of the product - what the customer has paid. Its value is valid before computing the function.

Description and post: i_have_change checks if, given machine and paid, exists a possible_change to be returned to the user lately. If it is possible, in possible_change there will be a valid colleccio in which it is stored the most optimum change (that is: the less "currency" items (banknotes/coins), the better). machine should be correctly modified (it doesn't matter if it changes even though I cannot give change).

Code:

bool i_have_change (colleccio& machine, const colleccio& paid,
                    colleccio& possible_change, double numeric_change) {
  vector<double> p(12); //the values of the currency are stored in p.
  p[0] = 50.; p[1]  = 20.;  p[2]  = 10.;
  p[3] =  5.; p[4]  =  2.;  p[5]  =  1.;
  p[6] = .50; p[7]  = .20;  p[8]  = .10;
  p[9] = .05; p[10] = .02; p[11]  = .01;

  //Add `paid` to `machine`
  for (int i = 0; i < paid.size(); ++i)
    machine[i] += paid[i];

  //I start with `numeric_change` (> 0) and I keep on subtracting all $$$
  //as much as I can (they are always <= `numeric_change`)
  for (int i = 0; i < machine.size() and numeric_change > 0; ++i) {
    while (p[i] <= numeric_change and machine[i] >= 1) {
      numeric_change -= p[i];
      ++possible_change[i];
      --machine[i];
    }
  }

  //If I still have `numeric_change`, I have not physical change!
  if (numeric_change != 0) return false;

  //Else, everything is correct and I've got change.
  return true;
}
\$\endgroup\$
2
  • \$\begingroup\$ canvi_numeric should be numeric_change. I assume it a copy-paste error, please fix. \$\endgroup\$
    – vnp
    Jan 6, 2016 at 22:10
  • \$\begingroup\$ paid is […] what the user has paid vs. numeric_change is [price] - what the customer has paid - not clear. By all means, comment the code. Using float/double for amounts of currency is against conventional wisdom - just use cents (or even millicents). If numeric_change is positive to begin with, the customer has not fully paid yet. You don't actually ask a question - advice: try to give as few notes and coins as possible/prefer to give larger denominations. If you need to return 6 cent, have 1 coin of 5, 4 of 2, and 0 of 1 cent, you're in trouble if you hand out that 5 cent coin. \$\endgroup\$
    – greybeard
    Jan 7, 2016 at 1:13

1 Answer 1

3
\$\begingroup\$

I see a number of things that may help you improve your code. Because it makes a lot of things simpler, I'm going to assume that you and your compiler are able to handle C++11.

Post complete code

Here on Code Review, we prefer longer and more complete questions and code which is different from many of the other sister sites. For that reason, when posting a question here for review, it's often best to include a short driver code showing the context of how your code is intended to be used. It helps reviewers quickly understand your code and give you a better review.

Use const where practical

The std::vector p gets created and destroyed every time the function is invoked. That's not very efficient and not at all necessary. Instead, we can make it static so it's created once and const because it shouldn't change. We can do that with this single line:

static const std::vector<double> p{ 50, 20, 10, 5, 2, 1, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01 };

Don't use floating point for money

There is a problem using floating point (that is, float or double types) fto represent money values. For example, when I tried to use your code to return €0.03 I only got €0.02. This is a fundamental problem with using double (or any floating-point representation) for money values. An alternative is to keep a number of cents as an integer value internally. For more depth about floating point issues, I'd recommend the excellent article "What every computer scientist should know about floating-point arithmetic" by David Goldberg.

Simplify expressions

The code currently has these lines:

if (numeric_change != 0) return false;
return true;

We can simplify this to:

return !numeric_change;

However this is something of a problem with floating point values. Either change the variable to use and integer type or compare to a real value smaller than your minimum change amount. For example, you might use 0.005. Much better would be to use integers.

Think carefully about the problem

If the vending machines contains €0.07 and I put in €50.00 for something that costs €10.00 what I would want to have happen is that I would get my €50.00 back and not the €10.00 item. What the program seems to actually do, however, is return €0.07. That is, I would expect that the function would return the value false (which it does), and then have possible_change identical to the paid object. The specification you quote is not very clear on this issue, but it seems like the right behavior to me.

Putting it all together

Using these suggestions, here is what the routine becomes:

bool i_have_change (colleccio& machine, const colleccio& paid,
                colleccio& possible_change, double numeric_change) {
    static const std::vector<unsigned> p{ 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5, 2, 1 };

    //Add paid to machine
    for (size_t i = 0; i < paid.size(); ++i)
        machine[i] += paid[i];


    unsigned change = numeric_change * 100;
    //I start with change (> 0) and I keep on substracting all $$$
    //as I can (they are always <= change)
    for (size_t i = 0; i < machine.size() and change > 0; ++i) {
        while (p[i] <= change and machine[i] >= 1) {
            change -= p[i];
            ++possible_change[i];
            --machine[i];
        }
    }

    if (change) {
        // can't make change so return money
        for (size_t i = 0; i < paid.size(); ++i) {
            possible_change[i] = paid[i];
        }
    } 
    //If I still have change, I have not physical change!
    return !change;
}

Test code

Since the code for colleccio objects was not given, I created my own to test the code.

#include <vector>
#include <initializer_list>
#include <iostream>
#include <numeric>

class colleccio : public std::vector<int>
{
public:
    colleccio(std::initializer_list<int> w) :
        std::vector<int>{w}
    {}
    colleccio() : std::vector<int>(12) {}
    double value() const { return std::inner_product(v.begin(), v.end(), begin(), 0)/100.0; }
    friend std::ostream& operator<<(std::ostream& out, const colleccio& col) {
        out << "{ ";
        for (const auto n : col)
            out << n << ", ";
        return out << "} = " << col.value();
    }
private:
    static const std::vector<unsigned> v;
};

const std::vector<unsigned> colleccio::v{ 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5, 2, 1 };

Now here is a convenience macro and test code in main.

#define SHOW(X) std::cout << # X " = " << (X) << std::endl

int main()
{
    colleccio machine{0, 0, 0, 0, 
                      0, 0, 0, 0,
                      0, 0, 0, 7};
    colleccio paid   {1, 0, 0, 0, 
                      0, 0, 0, 0,
                      0, 0, 0, 0};
    colleccio change;
    double chg_amount{40.0};

    std::cout << std::boolalpha;
    SHOW(machine);
    SHOW(paid);
    SHOW(change);
    SHOW(chg_amount);
    SHOW(i_have_change(machine, paid, change, chg_amount));
    SHOW(machine);
    SHOW(paid);
    SHOW(change);
    SHOW(chg_amount);
}

Sample output

machine = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, } = 0.07
paid = { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, } = 50
change = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, } = 0
chg_amount = 40
i_have_change(machine, paid, change, chg_amount) = false
machine = { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, } = 50
paid = { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, } = 50
change = { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, } = 50
chg_amount = 40
\$\endgroup\$
6
  • 1
    \$\begingroup\$ Well, ... my code would be ridiculous compared with that... Anyway, really thank you for your answer, and I changed the trick '- 0.005' just in case to improve my algorithm, but I see that you've catched it perfectly. \$\endgroup\$
    – JnxF
    Jan 7, 2016 at 0:17
  • \$\begingroup\$ Also, my colleccio was declared much simpler than yours (and less powerful, of course). Just: typedef vector<int> colleccio. It was just an atempt to give a "proper" name to that data-type. All the function you use (like calculating the total amount of a collectio where done by an auxiliar function). BTW: is it possible to "lock" the size of a vector? Because I do only know how to declare them with variable size. \$\endgroup\$
    – JnxF
    Jan 7, 2016 at 0:19
  • 1
    \$\begingroup\$ Technically, yes, one could lock the size of a std::vector by writing and providing a custom allocator but that's a rather advanced technique and technically dubious if you wanted to use for everything a std::vector supports. In real life, if I wanted to have a fixed size collection, I would use std::array instead of std::vector. \$\endgroup\$
    – Edward
    Jan 7, 2016 at 0:28
  • \$\begingroup\$ If the vending machines contains [< cost] and I put in [single denomination ≥ 2×cost] for something that costs [cost] what I would want to have happen is … - one of my pet peeves is, when trying to pay a 0€99 item with 1€, to not be offered Can't give change. Press Continue to just go ahead, pay 4 more cents to get 5 back. \$\endgroup\$
    – greybeard
    Jan 7, 2016 at 4:47
  • 1
    \$\begingroup\$ That's where the specification is actually clear: machine should be correctly modified (it doesn't matter if it changes even though I cannot give change). \$\endgroup\$
    – Edward
    Jan 8, 2016 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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