5
\$\begingroup\$

I've made a solution for a problem which involves changing order of objects having some mass, so it costs a mass of an object A and a mass of an object B to make a swap. The program needs to read a number of objects, their masses, their starting and ending order and calculate lowest cost of swapping objects to final order. The solution is correct in terms of calculations. The txt file has numbers in each line and name of a file is passed as command line argument. I would like to ask how should I split operations into separate functions and load data? What can I do to make a code cleaner? I am also wondering what exceptions should I made for invalid inputs?

#define min(a,b) ((a) < (b) ? (a) : (b))
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>

void readFromFile(int argc, char* argv[],const int MAX_VERTEXES, const int MIN_VERTEXES, int &n, int &minWeightGlobally, std::vector<int> &weights, std::vector<int> &startingOrder, std::vector<int> &endingOrder)
{   
    std::ifstream file;
    if (argc >= 2)
    {
        file.open(argv[1]);
    }
    else
    {
        throw std::exception("No parameter passed");
    }
    std::string line;

    if (file.is_open())
    {
        for (int z = 0; z < 4; z++)
        {
            std::getline(file, line);
            if (line.empty()) throw std::logic_error("Invalid input");
            std::istringstream iss(line);

            if (z == 0)
            {
                iss >> n;
                if (n<MIN_VERTEXES || n>MAX_VERTEXES) throw std::exception("Invalid amount of vertices");
            }
            if (z == 1)
            {
                weights.reserve(n);
                for (int a = 0; a < n; a++)
                {
                    int d;
                    iss >> d;
                    weights.push_back(d);
                    minWeightGlobally = min(minWeightGlobally, weights[a]);
                }
            }
            if (z == 2)
            {
                startingOrder.reserve(n);
                for (int a = 0; a < n; a++)
                {
                    int d;
                    iss >> d;
                    startingOrder.push_back(d - 1);
                }
            }
            if (z == 3)
            {
                endingOrder.reserve(n);
                for (int a = 0; a < n; a++)
                {
                    int d;
                    iss >> d;
                    endingOrder.push_back(d - 1);
                }
            }
        }
        file.close();
    }
    else
    {
        throw std::exception("Unable to open file");
    }
}

long long calculateLowestCostOfWork(int const &n, int const &MAX_WEIGHT, int const &minWeightGlobally, std::vector<int>& weights, std::vector<int>& startingOrder, std::vector<int>& endingOrder)
{
    std::vector<int> permutation(n);
    std::vector<bool> visitedVertexes(n);

    long long result = 0;
    //constructing permutation p
    for (int i = 0; i < n; i++)
        permutation[endingOrder[i]] = startingOrder[i];

    for (int i = 0; i < n; i++)
    {
        int numberOfElementsInCycle = 0;
        int minWeightInCycle = MAX_WEIGHT;
        long sumOfWeightsInCycle = 0;
        if (!visitedVertexes[i])
        {
            int x = i;
            //decomposition for simple cycles and calculating parameters for each cycle
            while (!visitedVertexes[x])
            {
                visitedVertexes[x] = true;
                numberOfElementsInCycle++;
                x = permutation[x];
                sumOfWeightsInCycle += weights[x];
                minWeightInCycle = min(minWeightInCycle, weights[x]);
            }
            //calculating lowest cost for each cycle
            result += (long long)min((sumOfWeightsInCycle + (numberOfElementsInCycle - 2) * minWeightInCycle), (sumOfWeightsInCycle + minWeightInCycle + (numberOfElementsInCycle + 1) * minWeightGlobally));
        }
    }
    return result;
}

int main(int argc, char *argv[]) 
{
    const int MAX_WEIGHT = 6500, MAX_VERTEXES = 1000000, MIN_VERTEXES = 2;
    std::vector<int> weights, startingOrder, endingOrder;
    int n=0;
    int minWeightGlobally = MAX_WEIGHT;
    try
    {
        readFromFile(argc, argv,MAX_VERTEXES, MIN_VERTEXES, n, minWeightGlobally, weights, startingOrder, endingOrder);
    }
    catch (...)
    {
        std::cout << "Error";
    }

    std::cout << calculateLowestCostOfWork(n,MAX_WEIGHT,minWeightGlobally,weights,startingOrder,endingOrder);

    return 0;
}

