"More Pizza" Problem: C++ Code Solution

Table Of Contents

Introduction
The main() function
Reading data from a file
The solution class

How to quickly calculate new solutions?

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

Unlock now all the premium content in this page.

Sign-in or register to buy access to this content using your virtual coins.

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

Unlock now all the premium content in this page.

Sign-in or register to buy access to this content using your virtual coins.