Zadanie

Przedstawione zadanie zainspirowane zostało wywiadem na kanale Joma Tech.

Poniższy kod źródłowy symuluje mecz siatkówki:

#include <iostream>
#include <random>
#include <algorithm>
#include <unordered_map>

constexpr int TEAM_A = 0;
constexpr int TEAM_B = 1;
constexpr int SETS_TO_WIN = 3;

std::unordered_map<int, std::string>  teams {{ TEAM_A, "TEAM_A"},
                                             { TEAM_B, "TEAM_B"}};

std::vector<int> playVolleyBallMatch(int homeTeam, int guestTeam)
{
    std::vector<int> sets;

    std::random_device rd;
    std::mt19937 gen(rd());
    std::bernoulli_distribution d(0.5);

    do
    {
        sets.push_back(d(gen) ? homeTeam : guestTeam);
    } 
    while (std::count(std::begin(sets),
                      std::end(sets), homeTeam) == SETS_TO_WIN ||
           std::count(std::begin(sets),
                      std::end(sets), guestTeam) == SETS_TO_WIN);

    return sets;
};

int main()
{
    auto sets = playVolleyBallMatch(TEAM_A, TEAM_B);

    // Implement your solution here
    
}

Uruchom w edytorze

Mecz siatkówki wygrywa drużyna, która jako pierwsza wygra trzy sety (wynik 3 : 0 lub 0 : 3). W przypadku remisu (2 : 2), rozgrywany jest dodatkowy, piąty set, czyli ”tie-break” (w piłce nożnej nazwalibyśmy to dogrywką). Inaczej mówiąc taki mecz obejmuje od 3 (minimalnie) do 5 (maksymalnie) setów. W naszym przypadku zwycięzcy kolejnych setów zwracani są w kontenerze std::vector (plik nagłówkowy vector) po wykonaniu symulacji przez funkcję playVolleyBallMatch (jej implementacja nie jest tutaj istotna). Jak już wiadomo kontener ten może przechowywać od 3 do 5 wpisów.

Zadanie polega na ustaleniu zwycięzcy meczu na podstawie otrzymanego kontenera std::vector, z zapisanymi zwycięzcami poszczególnych setów.

Rozwiązanie

Algorytm std::count

Naturalnym rozwiązaniem wydaje się być policzenie ile setów wygrała każda z drużyn. Oczywiście zwycięska drużyna wygrywa ich więcej (dokładnie 3). Do policzenia setów wykorzystamy algorytm std::count (plik nagłówkowy algorithm):

#include <iostream>
#include <random>
#include <algorithm>
#include <unordered_map>

constexpr int TEAM_A = 0;
constexpr int TEAM_B = 1;
constexpr int SETS_TO_WIN = 3;

std::unordered_map<int, std::string>  teams {{ TEAM_A, "TEAM_A"},
                                             { TEAM_B, "TEAM_B"}};

std::vector<int> playVolleyBallMatch(int homeTeam, int guestTeam)
{
    std::vector<int> sets;

    std::random_device rd;
    std::mt19937 gen(rd());
    std::bernoulli_distribution d(0.5);

    do
    {
        sets.push_back(d(gen) ? homeTeam : guestTeam);
    } 
    while (std::count(std::begin(sets),
                      std::end(sets), homeTeam) == SETS_TO_WIN ||
           std::count(std::begin(sets),
                      std::end(sets), guestTeam) == SETS_TO_WIN);

    return sets;
};

int main()
{
    auto sets = playVolleyBallMatch(TEAM_A, TEAM_B);

    // Implement your solution here
    auto a = std::count(std::begin(sets), std::end(sets), TEAM_A);
    auto b = std::count(std::begin(sets), std::end(sets), TEAM_B);
    auto winner = (a > b) ? a : b;

    std::cout << "The winner is team : " << teams[winner] << '\n';
}

Uruchom w edytorze

The winner is team : TEAM_B

Ponieważ wiemy ile setów wygrała każda z drużyn (zmienna ab), moglibyśmy jako bonus wyświetlić wynik meczu (nie jest to jednak celem tego zadania). Przedstawione rozwiązanie cechuje się liniową złożonością O(n), co wynika bezpośrednio z implementacji algorytm std::count. Można zadać sobie pytanie: czy zadanie wyznaczenia zwycięzcy meczu w siatkówkę można wykonać efektywniej (z jeszcze mniejszą złożonością) ?

Metoda std::vector::back

Mecz siatkówki wygrywa oczywiście drużyna, która wygra więcej setów (inaczej mówiąc, drużyna która pierwsza wygra 3 sety). Jak się okazuje znając zasady tej gry nie musimy zliczać poszczególnych setów, tak jak w poprzednim rozwiązaniu. Okazuje się bowiem, że zwycięzcą meczu będzie drużyna, która wygra ostatni set. Wniosek ten prowadzi nas do finalnego rozwiązania, które cechuje się stałą złożonością O(1). W tym celu wykorzystamy metodę std::vector::back, która w stałym czasie zwróci nam referencję do ostatniego elementu (zwycięzcy ostatniego seta) otrzymanego kontenera typu std::vector:

#include <iostream>
#include <random>
#include <algorithm>
#include <unordered_map>

constexpr int TEAM_A = 0;
constexpr int TEAM_B = 1;
constexpr int SETS_TO_WIN = 3;

std::unordered_map<int, std::string>  teams {{ TEAM_A, "TEAM_A"},
                                             { TEAM_B, "TEAM_B"}};

std::vector<int> playVolleyBallMatch(int homeTeam, int guestTeam)
{
    std::vector<int> sets;

    std::random_device rd;
    std::mt19937 gen(rd());
    std::bernoulli_distribution d(0.5);

    do
    {
        sets.push_back(d(gen) ? homeTeam : guestTeam);
    } 
    while (std::count(std::begin(sets),
                      std::end(sets), homeTeam) == SETS_TO_WIN ||
           std::count(std::begin(sets),
                      std::end(sets), guestTeam) == SETS_TO_WIN);

    return sets;
};

int main()
{
    auto sets = playVolleyBallMatch(TEAM_A, TEAM_B);

    // Implement your solution here
    auto winner = sets.back();

    std::cout << "The winner is team : " << teams[winner] << '\n';
}

Uruchom w edytorze

The winner is team : TEAM_A

Rozwiązanie to jest więc prostsze i wydajniejsze w porównaniu do poprzedniego (naiwnego), opartego na algorytmie std::count.

Jak więc widać, czasem znajomość reguł gry okazuje się bardzo przydatna 🙂