The input file is in form like below, first line (int n in code) it's telling about amount of objects (that's a nice name to include). Second line has their weights, third line startingOrder and last endingOrder. The task is to calculate a cost of move of objects(a cost is defined by sum of weights of two objects that are moved) from starting to ending order.

8
197 170 124 180 128 163 188 140
2 5 7 8 1 3 6 4
5 6 1 8 2 4 7 3

So ideally there should be exactly as many numbers in each row in each vector as in first line. The worst case scenario is obviously no values in any line after first line, so we will move through undeclared memory or out of bounds and we will get out of bounds exception. In the other cases program could calculate something, although there is a little possibility that it will calculate something good e.g input like this is valid e.g

8
197 170 124 180 128 163 188 140
1 2 3
3 1 2

is valid, but obviously it should calculate for 8 numbers, not for only three.

\$\endgroup\$
  • \$\begingroup\$ Hello. I am new to C++.Could you explain what long long functionName does ? \$\endgroup\$ – Manos Kounelakis Aug 16 at 5:56
  • \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. If your changes to the code are substantial, consider asking a follow-up question instead. \$\endgroup\$ – Mast Aug 16 at 6:04
  • \$\begingroup\$ @ManosKounelakis It's calculating the lowest cost of swaping of objects(swap is defined by changing two objects position and cost of that swap is sum of masses first and second object) from starting order into ending order. Permutation array is kinda function of changing (permutation) collection->collection, so i've included it into function permutation(ending order)=startingOrder. It's creating a simple graph with edges that e.g 1 has to be in place 2, that's what permutation function is saying. VisitedVertexes array is default set with false values. So loops are traveling through graph. \$\endgroup\$ – Jan Dycz Aug 16 at 14:16
  • \$\begingroup\$ Then you can have two methods of swapping, either you make swaps with lowest weight in cycle or you can "borrow" an object with lowest weight globally and make swaps with it. So in min(method1, method2) i am picking the lowest cost. Then i sum it up into result and do loops as long as there are cycles. \$\endgroup\$ – Jan Dycz Aug 16 at 14:22
  • \$\begingroup\$ @JanDycz no I was asking about the function signature long long functionName. I haven't seen something similar. \$\endgroup\$ – Manos Kounelakis Aug 16 at 14:45
9
\$\begingroup\$

Some minor comments:

  • No need to define min. Just #include <algorithm>and use std::min.

  • Move your magic numbers (like MAX_WEIGHT) right after the includes. That way, you avoid passing them around your methods.

  • Rather than returning all your vectors from readFromFile as output variables, and in order to shorten your type signature, return a struct instead in that function:

struct MassObjectsDescription {
  std::vector<int> weights;
  std::vector<int> startingOrder;
  std::vector<int> endingOrder;
  // Probably more fields here...
}

MassObjectsDescription readFromFile(int argc, char* argv[]) {
  // ...
}

You may want to move to classes in further iterations of your code.

  • No need to return 0 at the end of the main method.

  • Rather than reserving \$n\$ elements on vectors, instantiate them with the appropriate size as you have done in std::vector<int> permutation(n);.

  • int const &n. You may want to remove the reference to n as it is const, and there is no benefit (in fact, any) by passing the reference of such a little variable as an integer. Good job, though, doing it with vectors; it is a good practice doing so in order to avoid unnecessary copies.

  • Consider splitting your line result += into several lines with auxiliary variables. It is impossible guessing what's going on with such long line.

  • int x = i;. You first assign x to i, but suddenly it's got a value from permutation vector. Use i until changing its value and consider renaming the variable.

  • You are chaining if(z==0), if(z==1), if(z==2)... It is good practice to use else if or even switch statements. Plus, it would be a good idea creating a function that you may reuse to create vectors from istringstreams:

vector<int> readVector(std::istringstream& iss, int n) {
    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
        int d;
        iss >> d;
        v[i] = d - 1;
    }
    return v;
}
  • As a general rule, try to initialize variables as close to their first use. For instance, in your code you shouldn't be able to see the word vector in your main method; everything should be encapsulated on your methods.

  • Also, as a general rule, try to minimize the number of parameters of your functions. With the tips that I have given you above, probably you will end up having up to 3 or 4 parameters per function.

