Even More Pizza Hash Code: C++ Algorithm

1. The required header files
2. The algorithm parameters
3. Read input data
4. The representation of the solution
5. The Simulated Annealing algorithm
6. The main
7. Algorithm description
8. Conclusion

#The required header files

// Even More Pizza - Google Hash Code - 2021.
//
// Author: Pietro L. Carotenuto - https://www.pietrolc.com
#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <chrono>
#include <map>
#include <set>
#include <random>
#include <memory>
#include <list>

#The algorithm parameters

using namespace std;
using TSol = map<int, vector<int>>;

// Default input and output filenames 
string iFileName{ "..\a_example" };
string oFileName{ "..\a_example.out" };

// Number available of pizzas
int M{ 0 };
int M2{ 0 }; // Pizzas needed to deliver all orders!
int M3{ 0 }; // Min between M and M2
std::vector<int> T(3,0); // Capacity
 
using TPizza = std::set<int32_t>; // each pizza is made of integer ingredients
using TPizzaVect = vector<TPizza>; // vector of pizzas

TPizzaVect pizzas{};
int nIngr = 0; // total number of ingredients (to calculate)
std::vector<size_t> pzScore; // this vector contains the data used to initially sort the pizzas

// Random numbers generator
std::random_device rd;
std::mt19937 g(rd());
std::uniform_real_distribution<double> rnProb(0, 1);
std::uniform_int_distribution<int> rnBucket(0, 2); // to randomly choose among the teams of different size

// Number of neighbours to check
int32_t numMaxItemsToCheck{ 5u };
double T0 = 10000.0; // Default initial temperature
double ae = 0.000001; // Default reduction factor

// Size of the teams
const std::vector<int> pxp{ 2,3,4 };
using namespace std;
using TSol = map<int, vector<int>>;

// Default input and output filenames 
string iFileName{ "..\a_example" };
string oFileName{ "..\a_example.out" };

// Number available of pizzas
int M{ 0 };
int M2{ 0 }; // Pizzas needed to deliver all orders!
int M3{ 0 }; // Min between M and M2
std::vector<int> T(3,0); // Capacity
 
using TPizza = std::set<int32_t>; // each pizza is made of integer ingredients
using TPizzaVect = vector<TPizza>; // vector of pizzas

TPizzaVect pizzas{};
int nIngr = 0; // total number of ingredients (to calculate)
std::vector<size_t> pzScore; // this vector contains the data used to initially sort the pizzas

// Random numbers generator
std::random_device rd;
std::mt19937 g(rd());
std::uniform_real_distribution<double> rnProb(0, 1);
std::uniform_int_distribution<int> rnBucket(0, 2); // to randomly choose among the teams of different size

// Number of neighbours to check
int32_t numMaxItemsToCheck{ 5u };
double T0 = 10000.0; // Default initial temperature
double ae = 0.000001; // Default reduction factor

// Size of the teams
const std::vector<int> pxp{ 2,3,4 };

#Read input data

// Read input data from a file
void readInput()
{
    ifstream iFile;
    iFile.open(iFileName);
    iFile >> M;
    iFile >> T[0];
    iFile >> T[1];
    iFile >> T[2];
    M2 = T[0] * 2 + T[1] * 3 + T[2] * 4;
    M3 = std::min<int>(M, M2); // the sum of capacities must not exceed this value!
    std::cout << "N. pizzas: " << M << endl;
    std::cout << "T2: " << T[0] << endl;
    std::cout << "T3: " << T[1] << endl;
    std::cout << "T4: " << T[2] << endl;
    std::cout << "N. pizzas required to fill all orders: " << M2 << endl;
    //init pizzas vector
    pizzas.reserve(M);
    nIngr = 0;
    std::map<string, int> labels;
    for (int32_t i = 0; i < M; i++)
    {
        TPizza tmpPizza{};
        int sData;
        iFile >> sData;
        
        for (int j = 0; j < sData; j++)
        {
            string vData;
            iFile >> vData;
            if (labels.find(vData) != labels.end())
            {
                tmpPizza.emplace(labels[vData]);
            }
            else
            {
                labels[vData] = nIngr;
                tmpPizza.emplace(nIngr);
                ++nIngr;
            }
        }
        pizzas.emplace_back(tmpPizza);
    }
    iFile.close();
    pizzas.shrink_to_fit();
    std::cout << "N. ingredients: " << nIngr << endl;
    std::cout << "DONE!" << endl << endl;
}

#The representation of the solution

