3
\$\begingroup\$

I have a task to make a checkout line controller. First it receives, as input, an amount of checkouts and commands. Then commands that are C for coming and L for leaving, and after those the number of the checkout they are coming/leaving. Also, if there is someone at the checkout, they should be sent to the nearest empty one. If 2 are equally near, the one with the lowest number is chosen.

Input could be:

3 5
C 1
C 2
L 1
C 1
C 1

As output it just tells the checkout where each arriving customer is served. So output would be:

1
2
1
3

Code:

#include <iostream>
#include <vector>
using namespace std;

int main () {
    int n, m, checkout;
    char action;
    vector <int> output (0);

    cin >> n >> m; 

    vector <bool> state (n,false); //

    for (int i = 0; i < m; i++) {
        cin >> action >> checkout;
        checkout--; //Aligns checkout number with vectors number

        if (action == 'C') { //If someone comes
            if (state[checkout] == false) { //If the checkout he comes to is empty
                state[checkout] = true; // If it is, it's not anymore
                output.push_back(checkout + 1);
            } else { // If it isn't, check which is the closest empty one
                for (int i = 1; i < n; i++) { //Loops through below and above checkouts
                    if (checkout - i >= 0) { 
                        if (state[checkout - i] == false) {
                            state[checkout - i] = true;
                            output.push_back(checkout - i + 1);
                            break;
                        }
                    }
                    if (checkout + i < n) {
                        if (state[checkout + i] == false) {
                            state[checkout + i] = true;
                            output.push_back(checkout + i + 1);
                            break;
                        }
                    }
                }
            }
        }
        if (action == 'L') {
            state[checkout] = false;
        }
    }
    for ( int j = 0; j < output.size(); j++) {
        cout << output[j] << endl; //Outputs after all input is over (somone said I should do this)
    }
}

My program runs too slowly. I use codejudge.net to check if it is working properly. I have already improved it a lot, from what I started with, but it still doesn't cut it.

This question was originally posted on Stack Overflow.

\$\endgroup\$
  • \$\begingroup\$ Please never write if(boolean == true) but just write if(boolean). This is an equasion to much. \$\endgroup\$ – chillworld Feb 21 '16 at 7:32
  • \$\begingroup\$ @chillworld Please write that as an answer. \$\endgroup\$ – 200_success Feb 21 '16 at 15:25
2
\$\begingroup\$

I see some things that may help you improve your code.

Don't abuse using namespace std

Putting using namespace std within your program is generally a bad habit that you'd do well to avoid.

Check for errors

It may not be part of your assignment, but you should know that real programs should check for errors and handle them appropriately.

Use a function

Right now, everything is in main but we could make things a little more clear by creating a function. Specifically, as each customer arrives at a register, they need to find the nearest open register. This suggests a function: findNearestOpenRegister which could take a proposed register as an argument. However, this function would have to get a number of other things passed to it which suggests a further refinement, described in the next suggestion.

Use an object

We can make the main code cleaner by using an object to represent the array of cashiers at a store. I'd probably write it like this:

// represents a linear array of checkout registers at a store
class Checkout {
public:
    Checkout(int registerCount)
    : unoccupied(registerCount, true)
    {}
    int arrive(int r) { 
        int lo, hi;
        for (lo = hi = r; lo >= 0 || hi < unoccupied.size(); --lo, ++hi) {
            if (lo >= 0 && unoccupied[lo]) {
                unoccupied[lo] = false;
                return lo;
            } else if (hi < unoccupied.size() && unoccupied[hi]) {
                unoccupied[hi] = false;
                return hi;
            }
        }
        return ERROR;   // this is an error condition!
    }
    int leave(int r) { 
        if (unoccupied[r]) 
            return ERROR;
        unoccupied[r] = true; 
        return r;
    }
    static constexpr int ERROR = -1;
private:
    std::vector <bool> unoccupied;
};

Now the main function can use the object:

int main () {
    int n;
    int m; 

    std::cin >> n >> m; 
    Checkout reg(n);

    for (int i = 0; i < m; ++i) {
        int checkout;
        char action;
        std::cin >> action >> checkout;
        --checkout; // checkout is 1-based in input, zero-based internally
        switch(action) {
            case 'C':  // someone comes to the register
                checkout = reg.arrive(checkout); 
                if (checkout == Checkout::ERROR) {
                    std::cout << "Error: no free registers in line " << i+2 << ".\n";
                    return 1;
                }
                std::cout << ++checkout << '\n';
                break;
            case 'L':  // someone leaves the register
                checkout = reg.leave(checkout); 
                if (checkout == Checkout::ERROR) {
                    std::cout << "Error: attempt to leave free register in line " << i+2 << ".\n";
                    return 1;
                }
                break;
            default:
                std::cout << "Error: unknown action '" << action << "' in line " << i+2 << ".\n";
                return 1;
        }
    }
}

Note that error checking has been added, as per the earlier suggestion. Also note that rather than storing the output, this version simply emits it as it's generated, avoiding the additional data structure that is otherwise needed.

Profile the program

If you find that the program is not performing as fast as you need, the first step should be to try to find out where the program is spending its time. This can be done by several different methods. I tend to use gprof. Among the possibilities are using a different data structure. See this question for an example. Another possibility is to execute std::ios_base::sync_with_stdio(false);, but whether that speeds thing up or not is uncertain until you measure.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Ehm, okay. I am not very good at coding yet. There are numerous thing here I don't understand. In the object, what are you doing in line 4, 5 and 6? What does constexpr mean? \$\endgroup\$ – Rasmus Tollund Feb 21 '16 at 20:18
  • \$\begingroup\$ No worries; we're all here to improve our coding skills. For constexpr see the link. Lines 4-6 are a constructor. \$\endgroup\$ – Edward Feb 21 '16 at 20:43
  • \$\begingroup\$ Why did you change from "occupied" to "unoccupied"? \$\endgroup\$ – Deduplicator Feb 22 '16 at 0:13
  • \$\begingroup\$ Because each time unoccupied is checked, it would have had to be negated if it were occupied. \$\endgroup\$ – Edward Feb 22 '16 at 0:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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