guessing who picked you in secret santa

secret_santa.cpp

#include <algorithm>
#include <iostream>
#include <vector>


std::vector<int> create_graph(int sz)
{
    std::vector<int> graph;
    graph.reserve(sz);
    for (int i=0; i<sz; ++i)
        graph.push_back(i);
    return graph;
}

int source(const std::vector<int>& graph, int target)
{
    for (size_t i=0; i<graph.size(); ++i)
    {
        if (graph[i] == target)
            return i;
    }
    return -1;
}

void simulate_drawing(std::vector<int>* people)
{
    std::random_shuffle(people->begin(), people->end());
}

class Strategy
{
  public:
    virtual int guess(const std::vector<int>& graph, int guesses, int start) const = 0;
    virtual ~Strategy() {}
};

class FollowChain : public Strategy
{
  public:
    int guess(const std::vector<int>& graph, int guesses, int start) const
    {
        int guess = start, next;
        while (guesses --> 0)
        {
            next = graph[guess];
            if (next == start)
                break;
            guess = next;
        }
        return guess;
    }
};

class Random : public Strategy
{
  public:
    int guess(const std::vector<int>& graph, int guesses, int start) const
    {
        std::vector<int> remaining(graph); // sequence of random quesses
        remaining.erase(std::find(remaining.begin(), remaining.end(), start));
        std::random_shuffle(remaining.begin(), remaining.end());

        while (guesses-- > 0 && !remaining.empty())
        {
            int guess = remaining.back();
            remaining.pop_back();
            if (graph[guess] == start)
                return guess;
        }
        return -1;
    }
};

double evaluate_strategy(int sz, int guesses, int iters, const Strategy &strategy)
{
    std::vector<int> graph = create_graph(sz);
    int correct = 0;
    for (int i=0; i<iters; ++i) {
        simulate_drawing(&graph);
        int res = strategy.guess(graph, guesses, 0);
        if (res == source(graph, 0))
            ++correct;
    }
    return (double) correct / iters;
}

int main(int argc, char** argv)
{
    std::cout << "chain strategy: " << evaluate_strategy(41, 20, 1000000, FollowChain()) << '\n';
    std::cout << "random strategy: " << evaluate_strategy(41, 20, 1000000, Random()) << '\n';

    return EXIT_SUCCESS;
}