// Container used to store the solution
// including its "state". The state of
// a solution is required to quickly change it
// and generate a new "neighbour"
struct TSolCnt
{
    // Initialize a solution
    // The constructor should contain a greedy algorithm to get as much closer as possible to the best solution 
    TSolCnt()
    {
        sol[0] = {}; // This list contains all orders of size 2 (pizzas)
        sol[1] = {}; // This list contains all orders of size 3 (pizzas)
        sol[2] = {}; // This list contains all orders of size 4 (pizzas)
        std::vector<int> pzTmp(M, 0);
        for (int k = 0; k < M; ++k)
        {
            pzTmp[k] = k;
        }
        
        // You can generate a random solution or implement your own method to get the initial solution
        //std::shuffle(pzTmp.begin(), pzTmp.end(), g );
        std::sort(pzTmp.begin(), pzTmp.end(), 
            [&](int a, int b) 
            {
                return pzScore[a] > pzScore[b];
            });
        for (int p : pzTmp)
        {
            avPizzas.emplace_back(p);
        }
        
        // Filling initial data
        for (int i = 2; i >= 0; --i)
        {
            const size_t nord = std::min<size_t>(avPizzas.size() / (i + 2),  T[i] );
            const size_t np = nord * (i + 2);
            if (np > 0)
            {
                sol[i].insert(sol[i].begin(), avPizzas.begin(), std::next(avPizzas.begin(), np));
                avPizzas.erase(avPizzas.begin(), std::next(avPizzas.begin(), np));
            }
        }
        numOrders = calculateNumOrders(); // Calculate initial number of orders
        score = calculateTotalScore(); // Calculate initial score
    }
    // Assignment
    TSolCnt& operator= (const TSolCnt& rhs)
    {
        score = rhs.score;
        sol = rhs.sol;
        avPizzas = rhs.avPizzas;
        numOrders = rhs.numOrders;
        return *this;
    };
    // To calculate the score of a single order
    size_t calculateScore(vector<int>& v)
    {
        std::set<int> ings{};
        for (int idx : v)
        {
            for (int pz : pizzas[idx])
            {
                ings.emplace(pz);
            }
        }
        size_t s = ings.size();
        return (s * s);
    }
    // To calculate the score of the whole solution
    size_t calculateTotalScore()
    {
        size_t s = 0;
        for (auto p : pxp )
        {
            for (auto it = sol[p-2].begin(); 
                it != sol[p - 2].end();
                it = std::next(it, p))
            {
                vector<int> order(it, std::next(it, p));
                s += calculateScore(order);
            }
        }
        return s;
    }
    // To calculate the number of the orders
    size_t calculateNumOrders()
    {
        size_t nOrders = 0;
        for (auto p : pxp)
        {
            nOrders += sol[p - 2].size() / p;
        }
        return nOrders;
    }
    // To mutate the current solution and generate a new one
    void mutate(
        std::uniform_int_distribution<int32_t>& rnPizzaID,
        int& itID )
    {
        const bool smallJmp = rnProb(g) < 0.90;
        int attrem = 0;
        if (rnProb(g) < 0.8) // removal
        {
            int removals = smallJmp ? 2: 4;
            do
            {
                const int bucketIdx1 = rnBucket(g);
                const size_t numMoved = pxp[bucketIdx1];
                if (sol[bucketIdx1].size() >= numMoved)
                {
                    for (size_t i = 0; i < numMoved; i++)
                    {
                        const int i1 = sol[bucketIdx1].empty()
                            ? 0 : rnPizzaID(g) % sol[bucketIdx1].size();
                        //const int i2 = avPizzas.empty() ? 0 : rnPizzaID(g) % avPizzas.size();
                        auto a1 = std::next(sol[bucketIdx1].begin(), i1);
                        auto a2 = std::next(sol[bucketIdx1].begin(), i1 + 1);
                        //auto b1 = std::next(avPizzas.begin(), i2);
                        avPizzas.insert(avPizzas.end(), a1, a2);
                        sol[bucketIdx1].erase(a1, a2);
                        ++attrem;
                    }
                }
                --removals;
            } while (removals > 0
                && (sol[0].size() + sol[1].size() + sol[2].size()) > 0);
        }
        
        if (rnProb(g) < 0.20) //adding
        {
            int atp = smallJmp ? 1 : 1 + attrem;
            do
            {
                const int bucketIdx1 = rnBucket(g); // source or dest
                const size_t numMoved = pxp[bucketIdx1];
                if (avPizzas.size() >= numMoved && ((sol[bucketIdx1].size() / pxp[bucketIdx1]) < T[bucketIdx1]))
                {
                    for (size_t i = 0; i < numMoved; i++)
                    {
                        const int i2 = sol[bucketIdx1].empty() ? 0 : rnPizzaID(g) % sol[bucketIdx1].size();
                        auto a1 = avPizzas.begin();
                        auto a2 = std::next(avPizzas.begin());
                        auto b2 = std::next(sol[bucketIdx1].begin(), i2);
                        sol[bucketIdx1].insert(b2, a1, a2);
                        avPizzas.erase(a1, a2);
                    }
                }
                --atp;
            } while (0 < atp &&
                (sol[0].size() + sol[1].size() + sol[2].size()) < M3);
        }
        int mrp = 1 + itID % 4;
        do
        {
            if (rnProb(g) < 0.80)
            {
                const int bucketIdx0 = rnBucket(g);
                if (!sol[bucketIdx0].empty())
                {
                    const int i1 = sol[bucketIdx0].empty() ? 0 : rnPizzaID(g) % sol[bucketIdx0].size();
                    const int i2 = sol[bucketIdx0].empty() ? 0 : rnPizzaID(g) % sol[bucketIdx0].size();
                    int n1 = i1 / pxp[bucketIdx0];
                    int n2 = i2 / pxp[bucketIdx0];
                    if (n1 != n2)
                    {
                        auto b1 = std::next(sol[bucketIdx0].begin(), i1);
                        auto b2 = std::next(sol[bucketIdx0].begin(), i2);
                        std::swap(b1, b2);
                    }
                }
            }
                
            if (rnProb(g) < 0.33)
            {
                const int bucketIdx0 = rnBucket(g); // source or dest
                const int bucketIdx2 = rnBucket(g);
                const int i1 = sol[bucketIdx0].empty() ? 0 : rnPizzaID(g) % sol[bucketIdx0].size();
                const int i2 = sol[bucketIdx2].empty() ? 0 : rnPizzaID(g) % sol[bucketIdx2].size();
                if (!sol[bucketIdx0].empty()
                    && !sol[bucketIdx2].empty()
                    && (bucketIdx2 != bucketIdx0))
                {
                    auto b1 = std::next(sol[bucketIdx0].begin(), i1);
                    auto b2 = std::next(sol[bucketIdx2].begin(), i2);
                    int t1 = *b1;
                    int t2 = *b2;
                    *b2 = t1;
                    *b1 = t2;
                }
            };
            --mrp;
        } while (0< mrp);
        if (rnProb(g) < 0.2 && !avPizzas.empty())
        {
            std::rotate(avPizzas.begin(), std::next(avPizzas.begin()), avPizzas.end());
        }
        // update info
        numOrders = calculateNumOrders();
        score = calculateTotalScore();
    }
    // Helper function to print the solution
    void print()
    {
        std::cout << "Delivering " << numOrders << " orders:" << std::endl;
        cout << "Score: " << score << endl;
        for (auto p : pxp)
        {
            const size_t numPizzas = sol[p - 2].size();
            int j = 0;
            for (auto pz : sol[p - 2])
            {
                if (j % p == 0 && j < numPizzas)
                {
                    std::cout << p;
                }
                std::cout << " " << pz;
                ++j;
                if (j > 0 && j % p == 0)
                {
                    std::cout << endl;
                }
            }
        }
    }
    // Save solution to a file.
    // The name of the file is SCENARIO + "_" + ".out"
    void saveSolutionToFile()
    {
        // print to a file
        ofstream outFile;
        outFile.open(iFileName + "_.out");
        size_t s_offset = 0;
        outFile << "Score: " << score << endl; // to be removed from the output file before sending to Google!
        outFile << numOrders << endl;
        for (auto p : pxp)
        {
            const size_t numPizzas = sol[p - 2].size();
            int j = 0;
            for (auto pz : sol[p-2])
            {
                if (j % p == 0 && j < numPizzas)
                {
                    outFile << p;
                }
                outFile << " " << pz;
                ++j;
                if (j > 0 && j % p == 0)
                {
                    outFile << endl;
                }
            }
        }
        outFile.close();
    }
    std::list<int> avPizzas; // a queue containing available pizzas
    std::map<int, std::list<int> > sol; // a map to store the orders classified by teams size
    size_t score; // score of the current solution
    size_t numOrders; // the total number of the orders
};