Hopefully somebody else can give you some advice about exceptions.

\$\endgroup\$
  • \$\begingroup\$ Thank you for your feedback and advices. Is it advisable to include whole <algorithm> only for one std::min()? >Rather than reserving n elements on vectors, instantiate them with the appropriate size as you have done in std::vector<int> permutation(n);. But how if i don't know the size before reading n from file? >Your line while (!visitedVertexes[x]) seems redundant and should be replaced by an if, as at most 1 iteration is performed. >int x = i; Well i could put here x=0, since i am iterating from 0, first index of any container. \$\endgroup\$ – Jan Dycz Aug 15 at 2:10
  • \$\begingroup\$ While loop is needed for traversal, you will move from vertex to vertex as long as there is a need for each cycle e.g1 2 3 4 5 ||||||| 4 3 2 1 5 It's 2 cycles 1->4 4->1 and 2->3 3->2 and third cycle already in place 5->5. So in best case scenario all objects are in same place, so you iterate i<n times and do nothing in while loop, because in this case permutation[5-1]=[5-1], so it's already pointing to itself and it will set visitedVertexes to true, so with iterator i, i ensure that i will visit every vertex/node, even when there is no jumping around. \$\endgroup\$ – Jan Dycz Aug 15 at 2:11
  • \$\begingroup\$ Otherwise you need to jump to next (unvisited) vertex and get values from there to swap masses in the cycle. \$\endgroup\$ – Jan Dycz Aug 15 at 2:11
  • \$\begingroup\$ "at most 1 iteration is performed" - no, don't miss x = permutation[x]; \$\endgroup\$ – vnp Aug 15 at 2:24
  • \$\begingroup\$ The define about min is not only not needed, it is UB. \$\endgroup\$ – L. F. Aug 15 at 7:02
7
\$\begingroup\$

I would just point out that the macro version of min is inferior.

#define min1(a,b) ((a) < (b) ? (a) : (b))
template<typename T>
inline min2(T const& a, T const& b) {return a < b ? a : b;}

Think of this situation.

min1(a1++, 5)  // how many times is a incremented?
min2(a1++, 5)
\$\endgroup\$
  • 1
    \$\begingroup\$ Pardon my ignorance, but what is UB? \$\endgroup\$ – JnxF Aug 15 at 10:58
  • 2
    \$\begingroup\$ @JnxF: Undefined Behaviour, which basically means the compiler is allowed to generate any code it wants to, including no code at all, code that formats your hard disk, or code that kills your kitten. \$\endgroup\$ – Guntram Blohm supports Monica Aug 15 at 11:37
  • 1
    \$\begingroup\$ @HolyBlackCat I am talking about the macro name min which may screw up the header. I wasn’t really thinking about order of evaluation :) \$\endgroup\$ – L. F. Aug 15 at 19:48
  • 1
    \$\begingroup\$ @HolyBlackCat Its still multiple updates in the same expression. So even if it is not UB its still going to give you nasty surprizes with multiple updates. \$\endgroup\$ – Martin York Aug 15 at 19:48
  • 1
    \$\begingroup\$ (See [macro.names]/1.) \$\endgroup\$ – L. F. Aug 15 at 20:13
