Algo-Challenges/roulette-wheel.cpp at master · Feez/Algo-Challenges · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <algorithm>
#include <random>

struct Agent
{
    int id{};
    int score{};
};

std::vector<Agent> roulette_wheel(std::vector<Agent> const &agents)
{
    std::vector<int> scores;

    std::transform(agents.cbegin(),
                   agents.cend(),
                   std::back_inserter(scores),
                   [](Agent const &a) { return a.score; });

    std::vector<int> part_sums;

    std::partial_sum(scores.cbegin(),
                     scores.cend(),
                     std::back_inserter(part_sums));

    std::random_device rd;
    std::mt19937 eng(rd());
    std::uniform_int_distribution<> distr(0, part_sums.back() - 1);

    std::vector<Agent> results;

    std::generate_n(std::back_inserter(results), agents.size(),
                    [&]()
                    {
                        const auto iter = std::upper_bound(part_sums.cbegin(),
                                                           part_sums.cend(),
                                                           distr(eng));

                        return agents[std::distance(part_sums.cbegin(), iter)];
                    });

    return results;
}

int main()
{
    std::vector<Agent> const test_agents =
        {
            {0, 2},
            {1, 10},
            {2, 30},
            {3, 8},
            {4, 4}
        };

    for (auto const &agent : roulette_wheel(test_agents))
    {
        std::cout << "ID: " << agent.id <<
                     ", Score: " << agent.score
                     << std::endl;
    }
}