Here is my final solution, and I think this is the one, it works on big numbers of players in a very fast time, I really enjoyed this one ;)
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.IO;
namespace SplitTeams
{
class Program
{
class Player
{
public string Name { get; set; }
public int Rating { get; set; }
}
private static int _TotalPlayers;
private static Random rnd = new Random(DateTime.Now.Millisecond);
private static Player[] _Players;
private static bool FindSwappables(Player[] team1, Player[] team2, int diff, out int player1, out int player2)
{
player1 = 0;
player2 = 0;
int? maxDiff = null;
double halfDiff = Math.Abs(Math.Ceiling((float)diff / 2));
for (int i = 0; i < team1.Length; i++)
{
for (int j = 0; j < team2.Length; j++)
{
int currentDiff = team1[i].Rating - team2[j].Rating;
if (currentDiff > 0 && diff > 0 || currentDiff < 0 && diff < 0)//elligible swap (same sign)
{
currentDiff = Math.Abs(currentDiff);
if (currentDiff <= halfDiff && (!maxDiff.HasValue || currentDiff > maxDiff))
{
maxDiff = currentDiff;
player1 = i;
player2 = j;
}
}
}
}
return maxDiff != null;
}
private static void Cut(Player[] team1, Player[] team2)
{
for (int i = 0; i < _Players.Length / 2; i++)
team1[i] = _Players[i];
for (int i = _Players.Length / 2, counter = 0; i < _Players.Length; i++, counter++)
team2[counter] = _Players[i];
}
private static void Swap(Player[] team1, Player[] team2, int team1Index, int team2Index, ref int sum1, ref int sum2)
{
Player temp = team1[team1Index];
team1[team1Index] = team2[team2Index];
team2[team2Index] = temp;
sum1 += team1[team1Index].Rating - team2[team2Index].Rating;
sum2 += team2[team2Index].Rating - team1[team1Index].Rating;
}
private static void Split(Player[] team1, Player[] team2)
{
Cut(team1, team2);
int s1, s2, sum1, sum2;
sum1 = team1.Sum(x => x.Rating);
sum2 = team2.Sum(x => x.Rating);
int diff = sum1 - sum2;
while (diff != 0 && FindSwappables(team1, team2, diff, out s1, out s2))
{
Swap(team1, team2, s1, s2, ref sum1, ref sum2);
diff = sum1 - sum2;
}
}
#region Util
private static void GeneratePlayers()
{
DateTime start = DateTime.Now;
_Players = new Player[_TotalPlayers];
for (int i = 0; i < _Players.Length; i++)
_Players[i] = new Player { Name = "Player" + i.ToString(), Rating = rnd.Next(2000) };
DateTime end = DateTime.Now;
TimeSpan diff = end.Subtract(start);
Console.WriteLine(string.Format("Generated {0} players in {1} milliseconds", _TotalPlayers, diff.TotalMilliseconds));
}
private static void SplitAndReporttoConsole()
{
Player[] team1 = new Player[_TotalPlayers / 2];
Player[] team2 = new Player[_TotalPlayers / 2];
DateTime start = DateTime.Now;
Split(team1, team2);
DateTime end = DateTime.Now;
TimeSpan diff = end.Subtract(start);
Console.WriteLine(string.Format("Split {0} players into 2 {1} player teams in {2} milliseconds.", _TotalPlayers, _TotalPlayers / 2, diff.TotalMilliseconds));
float sum1 = team1.Sum(x => x.Rating);
float sum2 = team2.Sum(x => x.Rating);
float perc1 = (sum1 * 100) / (sum1 + sum2);
float perc2 = (sum2 * 100) / (sum1 + sum2);
Console.WriteLine(string.Format("Team 1: ({0:f2}%)", perc1));
foreach (Player p in team1)
Console.WriteLine(string.Format("Name: {0}, Rating: {1}", p.Name, p.Rating));
Console.WriteLine(string.Format("Team 2: ({0:f2}%)", perc2));
foreach (Player p in team2)
Console.WriteLine(string.Format("Name: {0}, Rating: {1}", p.Name, p.Rating));
}
private static void SplitAndReportToFile()
{
FileInfo fi = new FileInfo("C:\\output.txt");
FileStream fs = null;
if (!fi.Exists)
fs = new FileStream("C:\\output.txt", FileMode.Create);
else
fs = File.Open("C:\\output.txt", FileMode.Truncate);
StreamWriter sw = new StreamWriter(fs);
Player[] team1 = new Player[_TotalPlayers / 2];
Player[] team2 = new Player[_TotalPlayers / 2];
DateTime start = DateTime.Now;
Split(team1, team2);
DateTime end = DateTime.Now;
TimeSpan diff = end.Subtract(start);
Console.WriteLine(string.Format("Split {0} players into 2 {1} player teams in {2} milliseconds.", _TotalPlayers, _TotalPlayers / 2, diff.TotalMilliseconds));
float sum1 = team1.Sum(x => x.Rating);
float sum2 = team2.Sum(x => x.Rating);
float perc1 = (sum1 * 100) / (sum1 + sum2);
float perc2 = (sum2 * 100) / (sum1 + sum2);
sw.WriteLine(string.Format("Team 1: ({0:f2}%)", perc1));
foreach (Player p in team1)
sw.WriteLine(string.Format("Name: {0}, Rating: {1}", p.Name, p.Rating));
sw.WriteLine(string.Format("Team 2: ({0:f2}%)", perc2));
foreach (Player p in team2)
sw.WriteLine(string.Format("Name: {0}, Rating: {1}", p.Name, p.Rating));
sw.Close();
fs.Close();
}
private static void InsureTotalPlayers(string[] args)
{
if (args.Length > 0)
int.TryParse(args[0], out _TotalPlayers);
if (_TotalPlayers % 2 != 0)
throw new Exception("Invalid PLAYER_COUNT, must be even.");
}
#endregion
static void Main(string[] args)
{
/* _Players = new Player[]
{
new Player{Name="A", Rating=500},
new Player{Name="A", Rating=1},
new Player{Name="A", Rating=233},
new Player{Name="A", Rating=10},
new Player{Name="A", Rating=71},
new Player{Name="A", Rating=112},
new Player{Name="A", Rating=9},
new Player{Name="A", Rating=46}
};*/
_TotalPlayers = 1000;
_Players = new Player[_TotalPlayers];
for (int i = 0; i < _TotalPlayers; i++)
_Players[i] = new Player { Name = i.ToString(), Rating = i };
InsureTotalPlayers(args);
GeneratePlayers();
SplitAndReportToFile();
Console.Write("Press any key to exit.");
Console.Read();
}
}
}
You can generate players randomly or have them preset like in the above code ( I used arithma's suggestion and got a clear cut split 50/50).
Generated 1000 players in 0 milliseconds
Split 1000 players into 2 500 player teams in 41.9922 milliseconds.
[Edit]Modified to avoid overflow (need to test for more extreme cases).[/Edit]