4
\$\begingroup\$
  • Don’t use macros in place of functions (or function templates). Use standard functions where appropriate (i.e. std::min).
  • Include all necessary headers (<exception>, <stdexcept>).
  • Fix the compile errors in your code: std::exception has no constructor accepting a C string.
  • Separate concerns: each function should have a single responsibility. In particular, this means that readFromFile should not receive argc and argv. It probably also shouldn’t receive all the other arguments, and instead return the result (as an appropriately defined struct of vectors).
  • In C++, unlike in C, * and & in declarations go with the type, not with the variable name: int& n, not int &n.
  • Do not use RANDOM_CAPITALS in parameter names, regardless of whether the parameter is const.
  • Respect natural ordering: min_vertexes should come before max_vertexes.
  • Use guard clauses and early exit: Don’t indent the whole body of your function if the file successfully opened. Instead, check for failure and return/throw. Then continue without else.
  • But do not test whether the file was successfully opened, that’s useless. Instead, you must test whether each individual file reading operation was successful. You currently fail to do this.
  • I know people claim that this is a matter of opinion, but your bracing style is wasting a lot of vertical space: Your readFromFile function is 64 lines long. When putting the opening brace (and else) on the previous line, the function shrinks to 50 lines. 15% less. That’s a substantial reduction, and the whole function now fits on my screen. This is a drastic readability improvement.
  • Use consistent whitespace around operators. You mostly do this, but not everywhere.
  • Do not close the file explicitly unless you handle potential errors. The file will be closed automatically once the variable falls out of scope.
  • Use descriptive names. Single-letter variables in loops can be fine but z, a and d are cryptic names. i… as a loop variable is conventional.
  • Avoid magic constants. Why does the main loop go to 4? You seem to encode a state machine but the code doesn’t make this obvious.
  • Keep variable scope as close as possible (e.g. declare line inside the loop).
  • Use appropriate standard algorithms; for instance, to read n values in a loop, use std::copy_n with istream_iterators.
  • Don’t pass int (nor similar, small types) as const&, pass it by value.
  • I think the if (!visitedVertexes[x]) code is redundant and could be merged with the inner loop, but I currently don’t see how to do this well (= readably and efficiently). Still, consider whether this part of the algorithm can be restructured.
  • Don’t use C-style casts. In fact, the widening cast to long long here is unnecessary anyway.
  • Use local variables to break up excessively long expressions.
  • Use comments that describe why something is being done. The current comments don’t help me understand the code.
  • Use helper functions for repeated code, or when extracting code makes the logic more readable.
  • MAX_WEIGHT is unnecessary, and its value is completely arbitrary
  • Don’t swallow errors: your catch (...) means that all the informative error messages you had get lost.
  • In case of error, do not return 0 from main. You need to return an error code (usually 1).
  • Output error messages to STDERR, not STDOUT.

Which leaves us with something like this:

#include <algorithm>
#include <iostream>
#include <fstream>
#include <iterator>
#include <limits>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>

struct ObjectCollection {
    std::vector<int> weights;
    std::vector<int> startingOrder;
    std::vector<int> endingOrder;
    int minWeight;
};

std::vector<int> readOrder(std::istream& is, int const n) {
    std::vector<int> output;
    output.reserve(n);
    std::copy_n(std::istream_iterator<int>{is}, n, std::back_inserter(output));
    std::transform(begin(output), end(output), begin(output), [](int x) {return x - 1;});
    // FIXME: Optionally test for `is.fail()` here.
    return output;
}

ObjectCollection readFromFile(std::string const& filename, int const min_vertexes, int const max_vertexes) {
    std::ifstream file{filename};
    std::vector<int> weights;
    std::vector<int> startingOrder;
    std::vector<int> endingOrder;
    int n;

    for (int state = 0; state < 4; ++state) {
        std::string line;
        if (! std::getline(file, line)) throw std::logic_error{"Unable to read file"};
        // FIXME: This test is pretty useless: You filter empty input but not truncated input or too long input.
        if (line.empty()) throw std::logic_error{"Invalid input"};
        std::istringstream iss{line};

        if (state == 0) {
            if (! (iss >> n)) throw std::logic_error{"Failed to read n"};
            if (n < min_vertexes || n > max_vertexes) throw std::logic_error("Invalid amount of vertices");
        } else if (state == 1) {
            weights.reserve(n);
            std::copy_n(std::istream_iterator<int>{iss}, n, std::back_inserter(weights));
        } else if (state == 2) {
            startingOrder = readOrder(iss, n);
        } else {
            endingOrder = readOrder(iss, n);
        }
    }

    int const minWeight = *std::min_element(begin(weights), end(weights));
    return {weights, startingOrder, endingOrder, minWeight};
}