#The Simulated Annealing algorithm

// Using smart pointers, it is straightforward and faster
// to replace local solution with a better solution.
using TSolPtr = std::shared_ptr<TSolCnt>;
void orderPizzas()
{
    const int numEl{ static_cast<int>(pizzas.size()) };
    // This is used to choose randomly a pizza to order or remove
    std::uniform_int_distribution<int> rnPizzaID(0, numEl - 1);
    // Counters 
    int numItBetweenImprovement = 0;
    int cntIters{ 0 };
    cout << "...ok! Ready to start..." << endl;
    // make local initial solution
    TSolPtr localSol = std::make_shared<TSolCnt>();
    localSol->saveSolutionToFile();
    // this is the best solution until now found... so let's save it!
    TSolPtr savedSol = std::make_shared<TSolCnt>(*localSol);
    // Print some data...
    size_t currentSize = savedSol->numOrders;
    cout << "Initial score: " << savedSol->score << "tsize: " << currentSize << endl;
    if (currentSize > T[0] + T[1] + T[2])
    {
        cout << "Initial solution has wrong size; max size: " << T[0] + T[1] + T[2] << endl;
        return;
    }
#ifdef _DEBUG
    savedSol->print();
#endif // _DEBUG
    double temperature = T0; // initialize temperature
    while (numItBetweenImprovement < 5'000'000)
    {
        // Calculating new temperature
        ++cntIters;
        temperature = T0 * exp(-ae * cntIters);
        // creating new solutions from current one!
        TSolPtr bestNb = std::make_shared<TSolCnt>(); // with zero score
        for (auto i = 0; i < numMaxItemsToCheck; i++)
        {
            // Creating a copy of the local solution
            TSolPtr nb = std::make_shared<TSolCnt>(*localSol);
            if (nb)
            {
                // Mutate the new solution
                nb->mutate(rnPizzaID, numItBetweenImprovement );
                // Checking if the new solution is better
                if (nb->score > bestNb->score || ( nb->score == bestNb->score && nb->numOrders < bestNb->numOrders ) )
                {
                    bestNb.swap(nb);
                }
            }
        }
        const int64_t deltaEnergy = bestNb->score - savedSol->score;
        // If a better solution is found
        if (bestNb->score>0 && deltaEnergy > 0)
        {
            savedSol.swap(bestNb);
            localSol = std::make_shared<TSolCnt>(*savedSol);
            savedSol->saveSolutionToFile();
            cout << "New max score: " << savedSol->score << "tsize: " << savedSol->sol[0].size()/2 
                << ", " << savedSol->sol[1].size()/3 << ", " << savedSol->sol[2].size()/4
                << " [" << savedSol->sol[0].size() + savedSol->sol[1].size() + savedSol->sol[2].size() 
                << ", "<< savedSol->avPizzas.size() << "]";
            cout << "tTemperature: " << temperature;
            cout << "tdelta: " << deltaEnergy;
            cout << "tnumItBetweenImprovements: " << numItBetweenImprovement << endl;
            numItBetweenImprovement = 0;
#ifdef _DEBUG
            savedSol->print();
#endif // _DEBUG
        }
        else
        {
            // check if it can be accepted
            const auto probAccept = exp(deltaEnergy / temperature);
            if (rnProb(g) < probAccept) // accepted
            {
                localSol.swap(bestNb);
                cout << "Accepted lower score: " << localSol->score << "tsize: " << localSol->numOrders;
            }
            else
            {
                // Reset local solution to be equal to the best one found until now
                localSol = std::make_shared<TSolCnt>(*savedSol);
                cout << "Unaccepted lower score: " << bestNb->score;
            }
            cout << "tTemperature: " << temperature;
            cout << "tProbAccept: " << probAccept;
            cout << "tnumIts: " << numItBetweenImprovement << "r";
            ++numItBetweenImprovement;
        }
    }
#ifdef _DEBUG
    savedSol->print();
#endif // _DEBUG
}

