I know I thought the last one was my best, well this is MUCH more performant taking advantage of multiple shortcuts and also has a progress indication.
To note about this:
* the list is cut in half into 2 sorted lists using the Cut method
* the FindSwappables method loops through the players in team 1 trying to find the best player_team1/player_team2 pair that if swapped will get us closer to a solution (less difference between the sums of the ratings of the 2 team)
* the method FindPlayerToSwapWith finds the best choice from team 2 to swap with a preselected player from team 1. This makes use of the fact that the team2 list is sorted and does a binary search to try and locate a player.
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 long 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, long diff, out int player1, out int player2)
{
player1 = 0;
player2 = 0;
long? maxDiff = null;
long halfDiff = Convert.ToInt64(Math.Abs(Math.Ceiling((double)diff / 2)));
for (int i = 0; i < team1.Length; i++)
{
long rating = team1[i].Rating;
int? foundIndex = null;
if (diff > 0) //S1 > S2
foundIndex = FindPlayerToSwapWith(team2, 0, team2.Length - 1, rating - (halfDiff > rating ? 0 : halfDiff), null, rating);
else
foundIndex = FindPlayerToSwapWith(team2, 0, team2.Length - 1, team1[i].Rating + halfDiff, rating, null);
if (foundIndex.HasValue)
{
long currentDiff = team1[i].Rating - team2[foundIndex.Value].Rating;
currentDiff = Math.Abs(currentDiff);
if (currentDiff != 0 && currentDiff <= halfDiff && (!maxDiff.HasValue || currentDiff > maxDiff))
{
maxDiff = currentDiff;
player1 = i;
player2 = foundIndex.Value;
}
}
}
return maxDiff != null;
}
private static int? FindPlayerToSwapWith(Player[] list, int start, int end, long value, long? lowerBound, long? upperBound)
{
int diff = end - start;
bool acceptHigher = lowerBound.HasValue;
bool acceptLower = upperBound.HasValue;
if (value == list[start].Rating || (acceptHigher && lowerBound < list[start].Rating)) return start;
if(value == list[end].Rating || (acceptLower && upperBound > list[end].Rating)) return end;
if (acceptLower && diff == 1) return start;
if (acceptHigher && diff == 1) return end;
if (end <= start || value < list[start].Rating || value > list[end].Rating) return null;
if (list[start + diff / 2].Rating > value)
end = start + diff / 2;
else
start = start + diff / 2;
return FindPlayerToSwapWith(list, start, end, value, lowerBound, upperBound);
}
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];
team1 = team1.OrderBy(x => x.Rating).ToArray();
team2 = team2.OrderBy(x => x.Rating).ToArray();
}
private static void Swap(Player[] team1, Player[] team2, int team1Index, int team2Index, ref long sum1, ref long 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)
{
//_Players = Fold(_Players);
Cut(team1, team2);
int s1, s2; long sum1, sum2, startDiff;
sum1 = team1.Sum(x => x.Rating);
sum2 = team2.Sum(x => x.Rating);
long diff = sum1 - sum2;
startDiff = diff;
double percentageComplete = 0, previousPercentage = 0;
Console.WriteLine();
while (diff != 0 && FindSwappables(team1, team2, diff, out s1, out s2))
{
Swap(team1, team2, s1, s2, ref sum1, ref sum2);
diff = sum1 - sum2;
percentageComplete = (1 - (double)diff / (double)startDiff) * 100;
if (percentageComplete - previousPercentage >= 1)
{
previousPercentage = percentageComplete;
Console.Write(string.Format("\r{0:f2}%", percentageComplete));
}
}
Console.WriteLine("\r100%");
}
#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(5000) };
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 = 1000000;
InsureTotalPlayers(args);
//_Players = new Player[_TotalPlayers];
//for (int i = 0; i < _TotalPlayers; i++)
// _Players[i] = new Player { Name = i.ToString(), Rating = i };
GeneratePlayers();
SplitAndReportToFile();
Console.Write("Press any key to exit.");
Console.Read();
}
}
}
1 million players, valid ratings 0 -> 5000:
Generated 1000000 players in 954.1016 milliseconds
100%
Split 1000000 players into 2 500000 player teams in 47632.8125 milliseconds.
that yielded an exact 50/50 split.
