Baby_Heels.cpp

/*

There are two types of professional wrestlers: “babyfaces”
(“good guys”) and “heels”(“bad guys”). Between any pair of
professional wrestlers, there may or may not be a
rivalry.Suppose we have n professional wrestlers and we have a
list of r pairs of wrestlers for whichthere are rivalries. Give an
algorithm that determines whether it is possible to
designatesome of the wrestlers as babyfaces and the
remainder as heels such that each rivalry isbetween a babyface
and a heel. If it is possible to perform such a designation,
youralgorithm should produce it.

*/

#include <iostream>
#include <utility>
#include <list>
#include <algorithm>
#include <iterator>


class Competition
{
    enum class Teams
    {
        babyface,
        heel,
        nope
    };
    class Wrestler
    {
        Teams team;
        size_t _id;

      public:
        Wrestler(size_t _id) : _id(_id)
        {
            team = Teams::nope;
        }
        void set_team(Teams team)
        {
            this->team = team;
        }
        Teams get_team() const
        {
            return this->team;
        }
        size_t get_id() const
        {
            return this->_id;
        }
    };
    std::list<Wrestler *> *graph;
    const size_t N;
    bool isPossible(int, Teams);
    bool isCompetitionPossibleUtil(size_t);
    bool add_all() { return true; }
    void print_teams();

  public:
    Competition(size_t);
    bool add(std::pair<size_t, size_t>);
    template <typename T, typename... Types>
    bool add_all(T t, Types... pack);
    bool isCompetitionPossible();
    Competition *show_competition_schedule();
    ~Competition();
};
Competition::Competition(size_t N) : N(N)
{
    graph = new std::list<Wrestler *>[N];

    for (size_t i = 0; i < N; i++)
    {
        graph[i].push_back(new Wrestler(i));
    }
}

Competition::~Competition()
{
    for (size_t i = 0; i < N; i++)
    {
        delete graph[i].front();
    }
    delete[] graph;
}

bool Competition::add(std::pair<size_t, size_t> consent)
{
    if (consent.first >= N || consent.second >= N)
        return false;

    graph[consent.first].push_back(graph[consent.second].front());
    graph[consent.second].push_back(graph[consent.first].front());

    return true;
}

template <typename T, typename... Types>
bool Competition::add_all(T t, Types... pack)
{
    if (!add(t))
        return false;
    return add_all(pack...);
}

void Competition::print_teams()
{
    std::cout << "\nBaby-Faces:";
    for (size_t i = 0; i < N; i++)
    {
        const auto it = graph[i].front();
        if (it->get_team() == Teams::babyface)
            std::cout << "[" << it->get_id() << "],";
    }
    std::cout << "\nHeels:";
    for (size_t i = 0; i < N; i++)
    {
        const auto it = graph[i].front();
        if (it->get_team() == Teams::heel)
            std::cout << "[" << it->get_id() << "],";
    }
    std::cout << std::endl;
}

bool Competition::isPossible(int _id, Teams pre)
{
    auto it = graph[_id].begin();
    std::advance(it, 1);
    return !std::any_of(it, graph[_id].end(), [&pre](Wrestler *w) {
        return w->get_team() == pre;
    });
}

bool Competition::isCompetitionPossibleUtil(size_t vertex)
{
    if (vertex == N)
        return true;
    if (isPossible(vertex, Teams::heel))
    {
        graph[vertex].front()->set_team(Teams::heel);
        if (isCompetitionPossibleUtil(vertex + 1))
            return true;
        graph[vertex].front()->set_team(Teams::nope);
    }
    if (isPossible(vertex, Teams::babyface))
    {
        graph[vertex].front()->set_team(Teams::babyface);
        if (isCompetitionPossibleUtil(vertex + 1))
            return true;
        graph[vertex].front()->set_team(Teams::nope);
    }
    return false;
}

bool Competition::isCompetitionPossible()
{

    if (isCompetitionPossibleUtil(0))
    {
        print_teams();
        return true;
    }

    std::clog << "It is not possible!\n";
    return false;
}

Competition *Competition::show_competition_schedule()
{
    for (size_t i = 0; i < N; i++)
    {
        for (const auto j : graph[i])
        {
            std::cout << j->get_id() << " ->";
        }
        std::cout << "\n";
    }
    return this;
}

int main()
{
    const size_t N = 7;
    Competition *comp = new Competition(N);
    /*
       comp->add(std::make_pair(0,6));
       comp->add(std::make_pair(6,2));
       comp->add(std::make_pair(5,6));
       comp->add(std::make_pair(2,3));
       comp->add(std::make_pair(1,3));
       comp->add(std::make_pair(1,4));
     */

    comp->add_all(std::make_pair(0, 6),
                  std::make_pair(6, 2),
                  std::make_pair(5, 6),
                  std::make_pair(2, 3),
                  std::make_pair(1, 3),
                  std::make_pair(1, 4));

    comp->show_competition_schedule()->isCompetitionPossible();

    delete comp;
    return 0;
}