Least cost swapping in C++Array kept contiguous by swapping with the last elementGas cost calculatorArrange...

Typesetting "hollow slash"

What is the fastest way to level past 95 in Diablo II?

String routines

What's the point of writing that I know will never be used or read?

Why do so many people play out of turn on the last lead?

Is Fourier series a sampled version of Fourier transform?

Did Michelle Obama have a staff of 23; and Melania have a staff of 4?

Would getting a natural 20 with a penalty still count as a critical hit?

When did Bilbo and Frodo learn that Gandalf was a Maia?

If a person claims to know anything could it be disproven by saying 'prove that we are not in a simulation'?

Meaning of だけはわからない

Are there any cons in using rounded corners for bar graphs?

Why does Japan use the same type of AC power outlet as the US?

Expressing a chain of boolean ORs using ILP

Why do we use low resistance cables to minimize power losses?

How to prevent criminal gangs from making/buying guns?

What is the purpose/function of this power inductor in parallel?

Physical Interpretation of an Overdamped Pendulum

How to gracefully leave a company you helped start?

What allows us to use imaginary numbers?

How do I answer an interview question about how to handle a hard deadline I won't be able to meet?

Eric Andre had a dream

Why won't the Republicans use a superdelegate system like the DNC in their nomination process?

I was dismissed as a candidate for an abroad company after disclosing my disability



Least cost swapping in C++


Array kept contiguous by swapping with the last elementGas cost calculatorArrange three integers from least to greatestCalculate total cost of items, based on bulk discountFinding the max cost from the minimum cost incurred on travellingMySQL Query to check at least one field is greater than zeroDecimal Quantities needed to meet costOpen/Closed Principle with calculating the total cost of items in a shopping cartFilling a string at minimal cost






.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ margin-bottom:0;
}







3












$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.










share|improve this question









New contributor



Jan Dycz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






$endgroup$














  • $begingroup$
    Hello. I am new to C++.Could you explain what long long functionName does ?
    $endgroup$
    – Manos Kounelakis
    23 hours ago










  • $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
    23 hours ago










  • $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
    15 hours ago












  • $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
    15 hours ago












  • $begingroup$
    @JanDycz no I was asking about the function signature long long functionName. I haven't seen something similar.
    $endgroup$
    – Manos Kounelakis
    14 hours ago


















3












$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.










share|improve this question









New contributor



Jan Dycz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






$endgroup$














  • $begingroup$
    Hello. I am new to C++.Could you explain what long long functionName does ?
    $endgroup$
    – Manos Kounelakis
    23 hours ago










  • $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
    23 hours ago










  • $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
    15 hours ago












  • $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
    15 hours ago












  • $begingroup$
    @JanDycz no I was asking about the function signature long long functionName. I haven't seen something similar.
    $endgroup$
    – Manos Kounelakis
    14 hours ago














3












3








3





$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.










share|improve this question









New contributor



Jan Dycz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






$endgroup$




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.







c++ comparative-review






share|improve this question









New contributor



Jan Dycz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.










share|improve this question









New contributor



Jan Dycz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.








share|improve this question




share|improve this question








edited 23 hours ago









Mast

7,9147 gold badges38 silver badges92 bronze badges




7,9147 gold badges38 silver badges92 bronze badges






New contributor



Jan Dycz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.








asked 2 days ago









Jan DyczJan Dycz

165 bronze badges




165 bronze badges




New contributor



Jan Dycz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.




New contributor




Jan Dycz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

















  • $begingroup$
    Hello. I am new to C++.Could you explain what long long functionName does ?
    $endgroup$
    – Manos Kounelakis
    23 hours ago










  • $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
    23 hours ago










  • $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
    15 hours ago












  • $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
    15 hours ago












  • $begingroup$
    @JanDycz no I was asking about the function signature long long functionName. I haven't seen something similar.
    $endgroup$
    – Manos Kounelakis
    14 hours ago


















  • $begingroup$
    Hello. I am new to C++.Could you explain what long long functionName does ?
    $endgroup$
    – Manos Kounelakis
    23 hours ago










  • $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
    23 hours ago










  • $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
    15 hours ago












  • $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
    15 hours ago












  • $begingroup$
    @JanDycz no I was asking about the function signature long long functionName. I haven't seen something similar.
    $endgroup$
    – Manos Kounelakis
    14 hours ago
















$begingroup$
Hello. I am new to C++.Could you explain what long long functionName does ?
$endgroup$
– Manos Kounelakis
23 hours ago




$begingroup$
Hello. I am new to C++.Could you explain what long long functionName does ?
$endgroup$
– Manos Kounelakis
23 hours ago