long long calculateLowestCostOfWork(ObjectCollection const& objects) {
    int const n = objects.weights.size();
    std::vector<int> permutation(n);

    // constructing permutation p
    for (int i = 0; i < n; ++i)
        permutation[objects.endingOrder[i]] = objects.startingOrder[i];

    long long result = 0;
    std::vector<bool> visitedVertexes(n);

    for (int i = 0; i < n; ++i) {
        int numberOfElementsInCycle = 0;
        int minWeightInCycle = std::numeric_limits<int>::max();
        long sumOfWeightsInCycle = 0;
        if (! visitedVertexes[i]) {
            int x = i; // FIXME: Use proper name for `x`.
            // decomposition for simple cycles and calculating parameters for each cycle
            while (! visitedVertexes[x]) {
                visitedVertexes[x] = true;
                ++numberOfElementsInCycle;
                x = permutation[x];
                sumOfWeightsInCycle += objects.weights[x];
                minWeightInCycle = std::min(minWeightInCycle, objects.weights[x]);
            }
            // calculating lowest cost for each cycle
            // FIXME: Use proper names.
            int const cycleCost = (numberOfElementsInCycle - 2) * minWeightInCycle;
            int const globalCost = minWeightInCycle + (numberOfElementsInCycle + 1) * objects.minWeight;
            result += sumOfWeightsInCycle + std::min(cycleCost, globalCost);
        }
    }
    return result;
}

int main(int argc, char *argv[]) {
    if (argc != 2) {
        std::cerr << "Error: missing filename\n";
        return 1;
    }
    int const MIN_VERTEXES = 2;
    int const MAX_VERTEXES = 1000000;
    try {
        auto objects = readFromFile(argv[1], MIN_VERTEXES, MAX_VERTEXES);
        std::cout << calculateLowestCostOfWork(objects);
    } catch (std::exception const& ex) {
        std::cerr << "Error: " << ex.what() << "\n";
        return 1;
    }
}

(Untested, since I have no test data and don’t know what the algorithm is supposed to do.)

As mentioned elsewhere, the reserve-and-push_back pattern could be replaced by resizing the objects and then just copying directly. This means that you’d be performing redundant zero-initialisation, but on the other hand you’d avoid an out-of-bounds test inside the push_back. You need to benchmark to find out which of these variants is faster. However, this is unlikely to be a bottleneck in your code. Don’t sweat the small stuff.

\$\endgroup\$
  • \$\begingroup\$ I've rebuilded a code, according to your advices. Thank you for your feedback. \$\endgroup\$ – Jan Dycz Aug 16 at 4:32
4
\$\begingroup\$

Design

You biggest problem is encapsulation.
You treat your three different properties as three different data items rather than as a single data item. I feel it would be more logical to combine the data into a single item.

I suppose you did it this way because of the design of the input file. If given the chance I would change the format of this file. Define the properties of each item (start, end, weight) all on the same line. But even if you can't change the format I would still try and encapsulate the data into a single item.

Error

If the input file is mis-formed then you probably will not detect it and simply fill the input arrays with garbage values.

Code Review

Please no:

#define min(a,b) ((a) < (b) ? (a) : (b))

There is no reason to use macros (apart from the one thing they are good at which is conditional compilation of code, preferably to take into account different system implementations).

Looks like MAX_VERTEXES and MIN_VERTEXES and MAX_WIGHT should simply be global static state, rather than passed around the application. Note global variables are OK iff they are constant (ie non mutable).

int constexpr MaxVertexes = 1000000;
int constexpr MinVertexes = 2;
int constexpr MaxWeight   = 6500;

The other thing you should note is that all capitol identifiers are traditionally reserved for macros. Using them as variable names is iffy at best going to cause issues at worst. Please make sure all non macros use standard variable names.

If things are non mutable then mark them with const or constexpr to indicate that they are non mutable. This will make sure the compiler tells you about an error if you accidentally change their value.

