Introduction
The idea behind the algorithm used to solve the “More Pizza” problem is very simple: starting from a randomly chosen solution, this is further improved until a stop condition is met (e.g., the maximum score is achieved).
The description of the “More Pizza” algorithm have been provided in a previous post.
In this article, the C++ code implementation of that algorithm is provided and commented.
The main() function
Independently of the used approach, it is expected that these steps are followed:
- Reading of the input parameters (input file name, specific procedure parameters, etc. ).
- Reading of input data and storage of the information in a proper data structure.
- The solving procedure.
- Validation of the result (optional, as it is done by Google itself)
- Output of the solution to a file (if not already done in the solving procedure).
A set of global variables have been defined at the very top of the script:
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <chrono>
#include <map>
#include <set>
#include <random>
#include <memory>
using namespace std;
// Default input and output filenames
string iFileName{ "..\\a_example.in" };
string oFileName{ "..\\a_example.out" };
// Max number of slices (capacity)
int32_t M{ 0 };
// Number available of pizzas
int32_t N{ 0 };
using TSol = vector<int32_t>; // it is used for both pizzas and solution
TSol pizzas{}; // storing number of slices of each pizza
// Random numbers generator
std::random_device rd;
std::mt19937 g(rd());
std::uniform_int_distribution<int32_t> rnProbValue(0, 100);
std::uniform_real_distribution<double> rnProb(0, 1);
// Number of neighbours to check
int32_t numMaxItemsToCheck{ 5u };
double T0 = 10000.0; // Default initial temperature
double ae = 0.000001; // Default reduction factor
The structure of the main() function replicates the steps listed above.
int main(int argc, char* argv[])
{
// Reading input parameters
for (int i = 0; i < argc; i++)
{
cout << "argv[" << i << "] = " << argv[i] << endl;
}
if (argc > 1)
{
iFileName = argv[1];
oFileName = iFileName;
oFileName.append(".out");
if (argc >= 3)
{
T0 = std::atof(argv[2]);
if (argc >= 4)
{
numMaxItemsToCheck = std::atoi(argv[3]);
if (argc >= 5)
{
ae = std::atof(argv[4]);
}
}
}
}
std::cout << "input file: " << iFileName << endl;
std::cout << "output file: " << oFileName << endl;
std::cout << "initial temperature: " << T0 << endl;
std::cout << "alpha exp: " << ae << endl;
std::cout << "num neighbours: " << numMaxItemsToCheck << endl;
// Read data from input file
readInput();
auto start = chrono::steady_clock::now();
orderPizzas();
auto end = chrono::steady_clock::now();
cout << "Elapsed time in milliseconds : "
<< chrono::duration_cast<chrono::milliseconds>(end - start).count()
<< " ms" << endl;
return 0;
}
The validation of the solution and the saving of the solution to a file are part of the procedure itself. In fact, it is expected that each calculated solution is also valid. In addition, if the new solution improves the current result, then it should be saved to a file too.
Reading data from a file
The following code has been implemented to read the input file. The first two integers represent the maximum number of slices (i.e., the maximum score) and the number of pizzas respectively. The remaining N integers represent the number of each pizza.
// Read input data from a file
void readInput()
{
ifstream iFile;
iFile.open(iFileName);
iFile >> M; // Maximum number of slices (i.e., max score)
iFile >> N; // Number of pizzas
std::cout << "Max. num. slices: " << M << endl;
std::cout << "N. pizzas: " << N << endl;
//init pizzas vector
pizzas.reserve(N);
for (int32_t i = 0; i < N; i++)
{
int32_t tmpPizza{};
iFile >> tmpPizza;
pizzas.emplace_back(tmpPizza);
}
iFile.close();
pizzas.shrink_to_fit();
std::cout << "DONE!" << endl;
}
The solution class
I preferred to represent the solution inside a class to:
- store the actual solution.
- store the score of the solution.
- save the “state” of a solution (e.g., which pizzas can be added to the current solution).
- implement utility functions to:
- create an empty solution (i.e., having zero score).
- create a random solution.
- change the current solution in a random way (please, check mutate() function).
- calculate the score of the solution (please, check score() function).
- save the solution into a file with the required format (please, check the function saveSolutionToFile() ).
- print the current solution to screen
Unlock now all the premium content in this page.
Sign-in or register to buy access to this content using your virtual coins.