$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
23 hours ago




$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
23 hours ago












$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
15 hours ago






$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
15 hours ago














$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
15 hours ago






$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
15 hours ago














$begingroup$
@JanDycz no I was asking about the function signature long long functionName. I haven't seen something similar.
$endgroup$
– Manos Kounelakis
14 hours ago




$begingroup$
@JanDycz no I was asking about the function signature long long functionName. I haven't seen something similar.
$endgroup$
– Manos Kounelakis
14 hours ago










5 Answers
5






active

oldest

votes


















7












$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.






share|improve this answer











$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
    2 days ago










  • $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
    2 days ago












  • $begingroup$
    Otherwise you need to jump to next (unvisited) vertex and get values from there to swap masses in the cycle.
    $endgroup$
    – Jan Dycz
    2 days ago












  • $begingroup$
    "at most 1 iteration is performed" - no, don't miss x = permutation[x];
    $endgroup$
    – vnp
    2 days ago










  • $begingroup$
    The define about min is not only not needed, it is UB.
    $endgroup$
    – L. F.
    yesterday



















6












$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)





share|improve this answer









$endgroup$











  • 1




    $begingroup$
    Pardon my ignorance, but what is UB?
    $endgroup$
    – JnxF
    yesterday






  • 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
    yesterday








  • 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.
    yesterday








  • 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
    yesterday






  • 1




    $begingroup$
    (See [macro.names]/1.)
    $endgroup$
    – L. F.
    yesterday



















3












$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.






share|improve this answer











$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
    yesterday










  • $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
    yesterday






  • 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
    yesterday












  • $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
    yesterday










  • $begingroup$
    I've rebuilded a code, according to your advices. Thank you for your feedback.
    $endgroup$
    – Jan Dycz
    yesterday



















2












$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 filenamen";
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.






share|improve this answer











$endgroup$















  • $begingroup$
    I've rebuilded a code, according to your advices. Thank you for your feedback.
    $endgroup$
    – Jan Dycz
    yesterday



















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 filenamen";
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;
}





share|improve this answer








New contributor



Jan Dycz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





