team_balance.cpp

//
//  main.cpp
//  Team Balancing
//
//  Created by Brooke, Fabien
//

#include <iostream>
#include <string>
#include <vector>
#include <cmath>

using namespace std;

struct unit
{
    int attack;
    int defense;
    int number;
};

struct team
{
    int attack = 0;
    int defense = 0;
    vector<unit> units;
};

int calculateTeamRating(team &t);
void selectTeamForUnit(unit &player, vector<team> &teams);
void addUnitToTeam(unit &player, team &team);
void setLowestAndHighestTeams(vector<team> &teams);
void optimizeTeamBalance(vector<team> &teams);
void printTeams(vector<team> &teams);

// once we are within a range of imbalance tolerance
// we can stop attempting to improve the balance further
const int IMBALANCE_TOLERANCE = 3;

team *lowestTeam;
team *highestTeam;

int main()
{
    // read number of teams from first line
    int numTeams;
    cin >> numTeams;
    vector<team> teams(numTeams);
    
    // read unit stats
    int unitNumber = 0;
    int unitAttack;
    int unitDefense;
    char separator;
    
    while (cin >> unitAttack) {
        cin >> separator;
        cin >> unitDefense;
        
        // create a new unit and place into team that has
        // the lowest calculated rating (attack + defense)
        unit player;
        player.attack = unitAttack;
        player.defense = unitDefense;
        player.number = unitNumber;

        selectTeamForUnit(player, teams);
        
        unitNumber++;
    }
    
    // once we know all the units we can better balance the teams
    // this optimization can be skipped if requirement for balance
    // is less strict
    optimizeTeamBalance(teams);
    
    printTeams(teams);
    
    return 0;
}

int calculateTeamRating(team &t)
{
    return t.attack + t.defense;
}

void selectTeamForUnit(unit &player, vector<team> &teams)
{
    setLowestAndHighestTeams(teams);
    addUnitToTeam(player, *lowestTeam);
}

void addUnitToTeam(unit &player, team &team)
{
    team.attack += player.attack;
    team.defense += player.defense;
    team.units.push_back(player);
}

void setLowestAndHighestTeams(vector<team> &teams)
{
    if (teams.size() < 1) {
        return;
    }
    
    team &firstTeam = teams.at(0);
    int rating = calculateTeamRating(firstTeam);
    int minRating = rating;
    int maxRating = rating;
    lowestTeam = &firstTeam;
    highestTeam = &firstTeam;
    
    for (auto &team : teams) {
        int rating = calculateTeamRating(team);
        if (rating < minRating) {
            minRating = rating;
            lowestTeam = &team;
        }
        else if (rating > maxRating) {
            maxRating = rating;
            highestTeam = &team;
        }
    }
}

///
/// This optimization simply tries to improve the balance by moving units
/// from the current highest rated team to the current lowest rated team.
///
void optimizeTeamBalance(vector<team> &teams)
{
    setLowestAndHighestTeams(teams);
    
    int imbalance = calculateTeamRating(*highestTeam) - calculateTeamRating(*lowestTeam);
    
    // see if moving any units from highest team to lowest team improves balance
    for (int i = 0; i < highestTeam->units.size() && imbalance > IMBALANCE_TOLERANCE; i++) {
        
        // test using copies of the teams
        team lowest(*lowestTeam);
        team highest(*highestTeam);
        
        // move unit from highest to lowest team and recalculate imbalance
        unit &movingPlayer = highest.units.at(i);
        addUnitToTeam(movingPlayer, lowest);
        highest.attack -= movingPlayer.attack;
        highest.defense -= movingPlayer.defense;
        highest.units.erase(highest.units.begin() + i);
        
        // if we have improved the balance update the original teams
        int newImbalance = abs(calculateTeamRating(highest) - calculateTeamRating(lowest));
        if (newImbalance < imbalance) {
            imbalance = newImbalance;

            lowestTeam->attack = lowest.attack;
            lowestTeam->defense = lowest.defense;
            lowestTeam->units = lowest.units;
            
            highestTeam->attack = highest.attack;
            highestTeam->defense = highest.defense;
            highestTeam->units = highest.units;
            
            i--;
        }
    }
}

void printTeams(vector<team> &teams)
{
    for (auto &team : teams) {
        for (int i = 0; i < team.units.size(); i++) {
            cout << team.units.at(i).number;
            if (i != team.units.size() - 1) {
                cout << ", ";
            }
        }
        cout << endl;
    }
}