I would throw exception if the file name is not passed or the file did not open. Opps having read it threw now I see you do throw on open. I would change the order though so all the throwing is at the top. Then your code is all at the same indent level.

    std::ifstream file;
    if (argc >= 2)
    {
        file.open(argv[1]);
    }
    else
    {
        throw std::exception("No parameter passed");
    }
    std::string line;

    if (file.is_open())
    {

Your code is of the form:

    if (isGood()) {
         doGoodStuff();
    }
    else {
         throw error;
    }

Putting all your error tests at the top puts all your explicit checking and error handling at the top.

    // Check pre-conditions.
    if (!isGood()) {
         throw error;
    }

    // All your pre-conditions have been checked.
    doGoodStuff();

So your code above I would have written like this:

    std::ifstream file;
    if (argc < 2)
    {
        throw std::exception("No parameter passed");
    }

    // Initialize and open in one go.
    std::ifstream file(argv[1]);

    if (!file)   // don't specifically check for a good state
    {            // there are several bad states so check to see if the file
                 // is not bad.
        throw std::exception("Unable to open file");
    }

    // Now spend time reading the file.

Exceptions. The std::exception is the base class and has several derived types for different situations. In pre C++11 this class did not even take a string in the constructor so you could not use it like this:

std::exception("No parameter passed");

I would choose the more generic std::runtime_error. You will need to include <stdexcept> to get the definition.

OK this loop is absolutely not needed.

        for (int z = 0; z < 4; z++)

In the code you basically go:

        for (int z = 0; z < 4; z++) {
            if (z == 0) {taskOne();}
            if (z == 1) {taskTwo();}
            if (z == 2) {taskThree();}
            if (z == 3) {taskFour();}
        }

This whole construct can simply be replaced with:

       taskOne();
       taskTwo();
       taskThree();
       taskFour();

In the next section you never check that any read operation worked. Any stream operation should be checked to make sure it worked.

        iss >> n;

Did that actually read the value? Or is n left in its original state (thus causing you to add the last value read repeatedly). If you have a one off error then this kind of thing results in the last value being placed into the data twice (common issue).

                startingOrder.reserve(n);
                for (int a = 0; a < n; a++)
                {
                    int d;
                    iss >> d;
                    startingOrder.push_back(d - 1);
                }

I would so something more like this:

                startingOrder.reserve(n);
                while(iss >> d) {
                    startingOrder.push_back(d - 1);
                }
                if (startingOrder.size() != n) {
                    throw std::runtime_exception("Malformed input file .... some text");
                }

Technically you don't even need a loop you can simply use istream iterators to initiate an array. But while learning I would use the loop form and graduate to this form once you have started understanding more of the standard library.

                // How to create an array from stream iterators.
                startingOrder = std::vector<int>(std::istream_iterator<int>{iss},
                                                 std::istream_iterator<int>{});

Don't see the point in this.

        file.close();

I would just let the destructor do its job and close the file.

This function header is not const correct.

long long calculateLowestCostOfWork(int const &n, int const &MAX_WEIGHT, int const &minWeightGlobally, std::vector<int>& weights, std::vector<int>& startingOrder, std::vector<int>& endingOrder)

You pass several parameters by reference that are non-mutable (all the input arrays).

This is a bad habit (not using the curly braces).

    for (int i = 0; i < n; i++)
        permutation[endingOrder[i]] = startingOrder[i];

When you don't put braces only the one next statement is part of the loop. The trouble is that it is not always obvious that there are two (or more) statements and thus you could have some hard to find errors.

    // Not immediately obvious example. But still not 100% easy to spot.
    // But a lot of code reviewers can still easily miss this.
    for (int i = 0; i < n; i++)
        permutation[endingOrder[i]] = startingOrder[i];
        plop[i] = pile[i];

    // This kind of thing has happened to me
    #define UpdatePerm(permutation, endingOrder, startingOrder, plop, pile, i) \
        permutation[endingOrder[i]] = startingOrder[i]; \
        plop[i] = pile[i]

    // ... Lots of other code.

    for (int i = 0; i < n; i++)
        UpdatePerm(permutation, endingOrder, startingOrder, plop, pile, i);

Moral of the story always put the braces on and you will never be wrong.

     for (int i = 0; i < n; i++) {
        UpdatePerm(permutation, endingOrder, startingOrder, plop, pile, i);
     }

     // In your case:
     for (int i = 0; i < n; i++) {
        permutation[endingOrder[i]] = startingOrder[i];
     }

Only putting the try around one function seems strange.

try
{
    readFromFile(argc, argv,MAX_VERTEXES, MIN_VERTEXES, n, minWeightGlobally, weights, startingOrder, endingOrder);
}
catch (...)
{
    std::cout << "Error";
}

std::cout << calculateLowestCostOfWork(n,MAX_WEIGHT,minWeightGlobally,weights,startingOrder,endingOrder);

In the main I would have all the code inside the try block. So that any future errors would be caught by the try (people change code and don't always check were the code is use). But in addition to just printing error I would print the message as well. Then I would re-throw the exception so that the external operating system knows there was an error.

try
{
    // All real code that is not simply initializing constants.

    readFromFile(argc, argv,MAX_VERTEXES, MIN_VERTEXES, n, minWeightGlobally, weights, startingOrder, endingOrder);
    int result = calculateLowestCostOfWork(n,MAX_WEIGHT,minWeightGlobally,weights,startingOrder,endingOrder);
    std::cout << result << "\n";
}
catch (std::exception const& e) {
    std::cerr << "Error: " << e.what() << "\n";
    throw;
}
catch (...) {
    std::cerr << "Error: Unknown?\n";
    throw;
}

One variable per line please.

std::vector<int> weights, startingOrder, endingOrder;

This is simply horrible to read and make sure you got correct.

Let us have meaningful names.

int n=0;

I did a search of the code for the variable n to see where it is used. Do you know how many times n is in the code. Use meaningful names so it becomes easy to search and see the variables. Its not used by the way.

\$\endgroup\$
  • \$\begingroup\$ int n is a good name for a loop limit (in my view) - and i is an excellent name for a loop counter. A meaningful name doesn't have to be long. \$\endgroup\$ – Martin Bonner supports Monica Aug 15 at 15:44
  • \$\begingroup\$ @MartinBonner Well I will argue that you are wrong. And not just wrong but data provably wrong. As I mentioned above. Open up the file above in an editor and search for the variable n. How many characters are highlighted? From the beginning of main() how many times do I have to hit next to reach the declaration of n? 8 times. And its only usage is at 11 times? and its exceedingly hard to spot the usage without tabbing through to the point of usage as n is in both identifiers and keywords. \$\endgroup\$ – Martin York Aug 15 at 19:46
  • 1
    \$\begingroup\$ @MartinYork While I agree with you on n being less than ideal, any decent editor should be able to search on word boundaries. In Vim, this can be done with the \< and \> patterns or using the * or # keyword search. In GUI-based editors, there's usually a checkbox for "match whole word only" or something similar. The i loop counter is fine just because it's a standard practice, though raw loops are best avoided when possible, and iterator-based ("foreach") loops are preferable when raw loops are necessary. \$\endgroup\$ – Bloodgain Aug 15 at 21:35
  • \$\begingroup\$ @Bloodgain Yes I agree there are workarounds. But you are added cognative load for the maintainer when there is no need to do this. It is not hard to add meaningful names so best practice is to make identifiers meaningful. Even loop variables can be made more useful and reduce the cognitive burden of the maintainer. \$\endgroup\$ – Martin York Aug 16 at 0:08
  • \$\begingroup\$ I've rebuilded a code, according to your advices. Thank you for your feedback. \$\endgroup\$ – Jan Dycz Aug 16 at 4:32
0
\$\begingroup\$

I've tried my best and updated my code according to your valuable feedback, please have a look. What i am failing to do is to check whether there is a whitespace after numbers so the input 1 2 3 4whitespaces is not correct.

    #include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>
int constexpr MaxWeight = 6500, MinVertexes = 2, MaxVertexes = 1000000;

struct ObjectCollection 
{
    int amountOfObjects = 0;
    std::vector<int> weights;
    std::vector<int> startingOrder;
    std::vector<int> endingOrder;
    int minWeight = MaxWeight;
};

std::vector<int> readOrder(std::istringstream& iss, int const amountOfObjects) 
{
    std::vector<int> v;
    v.reserve(amountOfObjects);
    int i = 1;
    while(!iss.eof() && i <= amountOfObjects)
    {
        int number;
        iss >> number;
        if (number - 1 > amountOfObjects) throw std::logic_error("Too high index in order");
        v.push_back(number-1);
        i++;
    }
    if (v.size() != amountOfObjects) throw std::logic_error("Too few values in line");
    return v;
}

void readWeightsAndSetMinWeight(std::istringstream& iss, ObjectCollection& objects)
{
    objects.weights.reserve(objects.amountOfObjects);
    int i = 1;
    while (!iss.eof() && i <= objects.amountOfObjects)
    {
        int number;
        iss >> number;
        if (number> MaxWeight) throw std::logic_error("Too high weight");
        objects.weights.push_back(number);
        objects.minWeight = std::min(objects.minWeight, number);
        i++;
    }
    if (objects.weights.size() != objects.amountOfObjects) throw std::logic_error("Too few values in line");
}

//todo version for weight

ObjectCollection readFromFile(std::string const& filename)
{
    ObjectCollection objects;
    std::ifstream file(filename);

    if (!file.is_open()) throw std::exception("Unable to open file");

    for (int i = 0; i < 4; i++)
    {
        std::string line;
        std::getline(file, line);
        if (line.empty()) throw std::logic_error("Invalid input");
        std::istringstream iss(line);

        if (i == 0)
        {
            iss >> objects.amountOfObjects;
            if (objects.amountOfObjects<MinVertexes || objects.amountOfObjects>MaxVertexes) throw std::exception("Invalid amount of vertexes");
        }
        else if (i == 1)
        {
            objects.weights.reserve(objects.amountOfObjects);
            for (int j = 0; j < objects.amountOfObjects; j++)
            {
                //int number;
                //iss >> number;
                //objects.weights.push_back(number);
                //objects.minWeight = std::min(objects.minWeight, objects.weights[j]);
                readWeightsAndSetMinWeight(iss, objects);
            }
        }
        else if (i == 2)
        {
            objects.startingOrder = readOrder(iss,objects.amountOfObjects);
        }
        else if (i == 3)
        {
            objects.endingOrder = readOrder(iss, objects.amountOfObjects);
        }
    }
    return objects;
}

long long calculateLowestCostOfWork(ObjectCollection const& objects)
{
    int n = objects.amountOfObjects;
    std::vector<int> permutation(n);

    //constructing permutation
    for (int i = 0; i < n; i++) 
    {
        permutation[objects.endingOrder[i]] = objects.startingOrder[i];
    }

    long long result = 0;
    std::vector<bool> visitedVertexes(n);

    for (int i = 0; i < n; i++)
    {
        int numberOfElementsInCycle = 0;
        int minWeightInCycle = MaxWeight;
        long long sumOfWeightsInCycle = 0;
        if (!visitedVertexes[i])
        {
            int vertexToVisit = i;
            //decomposition for simple cycles and calculating parameters for each cycle
            while (!visitedVertexes[vertexToVisit])
            {
                visitedVertexes[vertexToVisit] = true;
                numberOfElementsInCycle++;
                vertexToVisit = permutation[vertexToVisit];
                sumOfWeightsInCycle += objects.weights[vertexToVisit];
                minWeightInCycle = std::min(minWeightInCycle, objects.weights[vertexToVisit]);
            }
            //calculating lowest cost for each cycle
            long long swappingWithMinWeightInCycle = sumOfWeightsInCycle + (static_cast<long long>(numberOfElementsInCycle) - 2) * static_cast<long long>(minWeightInCycle);
            long long swappingWithMinWeight =  sumOfWeightsInCycle + minWeightInCycle + (static_cast<long long>(numberOfElementsInCycle) + 1) * static_cast<long long>(objects.minWeight);
            result += std::min(swappingWithMinWeightInCycle, swappingWithMinWeight);
        }
    }
    return result;
}

int main(int argc, char* argv[])
{
    if (argc < 2)
    {
        std::cerr << "Error: missing filename\n";
        return 1;
    }

    ObjectCollection elephants;
    try
    {
        elephants = readFromFile(argv[1]);
        std::cout << calculateLowestCostOfWork(elephants);
    }
    catch (std::exception const& ex) 
    {
        std::cerr << "Error: " << ex.what() << "\n";
        return 1;
    }
    catch (...)
    {
        std::cerr << "Error unknown \n";
        return 1;
    }
    return 0;
}
\$\endgroup\$

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.