$endgroup$


















    Your Answer






    StackExchange.ifUsing("editor", function () {
    StackExchange.using("externalEditor", function () {
    StackExchange.using("snippets", function () {
    StackExchange.snippets.init();
    });
    });
    }, "code-snippets");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "196"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: false,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: null,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });






    Jan Dycz is a new contributor. Be nice, and check out our Code of Conduct.










    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f226145%2fleast-cost-swapping-in-c%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    5 Answers
    5






    active

    oldest

    votes








    5 Answers
    5






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    7












    $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.






    share|improve this answer











    $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
      2 days ago










    • $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
      2 days ago












    • $begingroup$
      Otherwise you need to jump to next (unvisited) vertex and get values from there to swap masses in the cycle.
      $endgroup$
      – Jan Dycz
      2 days ago












    • $begingroup$
      "at most 1 iteration is performed" - no, don't miss x = permutation[x];
      $endgroup$
      – vnp
      2 days ago










    • $begingroup$
      The define about min is not only not needed, it is UB.
      $endgroup$
      – L. F.
      yesterday
















    7












    $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.






    share|improve this answer











    $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
      2 days ago










    • $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
      2 days ago












    • $begingroup$
      Otherwise you need to jump to next (unvisited) vertex and get values from there to swap masses in the cycle.
      $endgroup$
      – Jan Dycz
      2 days ago












    • $begingroup$
      "at most 1 iteration is performed" - no, don't miss x = permutation[x];
      $endgroup$
      – vnp
      2 days ago










    • $begingroup$
      The define about min is not only not needed, it is UB.
      $endgroup$
      – L. F.
      yesterday














    7












    7








    7





    $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.






    share|improve this answer











    $endgroup$



    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.







    share|improve this answer














    share|improve this answer



    share|improve this answer








    edited yesterday

























    answered 2 days ago









    JnxFJnxF

    3203 silver badges13 bronze badges




    3203 silver badges13 bronze badges















    • $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
      2 days ago










    • $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
      2 days ago












    • $begingroup$
      Otherwise you need to jump to next (unvisited) vertex and get values from there to swap masses in the cycle.
      $endgroup$
      – Jan Dycz
      2 days ago












    • $begingroup$
      "at most 1 iteration is performed" - no, don't miss x = permutation[x];
      $endgroup$
      – vnp
      2 days ago










    • $begingroup$
      The define about min is not only not needed, it is UB.
      $endgroup$
      – L. F.
      yesterday


















    • $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
      2 days ago










    • $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
      2 days ago












    • $begingroup$
      Otherwise you need to jump to next (unvisited) vertex and get values from there to swap masses in the cycle.
      $endgroup$
      – Jan Dycz
      2 days ago












    • $begingroup$
      "at most 1 iteration is performed" - no, don't miss x = permutation[x];
      $endgroup$
      – vnp
      2 days ago










    • $begingroup$
      The define about min is not only not needed, it is UB.
      $endgroup$
      – L. F.
      yesterday
















    $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
    2 days ago




    $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
    2 days ago












    $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
    2 days ago






    $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
    2 days ago














    $begingroup$
    Otherwise you need to jump to next (unvisited) vertex and get values from there to swap masses in the cycle.
    $endgroup$
    – Jan Dycz
    2 days ago






    $begingroup$
    Otherwise you need to jump to next (unvisited) vertex and get values from there to swap masses in the cycle.
    $endgroup$
    – Jan Dycz
    2 days ago














    $begingroup$
    "at most 1 iteration is performed" - no, don't miss x = permutation[x];
    $endgroup$
    – vnp
    2 days ago




    $begingroup$
    "at most 1 iteration is performed" - no, don't miss x = permutation[x];
    $endgroup$
    – vnp
    2 days ago












    $begingroup$
    The define about min is not only not needed, it is UB.
    $endgroup$
    – L. F.
    yesterday




    $begingroup$
    The define about min is not only not needed, it is UB.
    $endgroup$
    – L. F.
    yesterday













    6












    $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)





    share|improve this answer









    $endgroup$











    • 1




      $begingroup$
      Pardon my ignorance, but what is UB?
      $endgroup$
      – JnxF
      yesterday






    • 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
      yesterday








    • 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.
      yesterday








    • 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
      yesterday






    • 1




      $begingroup$
      (See [macro.names]/1.)
      $endgroup$
      – L. F.
      yesterday
















    6












    $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)





    share|improve this answer









    $endgroup$











    • 1




      $begingroup$
      Pardon my ignorance, but what is UB?
      $endgroup$
      – JnxF
      yesterday






    • 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
      yesterday








    • 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.
      yesterday








    • 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
      yesterday






    • 1




      $begingroup$
      (See [macro.names]/1.)
      $endgroup$
      – L. F.
      yesterday














    6












    6








    6





    $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)





    share|improve this answer









    $endgroup$



    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)






    share|improve this answer












    share|improve this answer



    share|improve this answer










    answered yesterday









    Martin YorkMartin York

    76.6k4 gold badges92 silver badges285 bronze badges




    76.6k4 gold badges92 silver badges285 bronze badges











    • 1




      $begingroup$
      Pardon my ignorance, but what is UB?
      $endgroup$
      – JnxF
      yesterday






    • 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
      yesterday








    • 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.
      yesterday








    • 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
      yesterday






    • 1




      $begingroup$
      (See [macro.names]/1.)
      $endgroup$
      – L. F.
      yesterday














    • 1




      $begingroup$
      Pardon my ignorance, but what is UB?
      $endgroup$
      – JnxF
      yesterday






    • 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
      yesterday








    • 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.
      yesterday








    • 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
      yesterday






    • 1




      $begingroup$
      (See [macro.names]/1.)
      $endgroup$
      – L. F.
      yesterday








    1




    1




    $begingroup$
    Pardon my ignorance, but what is UB?
    $endgroup$
    – JnxF
    yesterday




    $begingroup$
    Pardon my ignorance, but what is UB?
    $endgroup$
    – JnxF
    yesterday




    2




    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
    yesterday






    $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
    yesterday






    1




    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.
    yesterday






    $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.
    yesterday






    1




    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
    yesterday




    $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
    yesterday




    1




    1




    $begingroup$
    (See [macro.names]/1.)
    $endgroup$
    – L. F.
    yesterday




    $begingroup$
    (See [macro.names]/1.)
    $endgroup$
    – L. F.
    yesterday











    3












    $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.






    share|improve this answer











    $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
      yesterday










    • $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
      yesterday






    • 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
      yesterday












    • $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
      yesterday










    • $begingroup$
      I've rebuilded a code, according to your advices. Thank you for your feedback.
      $endgroup$
      – Jan Dycz
      yesterday
















    3












    $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.






    share|improve this answer











    $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
      yesterday










    • $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
      yesterday






    • 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
      yesterday












    • $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
      yesterday










    • $begingroup$
      I've rebuilded a code, according to your advices. Thank you for your feedback.
      $endgroup$
      – Jan Dycz
      yesterday














    3












    3








    3





    $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.






    share|improve this answer











    $endgroup$



    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.







    share|improve this answer














    share|improve this answer



    share|improve this answer








    edited 23 hours ago









    Mast

    7,9147 gold badges38 silver badges92 bronze badges




    7,9147 gold badges38 silver badges92 bronze badges










    answered yesterday









    Martin YorkMartin York

    76.6k4 gold badges92 silver badges285 bronze badges




    76.6k4 gold badges92 silver badges285 bronze badges















    • $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
      yesterday










    • $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
      yesterday






    • 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
      yesterday












    • $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
      yesterday










    • $begingroup$
      I've rebuilded a code, according to your advices. Thank you for your feedback.
      $endgroup$
      – Jan Dycz
      yesterday


















    • $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
      yesterday










    • $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
      yesterday






    • 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
      yesterday












    • $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
      yesterday










    • $begingroup$
      I've rebuilded a code, according to your advices. Thank you for your feedback.
      $endgroup$
      – Jan Dycz
      yesterday
















    $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
    yesterday




    $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
    yesterday












    $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
    yesterday




    $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
    yesterday




    1




    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
    yesterday






    $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
    yesterday














    $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
    yesterday




    $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
    yesterday












    $begingroup$
    I've rebuilded a code, according to your advices. Thank you for your feedback.
    $endgroup$
    – Jan Dycz
    yesterday




    $begingroup$
    I've rebuilded a code, according to your advices. Thank you for your feedback.
    $endgroup$
    – Jan Dycz
    yesterday











    2












    $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 filenamen";
    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.






    share|improve this answer











    $endgroup$















    • $begingroup$
      I've rebuilded a code, according to your advices. Thank you for your feedback.
      $endgroup$
      – Jan Dycz
      yesterday
















    2












    $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 filenamen";
    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.






    share|improve this answer











    $endgroup$















    • $begingroup$
      I've rebuilded a code, according to your advices. Thank you for your feedback.
      $endgroup$
      – Jan Dycz
      yesterday














    2












    2








    2





    $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 filenamen";
    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.






    share|improve this answer











    $endgroup$




    • 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 filenamen";
    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.







    share|improve this answer














    share|improve this answer



    share|improve this answer








    edited yesterday

























    answered yesterday









    Konrad RudolphKonrad Rudolph

    5,15816 silver badges32 bronze badges




    5,15816 silver badges32 bronze badges















    • $begingroup$
      I've rebuilded a code, according to your advices. Thank you for your feedback.
      $endgroup$
      – Jan Dycz
      yesterday


















    • $begingroup$
      I've rebuilded a code, according to your advices. Thank you for your feedback.
      $endgroup$
      – Jan Dycz
      yesterday
















    $begingroup$
    I've rebuilded a code, according to your advices. Thank you for your feedback.
    $endgroup$
    – Jan Dycz
    yesterday




    $begingroup$
    I've rebuilded a code, according to your advices. Thank you for your feedback.
    $endgroup$
    – Jan Dycz
    yesterday











    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 filenamen";
    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;
    }





    share|improve this answer








    New contributor



    Jan Dycz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.





    $endgroup$




















      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 filenamen";
      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;
      }





      share|improve this answer








      New contributor



      Jan Dycz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.





      $endgroup$


















        0












        0








        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 filenamen";
        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;
        }





        share|improve this answer








        New contributor



        Jan Dycz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.





        $endgroup$



        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 filenamen";
        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;
        }






        share|improve this answer








        New contributor



        Jan Dycz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.








        share|improve this answer



        share|improve this answer






        New contributor



        Jan Dycz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.








        answered 15 hours ago









        Jan DyczJan Dycz

        165 bronze badges




        165 bronze badges




        New contributor



        Jan Dycz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.




        New contributor




        Jan Dycz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.



























            Jan Dycz is a new contributor. Be nice, and check out our Code of Conduct.










            draft saved

            draft discarded


















            Jan Dycz is a new contributor. Be nice, and check out our Code of Conduct.













            Jan Dycz is a new contributor. Be nice, and check out our Code of Conduct.












            Jan Dycz is a new contributor. Be nice, and check out our Code of Conduct.
















            Thanks for contributing an answer to Code Review Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f226145%2fleast-cost-swapping-in-c%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            Taj Mahal Inhaltsverzeichnis Aufbau | Geschichte | 350-Jahr-Feier | Heutige Bedeutung | Siehe auch |...

            Baia Sprie Cuprins Etimologie | Istorie | Demografie | Politică și administrație | Arii naturale...

            Nicolae Petrescu-Găină Cuprins Biografie | Opera | In memoriam | Varia | Controverse, incertitudini...