“More Pizza” problem: C++ code solution

In this article, the C++ code implementation of the "More Pizza" algorithm is provided and commented. The complete source file is available.

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:

  1. Reading of the input parameters (input file name, specific procedure parameters, etc. ).
  2. Reading of input data and storage of the information in a proper data structure.
  3. The solving procedure.
  4. Validation of the result (optional, as it is done by Google itself)
  5. 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.


 
Pietro L. Carotenuto
Pietro L. Carotenuto

C++ Software Engineer, Ph.D. in Information Engineering. I like reading and learning new things while working on new projects. Main author on PietroLC.com looking for contributions and guest authors.

Articles: 29

One comment

Leave your feedback here:

Your email address will not be published. Required fields are marked *