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;
}
$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.
c++ comparative-review
New contributor
$endgroup$
|
show 1 more comment
$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.
c++ comparative-review
New contributor
$endgroup$
$begingroup$
Hello. I am new to C++.Could you explain whatlong 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 signaturelong long functionName
. I haven't seen something similar.
$endgroup$
– Manos Kounelakis
14 hours ago
|
show 1 more comment
$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.
c++ comparative-review
New contributor
$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
c++ comparative-review
New contributor
New contributor
edited 23 hours ago
Mast
7,9147 gold badges38 silver badges92 bronze badges
7,9147 gold badges38 silver badges92 bronze badges
New contributor
asked 2 days ago
Jan DyczJan Dycz
165 bronze badges
165 bronze badges
New contributor
New contributor
$begingroup$
Hello. I am new to C++.Could you explain whatlong 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 signaturelong long functionName
. I haven't seen something similar.
$endgroup$
– Manos Kounelakis
14 hours ago
|
show 1 more comment
$begingroup$
Hello. I am new to C++.Could you explain whatlong 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 signaturelong 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
|
show 1 more comment
5 Answers
5
active
oldest
votes
$begingroup$
Some minor comments:
No need to define
min
. Just#include <algorithm>
and usestd::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 ton
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 assignx
toi
, but suddenly it's got a value frompermutation
vector. Usei
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 useelse if
or even switch statements. Plus, it would be a good idea creating a function that you may reuse to create vectors from istringstreams:
vector<int> readVector(std::istringstream& iss, int n) {
vector<int> v(n);
for (int i = 0; i < n; ++i) {
int d;
iss >> d;
v[i] = d - 1;
}
return v;
}
As a general rule, try to initialize variables as close to their first use. For instance, in your code you shouldn't be able to see the word vector in your main method; everything should be encapsulated on your methods.
Also, as a general rule, try to minimize the number of parameters of your functions. With the tips that I have given you above, probably you will end up having up to 3 or 4 parameters per function.
Hopefully somebody else can give you some advice about exceptions.
$endgroup$
$begingroup$
Thank you for your feedback and advices. Is it advisable to include whole <algorithm> only for one std::min()? >Rather than reserving n elements on vectors, instantiate them with the appropriate size as you have done in std::vector<int> permutation(n);. But how if i don't know the size before reading n from file? >Your line while (!visitedVertexes[x]) seems redundant and should be replaced by an if, as at most 1 iteration is performed. >int x = i; Well i could put here x=0, since i am iterating from 0, first index of any container.
$endgroup$
– Jan Dycz
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 missx = permutation[x];
$endgroup$
– vnp
2 days ago
$begingroup$
The define about min is not only not needed, it is UB.
$endgroup$
– L. F.
yesterday
|
show 9 more comments
$begingroup$
I would just point out that the macro version of min is inferior.
#define min1(a,b) ((a) < (b) ? (a) : (b))
template<typename T>
inline min2(T const& a, T const& b) {return a < b ? a : b;}
Think of this situation.
min1(a1++, 5) // how many times is a incremented?
min2(a1++, 5)
$endgroup$
1
$begingroup$
Pardon my ignorance, but what is UB?
$endgroup$
– JnxF
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 namemin
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
|
show 4 more comments
$begingroup$
Design
You biggest problem is encapsulation.
You treat your three different properties as three different data items rather than as a single data item. I feel it would be more logical to combine the data into a single item.
I suppose you did it this way because of the design of the input file. If given the chance I would change the format of this file. Define the properties of each item (start, end, weight) all on the same line. But even if you can't change the format I would still try and encapsulate the data into a single item.
Error
If the input file is mis-formed then you probably will not detect it and simply fill the input arrays with garbage values.
Code Review
Please no:
#define min(a,b) ((a) < (b) ? (a) : (b))
There is no reason to use macros (apart from the one thing they are good at which is conditional compilation of code, preferably to take into account different system implementations).
Looks like MAX_VERTEXES
and MIN_VERTEXES
and MAX_WIGHT
should simply be global static state, rather than passed around the application. Note global variables are OK iff they are constant (ie non mutable).
int constexpr MaxVertexes = 1000000;
int constexpr MinVertexes = 2;
int constexpr MaxWeight = 6500;
The other thing you should note is that all capitol identifiers are traditionally reserved for macros. Using them as variable names is iffy at best going to cause issues at worst. Please make sure all non macros use standard variable names.
If things are non mutable then mark them with const
or constexpr
to indicate that they are non mutable. This will make sure the compiler tells you about an error if you accidentally change their value.
I would throw exception if the file name is not passed or the file did not open. Opps having read it threw now I see you do throw on open. I would change the order though so all the throwing is at the top. Then your code is all at the same indent level.
std::ifstream file;
if (argc >= 2)
{
file.open(argv[1]);
}
else
{
throw std::exception("No parameter passed");
}
std::string line;
if (file.is_open())
{
Your code is of the form:
if (isGood()) {
doGoodStuff();
}
else {
throw error;
}
Putting all your error tests at the top puts all your explicit checking and error handling at the top.
// Check pre-conditions.
if (!isGood()) {
throw error;
}
// All your pre-conditions have been checked.
doGoodStuff();
So your code above I would have written like this:
std::ifstream file;
if (argc < 2)
{
throw std::exception("No parameter passed");
}
// Initialize and open in one go.
std::ifstream file(argv[1]);
if (!file) // don't specifically check for a good state
{ // there are several bad states so check to see if the file
// is not bad.
throw std::exception("Unable to open file");
}
// Now spend time reading the file.
Exceptions. The std::exception
is the base class and has several derived types for different situations. In pre C++11 this class did not even take a string in the constructor so you could not use it like this:
std::exception("No parameter passed");
I would choose the more generic std::runtime_error
. You will need to include <stdexcept>
to get the definition.
OK this loop is absolutely not needed.
for (int z = 0; z < 4; z++)
In the code you basically go:
for (int z = 0; z < 4; z++) {
if (z == 0) {taskOne();}
if (z == 1) {taskTwo();}
if (z == 2) {taskThree();}
if (z == 3) {taskFour();}
}
This whole construct can simply be replaced with:
taskOne();
taskTwo();
taskThree();
taskFour();
In the next section you never check that any read operation worked. Any stream operation should be checked to make sure it worked.
iss >> n;
Did that actually read the value? Or is n
left in its original state (thus causing you to add the last value read repeatedly). If you have a one off error then this kind of thing results in the last value being placed into the data twice (common issue).
startingOrder.reserve(n);
for (int a = 0; a < n; a++)
{
int d;
iss >> d;
startingOrder.push_back(d - 1);
}
I would so something more like this:
startingOrder.reserve(n);
while(iss >> d) {
startingOrder.push_back(d - 1);
}
if (startingOrder.size() != n) {
throw std::runtime_exception("Malformed input file .... some text");
}
Technically you don't even need a loop you can simply use istream iterators to initiate an array. But while learning I would use the loop form and graduate to this form once you have started understanding more of the standard library.
// How to create an array from stream iterators.
startingOrder = std::vector<int>(std::istream_iterator<int>{iss},
std::istream_iterator<int>{});
Don't see the point in this.
file.close();
I would just let the destructor do its job and close the file.
This function header is not const correct.
long long calculateLowestCostOfWork(int const &n, int const &MAX_WEIGHT, int const &minWeightGlobally, std::vector<int>& weights, std::vector<int>& startingOrder, std::vector<int>& endingOrder)
You pass several parameters by reference that are non-mutable (all the input arrays).
This is a bad habit (not using the curly braces).
for (int i = 0; i < n; i++)
permutation[endingOrder[i]] = startingOrder[i];
When you don't put braces only the one next statement is part of the loop. The trouble is that it is not always obvious that there are two (or more) statements and thus you could have some hard to find errors.
// Not immediately obvious example. But still not 100% easy to spot.
// But a lot of code reviewers can still easily miss this.
for (int i = 0; i < n; i++)
permutation[endingOrder[i]] = startingOrder[i];
plop[i] = pile[i];
// This kind of thing has happened to me
#define UpdatePerm(permutation, endingOrder, startingOrder, plop, pile, i)
permutation[endingOrder[i]] = startingOrder[i];
plop[i] = pile[i]
// ... Lots of other code.
for (int i = 0; i < n; i++)
UpdatePerm(permutation, endingOrder, startingOrder, plop, pile, i);
Moral of the story always put the braces on and you will never be wrong.
for (int i = 0; i < n; i++) {
UpdatePerm(permutation, endingOrder, startingOrder, plop, pile, i);
}
// In your case:
for (int i = 0; i < n; i++) {
permutation[endingOrder[i]] = startingOrder[i];
}
Only putting the try around one function seems strange.
try
{
readFromFile(argc, argv,MAX_VERTEXES, MIN_VERTEXES, n, minWeightGlobally, weights, startingOrder, endingOrder);
}
catch (...)
{
std::cout << "Error";
}
std::cout << calculateLowestCostOfWork(n,MAX_WEIGHT,minWeightGlobally,weights,startingOrder,endingOrder);
In the main I would have all the code inside the try block. So that any future errors would be caught by the try (people change code and don't always check were the code is use). But in addition to just printing error I would print the message as well. Then I would re-throw the exception so that the external operating system knows there was an error.
try
{
// All real code that is not simply initializing constants.
readFromFile(argc, argv,MAX_VERTEXES, MIN_VERTEXES, n, minWeightGlobally, weights, startingOrder, endingOrder);
int result = calculateLowestCostOfWork(n,MAX_WEIGHT,minWeightGlobally,weights,startingOrder,endingOrder);
std::cout << result << "n";
}
catch (std::exception const& e) {
std::cerr << "Error: " << e.what() << "n";
throw;
}
catch (...) {
std::cerr << "Error: Unknown?n";
throw;
}
One variable per line please.
std::vector<int> weights, startingOrder, endingOrder;
This is simply horrible to read and make sure you got correct.
Let us have meaningful names.
int n=0;
I did a search of the code for the variable n
to see where it is used. Do you know how many times n
is in the code. Use meaningful names so it becomes easy to search and see the variables. Its not used by the way.
$endgroup$
$begingroup$
int n
is a good name for a loop limit (in my view) - andi
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 variablen
. How many characters are highlighted? From the beginning ofmain()
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 asn
is in both identifiers and keywords.
$endgroup$
– Martin York
yesterday
1
$begingroup$
@MartinYork While I agree with you onn
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. Thei
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
|
show 1 more comment
$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 receiveargc
andargv
. 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
, notint &n
. - Do not use RANDOM_CAPITALS in parameter names, regardless of whether the parameter is
const
. - Respect natural ordering:
min_vertexes
should come beforemax_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 (andelse
) 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
andd
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
withistream_iterator
s. - Don’t pass
int
(nor similar, small types) asconst&
, 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
frommain
. 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.
$endgroup$
$begingroup$
I've rebuilded a code, according to your advices. Thank you for your feedback.
$endgroup$
– Jan Dycz
yesterday
add a comment |
$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;
}
New contributor
$endgroup$
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
$begingroup$
Some minor comments:
No need to define
min
. Just#include <algorithm>
and usestd::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 ton
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 assignx
toi
, but suddenly it's got a value frompermutation
vector. Usei
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 useelse if
or even switch statements. Plus, it would be a good idea creating a function that you may reuse to create vectors from istringstreams:
vector<int> readVector(std::istringstream& iss, int n) {
vector<int> v(n);
for (int i = 0; i < n; ++i) {
int d;
iss >> d;
v[i] = d - 1;
}
return v;
}
As a general rule, try to initialize variables as close to their first use. For instance, in your code you shouldn't be able to see the word vector in your main method; everything should be encapsulated on your methods.
Also, as a general rule, try to minimize the number of parameters of your functions. With the tips that I have given you above, probably you will end up having up to 3 or 4 parameters per function.
Hopefully somebody else can give you some advice about exceptions.
$endgroup$
$begingroup$
Thank you for your feedback and advices. Is it advisable to include whole <algorithm> only for one std::min()? >Rather than reserving n elements on vectors, instantiate them with the appropriate size as you have done in std::vector<int> permutation(n);. But how if i don't know the size before reading n from file? >Your line while (!visitedVertexes[x]) seems redundant and should be replaced by an if, as at most 1 iteration is performed. >int x = i; Well i could put here x=0, since i am iterating from 0, first index of any container.
$endgroup$
– Jan Dycz
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 missx = permutation[x];
$endgroup$
– vnp
2 days ago
$begingroup$
The define about min is not only not needed, it is UB.
$endgroup$
– L. F.
yesterday
|
show 9 more comments
$begingroup$
Some minor comments:
No need to define
min
. Just#include <algorithm>
and usestd::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 ton
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 assignx
toi
, but suddenly it's got a value frompermutation
vector. Usei
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 useelse if
or even switch statements. Plus, it would be a good idea creating a function that you may reuse to create vectors from istringstreams:
vector<int> readVector(std::istringstream& iss, int n) {
vector<int> v(n);
for (int i = 0; i < n; ++i) {
int d;
iss >> d;
v[i] = d - 1;
}
return v;
}
As a general rule, try to initialize variables as close to their first use. For instance, in your code you shouldn't be able to see the word vector in your main method; everything should be encapsulated on your methods.
Also, as a general rule, try to minimize the number of parameters of your functions. With the tips that I have given you above, probably you will end up having up to 3 or 4 parameters per function.
Hopefully somebody else can give you some advice about exceptions.
$endgroup$
$begingroup$
Thank you for your feedback and advices. Is it advisable to include whole <algorithm> only for one std::min()? >Rather than reserving n elements on vectors, instantiate them with the appropriate size as you have done in std::vector<int> permutation(n);. But how if i don't know the size before reading n from file? >Your line while (!visitedVertexes[x]) seems redundant and should be replaced by an if, as at most 1 iteration is performed. >int x = i; Well i could put here x=0, since i am iterating from 0, first index of any container.
$endgroup$
– Jan Dycz
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 missx = permutation[x];
$endgroup$
– vnp
2 days ago
$begingroup$
The define about min is not only not needed, it is UB.
$endgroup$
– L. F.
yesterday
|
show 9 more comments
$begingroup$
Some minor comments:
No need to define
min
. Just#include <algorithm>
and usestd::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 ton
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 assignx
toi
, but suddenly it's got a value frompermutation
vector. Usei
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 useelse if
or even switch statements. Plus, it would be a good idea creating a function that you may reuse to create vectors from istringstreams:
vector<int> readVector(std::istringstream& iss, int n) {
vector<int> v(n);
for (int i = 0; i < n; ++i) {
int d;
iss >> d;
v[i] = d - 1;
}
return v;
}
As a general rule, try to initialize variables as close to their first use. For instance, in your code you shouldn't be able to see the word vector in your main method; everything should be encapsulated on your methods.
Also, as a general rule, try to minimize the number of parameters of your functions. With the tips that I have given you above, probably you will end up having up to 3 or 4 parameters per function.
Hopefully somebody else can give you some advice about exceptions.
$endgroup$
Some minor comments:
No need to define
min
. Just#include <algorithm>
and usestd::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 ton
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 assignx
toi
, but suddenly it's got a value frompermutation
vector. Usei
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 useelse 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.
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 missx = permutation[x];
$endgroup$
– vnp
2 days ago
$begingroup$
The define about min is not only not needed, it is UB.
$endgroup$
– L. F.
yesterday
|
show 9 more comments
$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 missx = 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
|
show 9 more comments
$begingroup$
I would just point out that the macro version of min is inferior.
#define min1(a,b) ((a) < (b) ? (a) : (b))
template<typename T>
inline min2(T const& a, T const& b) {return a < b ? a : b;}
Think of this situation.
min1(a1++, 5) // how many times is a incremented?
min2(a1++, 5)
$endgroup$
1
$begingroup$
Pardon my ignorance, but what is UB?
$endgroup$
– JnxF
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 namemin
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
|
show 4 more comments
$begingroup$
I would just point out that the macro version of min is inferior.
#define min1(a,b) ((a) < (b) ? (a) : (b))
template<typename T>
inline min2(T const& a, T const& b) {return a < b ? a : b;}
Think of this situation.
min1(a1++, 5) // how many times is a incremented?
min2(a1++, 5)
$endgroup$
1
$begingroup$
Pardon my ignorance, but what is UB?
$endgroup$
– JnxF
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 namemin
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
|
show 4 more comments
$begingroup$
I would just point out that the macro version of min is inferior.
#define min1(a,b) ((a) < (b) ? (a) : (b))
template<typename T>
inline min2(T const& a, T const& b) {return a < b ? a : b;}
Think of this situation.
min1(a1++, 5) // how many times is a incremented?
min2(a1++, 5)
$endgroup$
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)
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 namemin
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
|
show 4 more comments
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 namemin
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
|
show 4 more comments
$begingroup$
Design
You biggest problem is encapsulation.
You treat your three different properties as three different data items rather than as a single data item. I feel it would be more logical to combine the data into a single item.
I suppose you did it this way because of the design of the input file. If given the chance I would change the format of this file. Define the properties of each item (start, end, weight) all on the same line. But even if you can't change the format I would still try and encapsulate the data into a single item.
Error
If the input file is mis-formed then you probably will not detect it and simply fill the input arrays with garbage values.
Code Review
Please no:
#define min(a,b) ((a) < (b) ? (a) : (b))
There is no reason to use macros (apart from the one thing they are good at which is conditional compilation of code, preferably to take into account different system implementations).
Looks like MAX_VERTEXES
and MIN_VERTEXES
and MAX_WIGHT
should simply be global static state, rather than passed around the application. Note global variables are OK iff they are constant (ie non mutable).
int constexpr MaxVertexes = 1000000;
int constexpr MinVertexes = 2;
int constexpr MaxWeight = 6500;
The other thing you should note is that all capitol identifiers are traditionally reserved for macros. Using them as variable names is iffy at best going to cause issues at worst. Please make sure all non macros use standard variable names.
If things are non mutable then mark them with const
or constexpr
to indicate that they are non mutable. This will make sure the compiler tells you about an error if you accidentally change their value.
I would throw exception if the file name is not passed or the file did not open. Opps having read it threw now I see you do throw on open. I would change the order though so all the throwing is at the top. Then your code is all at the same indent level.
std::ifstream file;
if (argc >= 2)
{
file.open(argv[1]);
}
else
{
throw std::exception("No parameter passed");
}
std::string line;
if (file.is_open())
{
Your code is of the form:
if (isGood()) {
doGoodStuff();
}
else {
throw error;
}
Putting all your error tests at the top puts all your explicit checking and error handling at the top.
// Check pre-conditions.
if (!isGood()) {
throw error;
}
// All your pre-conditions have been checked.
doGoodStuff();
So your code above I would have written like this:
std::ifstream file;
if (argc < 2)
{
throw std::exception("No parameter passed");
}
// Initialize and open in one go.
std::ifstream file(argv[1]);
if (!file) // don't specifically check for a good state
{ // there are several bad states so check to see if the file
// is not bad.
throw std::exception("Unable to open file");
}
// Now spend time reading the file.
Exceptions. The std::exception
is the base class and has several derived types for different situations. In pre C++11 this class did not even take a string in the constructor so you could not use it like this:
std::exception("No parameter passed");
I would choose the more generic std::runtime_error
. You will need to include <stdexcept>
to get the definition.
OK this loop is absolutely not needed.
for (int z = 0; z < 4; z++)
In the code you basically go:
for (int z = 0; z < 4; z++) {
if (z == 0) {taskOne();}
if (z == 1) {taskTwo();}
if (z == 2) {taskThree();}
if (z == 3) {taskFour();}
}
This whole construct can simply be replaced with:
taskOne();
taskTwo();
taskThree();
taskFour();
In the next section you never check that any read operation worked. Any stream operation should be checked to make sure it worked.
iss >> n;
Did that actually read the value? Or is n
left in its original state (thus causing you to add the last value read repeatedly). If you have a one off error then this kind of thing results in the last value being placed into the data twice (common issue).
startingOrder.reserve(n);
for (int a = 0; a < n; a++)
{
int d;
iss >> d;
startingOrder.push_back(d - 1);
}
I would so something more like this:
startingOrder.reserve(n);
while(iss >> d) {
startingOrder.push_back(d - 1);
}
if (startingOrder.size() != n) {
throw std::runtime_exception("Malformed input file .... some text");
}
Technically you don't even need a loop you can simply use istream iterators to initiate an array. But while learning I would use the loop form and graduate to this form once you have started understanding more of the standard library.
// How to create an array from stream iterators.
startingOrder = std::vector<int>(std::istream_iterator<int>{iss},
std::istream_iterator<int>{});
Don't see the point in this.
file.close();
I would just let the destructor do its job and close the file.
This function header is not const correct.
long long calculateLowestCostOfWork(int const &n, int const &MAX_WEIGHT, int const &minWeightGlobally, std::vector<int>& weights, std::vector<int>& startingOrder, std::vector<int>& endingOrder)
You pass several parameters by reference that are non-mutable (all the input arrays).
This is a bad habit (not using the curly braces).
for (int i = 0; i < n; i++)
permutation[endingOrder[i]] = startingOrder[i];
When you don't put braces only the one next statement is part of the loop. The trouble is that it is not always obvious that there are two (or more) statements and thus you could have some hard to find errors.
// Not immediately obvious example. But still not 100% easy to spot.
// But a lot of code reviewers can still easily miss this.
for (int i = 0; i < n; i++)
permutation[endingOrder[i]] = startingOrder[i];
plop[i] = pile[i];
// This kind of thing has happened to me
#define UpdatePerm(permutation, endingOrder, startingOrder, plop, pile, i)
permutation[endingOrder[i]] = startingOrder[i];
plop[i] = pile[i]
// ... Lots of other code.
for (int i = 0; i < n; i++)
UpdatePerm(permutation, endingOrder, startingOrder, plop, pile, i);
Moral of the story always put the braces on and you will never be wrong.
for (int i = 0; i < n; i++) {
UpdatePerm(permutation, endingOrder, startingOrder, plop, pile, i);
}
// In your case:
for (int i = 0; i < n; i++) {
permutation[endingOrder[i]] = startingOrder[i];
}
Only putting the try around one function seems strange.
try
{
readFromFile(argc, argv,MAX_VERTEXES, MIN_VERTEXES, n, minWeightGlobally, weights, startingOrder, endingOrder);
}
catch (...)
{
std::cout << "Error";
}
std::cout << calculateLowestCostOfWork(n,MAX_WEIGHT,minWeightGlobally,weights,startingOrder,endingOrder);
In the main I would have all the code inside the try block. So that any future errors would be caught by the try (people change code and don't always check were the code is use). But in addition to just printing error I would print the message as well. Then I would re-throw the exception so that the external operating system knows there was an error.
try
{
// All real code that is not simply initializing constants.
readFromFile(argc, argv,MAX_VERTEXES, MIN_VERTEXES, n, minWeightGlobally, weights, startingOrder, endingOrder);
int result = calculateLowestCostOfWork(n,MAX_WEIGHT,minWeightGlobally,weights,startingOrder,endingOrder);
std::cout << result << "n";
}
catch (std::exception const& e) {
std::cerr << "Error: " << e.what() << "n";
throw;
}
catch (...) {
std::cerr << "Error: Unknown?n";
throw;
}
One variable per line please.
std::vector<int> weights, startingOrder, endingOrder;
This is simply horrible to read and make sure you got correct.
Let us have meaningful names.
int n=0;
I did a search of the code for the variable n
to see where it is used. Do you know how many times n
is in the code. Use meaningful names so it becomes easy to search and see the variables. Its not used by the way.
$endgroup$
$begingroup$
int n
is a good name for a loop limit (in my view) - andi
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 variablen
. How many characters are highlighted? From the beginning ofmain()
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 asn
is in both identifiers and keywords.
$endgroup$
– Martin York
yesterday
1
$begingroup$
@MartinYork While I agree with you onn
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. Thei
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
|
show 1 more comment
$begingroup$
Design
You biggest problem is encapsulation.
You treat your three different properties as three different data items rather than as a single data item. I feel it would be more logical to combine the data into a single item.
I suppose you did it this way because of the design of the input file. If given the chance I would change the format of this file. Define the properties of each item (start, end, weight) all on the same line. But even if you can't change the format I would still try and encapsulate the data into a single item.
Error
If the input file is mis-formed then you probably will not detect it and simply fill the input arrays with garbage values.
Code Review
Please no:
#define min(a,b) ((a) < (b) ? (a) : (b))
There is no reason to use macros (apart from the one thing they are good at which is conditional compilation of code, preferably to take into account different system implementations).
Looks like MAX_VERTEXES
and MIN_VERTEXES
and MAX_WIGHT
should simply be global static state, rather than passed around the application. Note global variables are OK iff they are constant (ie non mutable).
int constexpr MaxVertexes = 1000000;
int constexpr MinVertexes = 2;
int constexpr MaxWeight = 6500;
The other thing you should note is that all capitol identifiers are traditionally reserved for macros. Using them as variable names is iffy at best going to cause issues at worst. Please make sure all non macros use standard variable names.
If things are non mutable then mark them with const
or constexpr
to indicate that they are non mutable. This will make sure the compiler tells you about an error if you accidentally change their value.
I would throw exception if the file name is not passed or the file did not open. Opps having read it threw now I see you do throw on open. I would change the order though so all the throwing is at the top. Then your code is all at the same indent level.
std::ifstream file;
if (argc >= 2)
{
file.open(argv[1]);
}
else
{
throw std::exception("No parameter passed");
}
std::string line;
if (file.is_open())
{
Your code is of the form:
if (isGood()) {
doGoodStuff();
}
else {
throw error;
}
Putting all your error tests at the top puts all your explicit checking and error handling at the top.
// Check pre-conditions.
if (!isGood()) {
throw error;
}
// All your pre-conditions have been checked.
doGoodStuff();
So your code above I would have written like this:
std::ifstream file;
if (argc < 2)
{
throw std::exception("No parameter passed");
}
// Initialize and open in one go.
std::ifstream file(argv[1]);
if (!file) // don't specifically check for a good state
{ // there are several bad states so check to see if the file
// is not bad.
throw std::exception("Unable to open file");
}
// Now spend time reading the file.
Exceptions. The std::exception
is the base class and has several derived types for different situations. In pre C++11 this class did not even take a string in the constructor so you could not use it like this:
std::exception("No parameter passed");
I would choose the more generic std::runtime_error
. You will need to include <stdexcept>
to get the definition.
OK this loop is absolutely not needed.
for (int z = 0; z < 4; z++)
In the code you basically go:
for (int z = 0; z < 4; z++) {
if (z == 0) {taskOne();}
if (z == 1) {taskTwo();}
if (z == 2) {taskThree();}
if (z == 3) {taskFour();}
}
This whole construct can simply be replaced with:
taskOne();
taskTwo();
taskThree();
taskFour();
In the next section you never check that any read operation worked. Any stream operation should be checked to make sure it worked.
iss >> n;
Did that actually read the value? Or is n
left in its original state (thus causing you to add the last value read repeatedly). If you have a one off error then this kind of thing results in the last value being placed into the data twice (common issue).
startingOrder.reserve(n);
for (int a = 0; a < n; a++)
{
int d;
iss >> d;
startingOrder.push_back(d - 1);
}
I would so something more like this:
startingOrder.reserve(n);
while(iss >> d) {
startingOrder.push_back(d - 1);
}
if (startingOrder.size() != n) {
throw std::runtime_exception("Malformed input file .... some text");
}
Technically you don't even need a loop you can simply use istream iterators to initiate an array. But while learning I would use the loop form and graduate to this form once you have started understanding more of the standard library.
// How to create an array from stream iterators.
startingOrder = std::vector<int>(std::istream_iterator<int>{iss},
std::istream_iterator<int>{});
Don't see the point in this.
file.close();
I would just let the destructor do its job and close the file.
This function header is not const correct.
long long calculateLowestCostOfWork(int const &n, int const &MAX_WEIGHT, int const &minWeightGlobally, std::vector<int>& weights, std::vector<int>& startingOrder, std::vector<int>& endingOrder)
You pass several parameters by reference that are non-mutable (all the input arrays).
This is a bad habit (not using the curly braces).
for (int i = 0; i < n; i++)
permutation[endingOrder[i]] = startingOrder[i];
When you don't put braces only the one next statement is part of the loop. The trouble is that it is not always obvious that there are two (or more) statements and thus you could have some hard to find errors.
// Not immediately obvious example. But still not 100% easy to spot.
// But a lot of code reviewers can still easily miss this.
for (int i = 0; i < n; i++)
permutation[endingOrder[i]] = startingOrder[i];
plop[i] = pile[i];
// This kind of thing has happened to me
#define UpdatePerm(permutation, endingOrder, startingOrder, plop, pile, i)
permutation[endingOrder[i]] = startingOrder[i];
plop[i] = pile[i]
// ... Lots of other code.
for (int i = 0; i < n; i++)
UpdatePerm(permutation, endingOrder, startingOrder, plop, pile, i);
Moral of the story always put the braces on and you will never be wrong.
for (int i = 0; i < n; i++) {
UpdatePerm(permutation, endingOrder, startingOrder, plop, pile, i);
}
// In your case:
for (int i = 0; i < n; i++) {
permutation[endingOrder[i]] = startingOrder[i];
}
Only putting the try around one function seems strange.
try
{
readFromFile(argc, argv,MAX_VERTEXES, MIN_VERTEXES, n, minWeightGlobally, weights, startingOrder, endingOrder);
}
catch (...)
{
std::cout << "Error";
}
std::cout << calculateLowestCostOfWork(n,MAX_WEIGHT,minWeightGlobally,weights,startingOrder,endingOrder);
In the main I would have all the code inside the try block. So that any future errors would be caught by the try (people change code and don't always check were the code is use). But in addition to just printing error I would print the message as well. Then I would re-throw the exception so that the external operating system knows there was an error.
try
{
// All real code that is not simply initializing constants.
readFromFile(argc, argv,MAX_VERTEXES, MIN_VERTEXES, n, minWeightGlobally, weights, startingOrder, endingOrder);
int result = calculateLowestCostOfWork(n,MAX_WEIGHT,minWeightGlobally,weights,startingOrder,endingOrder);
std::cout << result << "n";
}
catch (std::exception const& e) {
std::cerr << "Error: " << e.what() << "n";
throw;
}
catch (...) {
std::cerr << "Error: Unknown?n";
throw;
}
One variable per line please.
std::vector<int> weights, startingOrder, endingOrder;
This is simply horrible to read and make sure you got correct.
Let us have meaningful names.
int n=0;
I did a search of the code for the variable n
to see where it is used. Do you know how many times n
is in the code. Use meaningful names so it becomes easy to search and see the variables. Its not used by the way.
$endgroup$
$begingroup$
int n
is a good name for a loop limit (in my view) - andi
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 variablen
. How many characters are highlighted? From the beginning ofmain()
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 asn
is in both identifiers and keywords.
$endgroup$
– Martin York
yesterday
1
$begingroup$
@MartinYork While I agree with you onn
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. Thei
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
|
show 1 more comment
$begingroup$
Design
You biggest problem is encapsulation.
You treat your three different properties as three different data items rather than as a single data item. I feel it would be more logical to combine the data into a single item.
I suppose you did it this way because of the design of the input file. If given the chance I would change the format of this file. Define the properties of each item (start, end, weight) all on the same line. But even if you can't change the format I would still try and encapsulate the data into a single item.
Error
If the input file is mis-formed then you probably will not detect it and simply fill the input arrays with garbage values.
Code Review
Please no:
#define min(a,b) ((a) < (b) ? (a) : (b))
There is no reason to use macros (apart from the one thing they are good at which is conditional compilation of code, preferably to take into account different system implementations).
Looks like MAX_VERTEXES
and MIN_VERTEXES
and MAX_WIGHT
should simply be global static state, rather than passed around the application. Note global variables are OK iff they are constant (ie non mutable).
int constexpr MaxVertexes = 1000000;
int constexpr MinVertexes = 2;
int constexpr MaxWeight = 6500;
The other thing you should note is that all capitol identifiers are traditionally reserved for macros. Using them as variable names is iffy at best going to cause issues at worst. Please make sure all non macros use standard variable names.
If things are non mutable then mark them with const
or constexpr
to indicate that they are non mutable. This will make sure the compiler tells you about an error if you accidentally change their value.
I would throw exception if the file name is not passed or the file did not open. Opps having read it threw now I see you do throw on open. I would change the order though so all the throwing is at the top. Then your code is all at the same indent level.
std::ifstream file;
if (argc >= 2)
{
file.open(argv[1]);
}
else
{
throw std::exception("No parameter passed");
}
std::string line;
if (file.is_open())
{
Your code is of the form:
if (isGood()) {
doGoodStuff();
}
else {
throw error;
}
Putting all your error tests at the top puts all your explicit checking and error handling at the top.
// Check pre-conditions.
if (!isGood()) {
throw error;
}
// All your pre-conditions have been checked.
doGoodStuff();
So your code above I would have written like this:
std::ifstream file;
if (argc < 2)
{
throw std::exception("No parameter passed");
}
// Initialize and open in one go.
std::ifstream file(argv[1]);
if (!file) // don't specifically check for a good state
{ // there are several bad states so check to see if the file
// is not bad.
throw std::exception("Unable to open file");
}
// Now spend time reading the file.
Exceptions. The std::exception
is the base class and has several derived types for different situations. In pre C++11 this class did not even take a string in the constructor so you could not use it like this:
std::exception("No parameter passed");
I would choose the more generic std::runtime_error
. You will need to include <stdexcept>
to get the definition.
OK this loop is absolutely not needed.
for (int z = 0; z < 4; z++)
In the code you basically go:
for (int z = 0; z < 4; z++) {
if (z == 0) {taskOne();}
if (z == 1) {taskTwo();}
if (z == 2) {taskThree();}
if (z == 3) {taskFour();}
}
This whole construct can simply be replaced with:
taskOne();
taskTwo();
taskThree();
taskFour();
In the next section you never check that any read operation worked. Any stream operation should be checked to make sure it worked.
iss >> n;
Did that actually read the value? Or is n
left in its original state (thus causing you to add the last value read repeatedly). If you have a one off error then this kind of thing results in the last value being placed into the data twice (common issue).
startingOrder.reserve(n);
for (int a = 0; a < n; a++)
{
int d;
iss >> d;
startingOrder.push_back(d - 1);
}
I would so something more like this:
startingOrder.reserve(n);
while(iss >> d) {
startingOrder.push_back(d - 1);
}
if (startingOrder.size() != n) {
throw std::runtime_exception("Malformed input file .... some text");
}
Technically you don't even need a loop you can simply use istream iterators to initiate an array. But while learning I would use the loop form and graduate to this form once you have started understanding more of the standard library.
// How to create an array from stream iterators.
startingOrder = std::vector<int>(std::istream_iterator<int>{iss},
std::istream_iterator<int>{});
Don't see the point in this.
file.close();
I would just let the destructor do its job and close the file.
This function header is not const correct.
long long calculateLowestCostOfWork(int const &n, int const &MAX_WEIGHT, int const &minWeightGlobally, std::vector<int>& weights, std::vector<int>& startingOrder, std::vector<int>& endingOrder)
You pass several parameters by reference that are non-mutable (all the input arrays).
This is a bad habit (not using the curly braces).
for (int i = 0; i < n; i++)
permutation[endingOrder[i]] = startingOrder[i];
When you don't put braces only the one next statement is part of the loop. The trouble is that it is not always obvious that there are two (or more) statements and thus you could have some hard to find errors.
// Not immediately obvious example. But still not 100% easy to spot.
// But a lot of code reviewers can still easily miss this.
for (int i = 0; i < n; i++)
permutation[endingOrder[i]] = startingOrder[i];
plop[i] = pile[i];
// This kind of thing has happened to me
#define UpdatePerm(permutation, endingOrder, startingOrder, plop, pile, i)
permutation[endingOrder[i]] = startingOrder[i];
plop[i] = pile[i]
// ... Lots of other code.
for (int i = 0; i < n; i++)
UpdatePerm(permutation, endingOrder, startingOrder, plop, pile, i);
Moral of the story always put the braces on and you will never be wrong.
for (int i = 0; i < n; i++) {
UpdatePerm(permutation, endingOrder, startingOrder, plop, pile, i);
}
// In your case:
for (int i = 0; i < n; i++) {
permutation[endingOrder[i]] = startingOrder[i];
}
Only putting the try around one function seems strange.
try
{
readFromFile(argc, argv,MAX_VERTEXES, MIN_VERTEXES, n, minWeightGlobally, weights, startingOrder, endingOrder);
}
catch (...)
{
std::cout << "Error";
}
std::cout << calculateLowestCostOfWork(n,MAX_WEIGHT,minWeightGlobally,weights,startingOrder,endingOrder);
In the main I would have all the code inside the try block. So that any future errors would be caught by the try (people change code and don't always check were the code is use). But in addition to just printing error I would print the message as well. Then I would re-throw the exception so that the external operating system knows there was an error.
try
{
// All real code that is not simply initializing constants.
readFromFile(argc, argv,MAX_VERTEXES, MIN_VERTEXES, n, minWeightGlobally, weights, startingOrder, endingOrder);
int result = calculateLowestCostOfWork(n,MAX_WEIGHT,minWeightGlobally,weights,startingOrder,endingOrder);
std::cout << result << "n";
}
catch (std::exception const& e) {
std::cerr << "Error: " << e.what() << "n";
throw;
}
catch (...) {
std::cerr << "Error: Unknown?n";
throw;
}
One variable per line please.
std::vector<int> weights, startingOrder, endingOrder;
This is simply horrible to read and make sure you got correct.
Let us have meaningful names.
int n=0;
I did a search of the code for the variable n
to see where it is used. Do you know how many times n
is in the code. Use meaningful names so it becomes easy to search and see the variables. Its not used by the way.
$endgroup$
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.
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) - andi
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 variablen
. How many characters are highlighted? From the beginning ofmain()
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 asn
is in both identifiers and keywords.
$endgroup$
– Martin York
yesterday
1
$begingroup$
@MartinYork While I agree with you onn
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. Thei
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
|
show 1 more comment
$begingroup$
int n
is a good name for a loop limit (in my view) - andi
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 variablen
. How many characters are highlighted? From the beginning ofmain()
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 asn
is in both identifiers and keywords.
$endgroup$
– Martin York
yesterday
1
$begingroup$
@MartinYork While I agree with you onn
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. Thei
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
|
show 1 more comment
$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 receiveargc
andargv
. 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
, notint &n
. - Do not use RANDOM_CAPITALS in parameter names, regardless of whether the parameter is
const
. - Respect natural ordering:
min_vertexes
should come beforemax_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 (andelse
) 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
andd
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
withistream_iterator
s. - Don’t pass
int
(nor similar, small types) asconst&
, 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
frommain
. 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.
$endgroup$
$begingroup$
I've rebuilded a code, according to your advices. Thank you for your feedback.
$endgroup$
– Jan Dycz
yesterday
add a comment |
$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 receiveargc
andargv
. 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
, notint &n
. - Do not use RANDOM_CAPITALS in parameter names, regardless of whether the parameter is
const
. - Respect natural ordering:
min_vertexes
should come beforemax_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 (andelse
) 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
andd
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
withistream_iterator
s. - Don’t pass
int
(nor similar, small types) asconst&
, 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
frommain
. 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.
$endgroup$
$begingroup$
I've rebuilded a code, according to your advices. Thank you for your feedback.
$endgroup$
– Jan Dycz
yesterday
add a comment |
$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 receiveargc
andargv
. 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
, notint &n
. - Do not use RANDOM_CAPITALS in parameter names, regardless of whether the parameter is
const
. - Respect natural ordering:
min_vertexes
should come beforemax_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 (andelse
) 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
andd
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
withistream_iterator
s. - Don’t pass
int
(nor similar, small types) asconst&
, 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
frommain
. 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.
$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 receiveargc
andargv
. 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
, notint &n
. - Do not use RANDOM_CAPITALS in parameter names, regardless of whether the parameter is
const
. - Respect natural ordering:
min_vertexes
should come beforemax_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 (andelse
) 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
andd
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
withistream_iterator
s. - Don’t pass
int
(nor similar, small types) asconst&
, 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
frommain
. 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.
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
add a comment |
$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
add a comment |
$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;
}
New contributor
$endgroup$
add a comment |
$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;
}
New contributor
$endgroup$
add a comment |
$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;
}
New contributor
$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;
}
New contributor
New contributor
answered 15 hours ago
Jan DyczJan Dycz
165 bronze badges
165 bronze badges
New contributor
New contributor
add a comment |
add a comment |
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.
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
$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