#The main

int main(int argc, char* argv[])
{
    // Reading algorithm 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();
    // Calculate the score of each pizza
    pzScore.resize(M,0);
    for (size_t i = 0; i < M; i++)
    {
        for (size_t j = 0; j < M; j++)
        {
            if (i != j)
            {
                std::vector<int> v(pizzas[i].size() + pizzas[j].size(), 0);
                auto it = std::set_difference(pizzas[i].begin(), pizzas[i].end(),
                    pizzas[j].begin(), pizzas[j].end(), v.begin());
                v.resize(it - v.begin());
                pzScore[i] += v.size();
            }
        }
    }
    auto start = chrono::steady_clock::now();
#ifdef _DEBUG
    //cout << "Pizzas:n";
    //for (auto& item : pizzas)
    //{
    //    cout << item.size();
    //
    //    for (auto item2 : item)
    //    {
    //        cout << " " << item2;
    //    }
    //    cout << endl;
    //}
#endif // _DEBUG
    orderPizzas();
    auto end = chrono::steady_clock::now();
    cout << "Elapsed time in nanoseconds : "
        << chrono::duration_cast<chrono::nanoseconds>(end - start).count()
        << " ns" << endl;
    cout << "Elapsed time in microseconds : "
        << chrono::duration_cast<chrono::microseconds>(end - start).count()
        << " microseconds" << endl;
    cout << "Elapsed time in milliseconds : "
        << chrono::duration_cast<chrono::milliseconds>(end - start).count()
        << " ms" << endl;
    cout << "Elapsed time in seconds : "
        << chrono::duration_cast<chrono::seconds>(end - start).count()
        << " sec" << endl;
    return 0;
}

#Algorithm description

A flowchart of the main algorithm can be found in the post describing the algorithm for the “More Pizza” problem.

• the representation of the solution (a map of lists rather than a vector of integers)
• the function to mutate the current solution and generate a new one
• the function to calculate the score of the solution

#Conclusion