LebGeeks

MSD

Member

Re: Exercise - Team Balancing

(rating is always positive).

#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>
using namespace std;


void main(void){
	vector<int> a;
    int const K = 1999500;
    for(int i = 0; i < K; i++){
        a.push_back(rand());
    }
	sort(a.begin(),a.end());
	clock_t start;
	start = clock();

	vector<int> TL;
	vector<int> TR;
	TL.push_back(a[0]);
	TR.push_back(a[1]);
	size_t idx = 2;
	unsigned int maxSum = a[0];
	unsigned int minSum = a[1];
	vector<int> *currentMax = &TL;
	vector<int> *currentMin = &TR;
	while(idx < a.size()){
		(*currentMin).push_back(a[idx]);
		minSum += a[idx];
		if(minSum > maxSum || (*currentMin).size() > (*currentMax).size()){
			int tmpSum = minSum;
			minSum = maxSum;
			maxSum = tmpSum;
			vector<int> *tmp = currentMin;
			currentMin = currentMax;
			currentMax = tmp;
		}

		idx++;
	}
	cout<<"Execution Time: "<<( double(clock() - start)/CLOCKS_PER_SEC )<<endl;


	cout<<minSum<<endl<<maxSum<<endl;
	cout<<(*currentMin).size()<<endl<<(*currentMax).size()<<endl;
}

Execution Time: 0.038
3505837259
3505853690
999750
999750

From skimming through your implementation, I think that your test input would result in distributing the sorted list among the 2 list in an alternating manner, which would cause the 2 lists to reach the final state automatically and without further processing, and this might also get you a clear 50/50 cut. To really test your code, generate random data instead of a simple sequence.

jsaade

Member

Re: Exercise - Team Balancing

You are right, if the array is sorted just add one to the first team, then another to the second team and you will get 50/50 with closest ratings.
In any case as I said before, in real-time you need to go to the simplest way.
Second implementation is wrong and my battery died, a simpler one:

#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>
using namespace std;


void main(void){
	vector<int> a;
    int const K = 1999500;
    for(int i = 0; i < K; i++){
		srand(i);
        a.push_back(rand());
    }
	sort(a.begin(),a.end());
	clock_t start;
	start = clock();

	vector<int> TL;
	vector<int> TR;
	TL.push_back(a[0]);
	TR.push_back(a[1]);
	size_t idx = 2;
	unsigned int maxSum = a[0];
	unsigned int minSum = a[1];
	vector<int> *currentMax = &TL;
	vector<int> *currentMin = &TR;
	while(idx < a.size()){
		(*currentMin).push_back(a[idx]);
		minSum += a[idx];
		int tmpSum = minSum;
		minSum = maxSum;
		maxSum = tmpSum;
		vector<int> *tmp = currentMin;
		currentMin = currentMax;
		currentMax = tmp;
	

		idx++;
	}
	cout<<"Execution Time: "<<( double(clock() - start)/CLOCKS_PER_SEC )<<endl;


	cout<<minSum<<endl<<maxSum<<endl;
	cout<<(*currentMin).size()<<endl<<(*currentMax).size()<<endl;
}

MSD

Member

Re: Exercise - Team Balancing

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.

arithma

Member

Re: Exercise - Team Balancing

Random numbers generated using rand from stdlib (0 to 0x7FFF).
For 10,000 Numbers

81107087 - 81107086 = 1
5572*1000000/2337939 = 2383microseconds

For 100,000 Numbers, for one of the worst cases.

819261805 - 819261804 = 1
74555*1000000/2337939 = 31889microseconds

However, when I used a Mersene Twister, and masked by 0xFFFFFFFFFFFF (48bits on) I started getting results such as there:

7045553622973428157 - 7045553622973352279 = 75878
141490*1000000/2337939 = 60519microseconds

I think the results deteriorate for a very important reason: There's less possibilities for the algorithm to find a decent pair to swap as to minimize the difference to zero, which means we won't have as much reassurance that this combination the swapping ended with is optimal.

@MSD: Your code does not return no matter what I tried with 100,000 values. Note that you must use longs instead of integers to handle such huge sums decently.
You can find a C, C++, C# Mersene Twister here: http://www.math.sci.hiroshima-u.ac.jp/~ … -lang.html
I am using the C version from my C++ code by including and using extern "C".

Last edited by arithma (January 30 2011)

MSD

Member

Re: Exercise - Team Balancing

@arithma, did you check the latest edition? It has long and a bunch of other goodies ;)

arithma

Member

Re: Exercise - Team Balancing

My algorithm is solving the million number problem for a range from [0, 32767) in under 100milliseconds. The reason that our algorithms are doing such a good job is that the problem has become much easier when there's a plethora of options to pick from. For example, my algorithm resolves the just mentioned range and count in under 10 swaps (usually a single swap or 5 swaps would suffice apart from the rare or the unobserved).

With this description of your algorithm, I think our methods have converged. We need to break a new frontier. I suggest we deal with 48 bit random numbers using a MerseneTwister. We'll deal with counts up to 1,000,000 for now. We'll compare algorithms based on Random Number seeds. We can verify things by binary blobs of the partitioned arrays.

It's probably to the best if we play cool about this problem now, I don't want this obsession to take over my life.

BTW: I already have a head start with the techniques, and by playing with the already linked to mersene twister.

PS: You can start experimenting immediately with [0,5000) rank range with a 100 elements. The behavior will be apparent to you: You can't be sure whether your results are optimal or not when the range with respect to the count of elements is large. I believe this is the core of the problem that I was bouncing around explaining with theory earlier. No, we should rather start here. 100 ranks, ranging from 0 to 5000. No need for extra libraries. That will come later. We should come up with a technique to generate the same sequences from the same seed, so that we can communicate better, and race, without having to expose our techniques. We can of course share all the code towards closing the problem and declaring a bad ass winner and a sour ass loser

Cheers.

Last edited by arithma (January 30 2011)

Georges

Member

Re: Exercise - Team Balancing

Arithma and MSD...
Just out of curiosity, Why do you both always tend to complicate things this much ?

jsaade

Member

Re: Exercise - Team Balancing

Arithma and MSD...
Just out of curiosity, Why do you both always tend to complicate things this much ?

Too much free time?

Joe

Member

Re: Exercise - Team Balancing

Arithma and MSD...
Just out of curiosity, Why do you both always tend to complicate things this much ?

Because optimization is exactly the point of these exercises. Going for simple solutions like the quadratic one, is not at all the most interesting part of such programming.

arithma

Member

Re: Exercise - Team Balancing

We wish it's quadratic. It's actually exponential in complexity. However there are tricks that you can do, but you can't be sure that your result is optimal.

@Georges: I do not think we complicated this problem. I did however push this conversation into something collaborative, competitive and exciting at the same time.

@ZeRaW: Yes, I do have about 10 hours of free time a day, be it a work day or not.

Anyway, here's the 64-bit Mersene Twister ported to C#. I ported it based on a 32 bit implementation in C#, and matched it with the C implementation I am using. You're welcome.

main.cs

using System;

namespace MerseneTwisterTester
{
    class Program
    {
        static void Main(string[] args)
        {
            mt19937.sgenrand(255);
            for(int i = 0; i < 10; i++)
                Console.WriteLine(mt19937.genrand());
        }
    }
}

mt19937.cs

using System;

public class mt19937
{
    /* Period parameters */
    private const int N = 312;
    private const int M = 156;
    private const ulong MATRIX_A = 0xB5026F5AA96619E9; /* constant vector a */
    private const ulong UPPER_MASK = 0xFFFFFFFF80000000; /* most significant w-r bits */
    private const ulong LOWER_MASK = 0x7FFFFFFF; /* least significant r bits */

    /* Tempering parameters */
    private const ulong TEMPERING_MASK_B = 0x9d2c5680;
    private const ulong TEMPERING_MASK_C = 0xefc60000;

    private static ulong TEMPERING_SHIFT_U(ulong y) { return (y >> 29); }
    private static ulong TEMPERING_SHIFT_S(ulong y) { return (y << 17); }
    private static ulong TEMPERING_SHIFT_T(ulong y) { return (y << 37); }
    private static ulong TEMPERING_SHIFT_L(ulong y) { return (y >> 43); }

    //static unsigned long mt[N]; /* the array for the state vector  */
    private static ulong[] mt = new ulong[N];

    // static int mti=N+1; /* mti==N+1 means mt[N] is not initialized */
    private static uint mti = N + 1; /* mti==N+1 means mt[N] is not initialized */

    /* initializing the array with a NONZERO seed */
    public static void sgenrand(ulong seed)
    {
        /* setting initial seeds to mt[N] using         */
        /* the generator Line 25 of Table 1 in          */
        /* [KNUTH 1981, The Art of Computer Programming */
        /*    Vol. 2 (2nd Ed.), pp102]                  */

        mt[0] = seed;
        for(mti = 1; mti < N; mti++) {
            mt[mti] = (6364136223846793005 * (mt[mti-1] ^ (mt[mti-1] >> 62)) + mti);
        }
    }

    private static ulong[/* 2 */] mag01 = { 0x0, MATRIX_A };
    /* generating reals */
    /* unsigned long */
    /* for integer generation */
    public static ulong genrand()
    {
        ulong y;

        /* mag01[x] = x * MATRIX_A  for x=0,1 */
        if(mti >= N) /* generate N words at one time */ {
            short kk;

            if(mti == N + 1) /* if sgenrand() has not been called, */ {
                sgenrand(5489); /* a default initial seed is used   */
            }

            for(kk = 0; kk < N - M; kk++) {
                y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK);
                mt[kk] = mt[kk + M] ^ (y >> 1) ^ mag01[y & 0x1];
            }

            for(; kk < N - 1; kk++) {
                y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK);
                mt[kk] = mt[kk + (M - N)] ^ (y >> 1) ^ mag01[y & 0x1];
            }

            y = (mt[N - 1] & UPPER_MASK) | (mt[0] & LOWER_MASK);
            mt[N - 1] = mt[M - 1] ^ (y >> 1) ^ mag01[y & 0x1];

            mti = 0;
        }

        y = mt[mti++];
        y ^= (y >> 29) & 0x5555555555555555;
        y ^= (y << 17) & 0x71D67FFFEDA60000;
        y ^= (y << 37) & 0xFFF7EEE000000000;
        y ^= (y >> 43);

        return y;
    }
}

For the rare C/C++ developer, here we go:
main.cpp

#include <iostream>
using namespace std;

extern "C" { // when using C, just include the file.
	#include "mt64.h"
}

int main(){
	init_genrand64(255);
	for(int i = 0; i < 10; i++)
		cout << genrand64_int64() << endl;
	return 0;
}

Header file, summary for user and for compiler (yes, we fluff our compiler that much)
mt64.h

/* initializes mt[NN] with a seed */
void init_genrand64(unsigned long long seed);

/* initialize by an array with array-length */
/* init_key is the array for initializing keys */
/* key_length is its length */
void init_by_array64(unsigned long long init_key[], 
		     unsigned long long key_length);

/* generates a random number on [0, 2^64-1]-interval */
unsigned long long genrand64_int64(void);


/* generates a random number on [0, 2^63-1]-interval */
long long genrand64_int63(void);

/* generates a random number on [0,1]-real-interval */
double genrand64_real1(void);

/* generates a random number on [0,1)-real-interval */
double genrand64_real2(void);

/* generates a random number on (0,1)-real-interval */
double genrand64_real3(void);

and finally: mt19937-64.c. Yes, I mix C and C++ in source code without fear, bitch.

#include <stdio.h>
#include "mt64.h"

#define NN 312
#define MM 156
#define MATRIX_A 0xB5026F5AA96619E9ULL
#define UM 0xFFFFFFFF80000000ULL /* Most significant 33 bits */
#define LM 0x7FFFFFFFULL /* Least significant 31 bits */


/* The array for the state vector */
static unsigned long long mt[NN]; 
/* mti==NN+1 means mt[NN] is not initialized */
static int mti=NN+1; 

/* initializes mt[NN] with a seed */
void init_genrand64(unsigned long long seed)
{
    mt[0] = seed;
    for (mti=1; mti<NN; mti++) 
        mt[mti] =  (6364136223846793005ULL * (mt[mti-1] ^ (mt[mti-1] >> 62)) + mti);
}

/* initialize by an array with array-length */
/* init_key is the array for initializing keys */
/* key_length is its length */
void init_by_array64(unsigned long long init_key[],
		     unsigned long long key_length)
{
    unsigned long long i, j, k;
    init_genrand64(19650218ULL);
    i=1; j=0;
    k = (NN>key_length ? NN : key_length);
    for (; k; k--) {
        mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 62)) * 3935559000370003845ULL))
          + init_key[j] + j; /* non linear */
        i++; j++;
        if (i>=NN) { mt[0] = mt[NN-1]; i=1; }
        if (j>=key_length) j=0;
    }
    for (k=NN-1; k; k--) {
        mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 62)) * 2862933555777941757ULL))
          - i; /* non linear */
        i++;
        if (i>=NN) { mt[0] = mt[NN-1]; i=1; }
    }

    mt[0] = 1ULL << 63; /* MSB is 1; assuring non-zero initial array */ 
}

/* generates a random number on [0, 2^64-1]-interval */
unsigned long long genrand64_int64(void)
{
    int i;
    unsigned long long x;
    static unsigned long long mag01[2]={0ULL, MATRIX_A};

    if (mti >= NN) { /* generate NN words at one time */

        /* if init_genrand64() has not been called, */
        /* a default initial seed is used     */
        if (mti == NN+1) 
            init_genrand64(5489ULL); 

        for (i=0;i<NN-MM;i++) {
            x = (mt[i]&UM)|(mt[i+1]&LM);
            mt[i] = mt[i+MM] ^ (x>>1) ^ mag01[(int)(x&1ULL)];
        }
        for (;i<NN-1;i++) {
            x = (mt[i]&UM)|(mt[i+1]&LM);
            mt[i] = mt[i+(MM-NN)] ^ (x>>1) ^ mag01[(int)(x&1ULL)];
        }
        x = (mt[NN-1]&UM)|(mt[0]&LM);
        mt[NN-1] = mt[MM-1] ^ (x>>1) ^ mag01[(int)(x&1ULL)];

        mti = 0;
    }
  
    x = mt[mti++];

    x ^= (x >> 29) & 0x5555555555555555ULL;
    x ^= (x << 17) & 0x71D67FFFEDA60000ULL;
    x ^= (x << 37) & 0xFFF7EEE000000000ULL;
    x ^= (x >> 43);

    return x;
}

/* generates a random number on [0, 2^63-1]-interval */
long long genrand64_int63(void)
{
    return (long long)(genrand64_int64() >> 1);
}

/* generates a random number on [0,1]-real-interval */
double genrand64_real1(void)
{
    return (genrand64_int64() >> 11) * (1.0/9007199254740991.0);
}

/* generates a random number on [0,1)-real-interval */
double genrand64_real2(void)
{
    return (genrand64_int64() >> 11) * (1.0/9007199254740992.0);
}

/* generates a random number on (0,1)-real-interval */
double genrand64_real3(void)
{
    return ((genrand64_int64() >> 12) + 0.5) * (1.0/4503599627370496.0);
}

No matter what you use, this output will signify your success.

3220586997909315655
3303451203970382242
11896436706893466529
8960318650144385956
4679212705770455613
15567843309247195414
6961994097256010468
10807484256991480663
11890420171946432686
15474158341220671739

So far I am taking the random number and masking it with 0xFFFF (though the output above is the raw 64bit numbers). 0xFFFF is even larger than the largest number returned by the C/C++ stdlib random function (0x7FFF) (which is pretty cute now that I compare).

Gladiators, begin!

Last edited by arithma (January 31 2011)

MSD

Member

Re: Exercise - Team Balancing

......... Generated 888888 players in 782.2265 milliseconds

100 %
Split 888888 players into 2 444444 player teams in 7694.336 milliseconds.

In another scenario 8.9 million players take about 33 minutes and gets me a 50/50 split (I ran this in debug mode)

The only way to make my code get a result far from a 50/50 is to manually shift the balance by adding entries different from the rest. And obviously this can be experimented with usually only on small lists like for example a list of 10 players.
I am avoiding to put any more code here so if interested you can check it on GitHub
https://github.com/M-S-D/Team-Splitter

arithma

Member

Re: Exercise - Team Balancing

@MSD: What does your algo return when using genrand()%5000 with 100 values with a seed of say 100?

MSD

Member

Re: Exercise - Team Balancing

@MSD: What does your algo return when using genrand()%5000 with 100 values with a seed of say 100?

Generated 100 players in 2 milliseconds

100 %
Split 100 players into 2 50 player teams in 25 milliseconds.

50/50 split

MSD

Member

Re: Exercise - Team Balancing

To compare our 2 algos, we need the same input, I propose you generate a file containing the cases that have a bad performance on your algo and I would test them and compare results. You could upload it somewhere like mediafire or some online space.

arithma

Member

Re: Exercise - Team Balancing

That's why I ported the 64 bit generator to C#. For a given seed, it generates the exact same sequence of pseudo-random numbers.
So by sharing a seed (and any additional steps to shape the input to the algo), we can avoid having to upload random numbers to the internets.
I checked your code and you're still using the 32bit mersene twister.

random() % 5000 should be the formula you use to get each sequence number.
We'll make sure everything is in place tonight.

MSD

Member

Re: Exercise - Team Balancing

That's why I ported the 64 bit generator to C#. For a given seed, it generates the exact same sequence of pseudo-random numbers.
So by sharing a seed (and any additional steps to shape the input to the algo), we can avoid having to upload random numbers to the internets.
I checked your code and you're still using the 32bit mersene twister.

random() % 5000 should be the formula you use to get each sequence number.
We'll make sure everything is in place tonight.

Both versions (64 and 32) are in the project but I am using the 64 bit one, and the latest push includes your suggestions of % 5000

 mt19937.sgenrand(100);
.
.
.
_Players[i] = new Player { Name = "Player" + i.ToString(), Rating = (long)(mt19937.genrand() % 5000) };

Last edited by MSD (February 1 2011)

arithma

Member

Re: Exercise - Team Balancing

Here are the first 10 numbers from the sequence:

518
1091
42
1965
1638
4596
3829
2824
2712
2614

123113 - 123114, I got it down partitioned to this in no time. Let's try to find another meaty seed and formula.

I used 10,000 this time instead of 5,000 for the range. The number of elements is 30.
This one proved just a little bit more difficult but ultimately I got to the theoretically optimal solution. Does your algo do that?
The 10 first elements from the sequence generated here are:

2559
930
6175
6621
8386
4565
5337
219
6201
719

MSD

Member

Re: Exercise - Team Balancing

Here are the first 10 numbers from the sequence:

518
1091
42
1965
1638
4596
3829
2824
2712
2614

123113 - 123114, I got it down partitioned to this in no time. Let's try to find another meaty seed and formula.

I used 10,000 this time instead of 5,000 for the range. The number of elements is 30.
This one proved just a little bit more difficult but ultimately I got to the theoretically optimal solution. Does your algo do that?
The 10 first elements from the sequence generated here are:

2559
930
6175
6621
8386
4565
5337
219
6201
719

You could have given me the seed instead of me having to figure it out :)
Anyways, I got a 50 / 50 split in about 20 milliseconds. Seed is 574, range is 10,000, and there are 30 players:

Generated 30 players in 1.9532 milliseconds

100 %
Split 30 players into 2 15 player teams in 20.5078 milliseconds.

and here is the result split:

Team 1: (50.00%)
Name: Player7, Rating: 219
Name: Player9, Rating: 719
Name: Player19, Rating: 998
Name: Player0, Rating: 2559
Name: Player5, Rating: 4565
Name: Player6, Rating: 5337
Name: Player22, Rating: 5847
Name: Player2, Rating: 6175
Name: Player8, Rating: 6201
Name: Player3, Rating: 6621
Name: Player14, Rating: 6857
Name: Player23, Rating: 7746
Name: Player13, Rating: 8012
Name: Player4, Rating: 8386
Name: Player25, Rating: 9811
Team 2: (50.00%)
Name: Player12, Rating: 28
Name: Player1, Rating: 930
Name: Player21, Rating: 2489
Name: Player28, Rating: 3026
Name: Player26, Rating: 3111
Name: Player24, Rating: 3841
Name: Player27, Rating: 4581
Name: Player17, Rating: 4708
Name: Player18, Rating: 5288
Name: Player16, Rating: 6388
Name: Player10, Rating: 7753
Name: Player15, Rating: 9081
Name: Player29, Rating: 9490
Name: Player20, Rating: 9532
Name: Player11, Rating: 9808

How much did it take you?

arithma

Member

Re: Exercise - Team Balancing

Actually I've messed up my code. It's returning around a difference of 37 at best. But I can run it 10 times in 20milliseconds so I have some space for extra hardening.

arithma

Member

Re: Exercise - Team Balancing

Here are my results. The algo does not always return the optimal solution, but it's fast enough nonetheless.

719
930
998
2559
3111
4581
5337
6201
6388
6621
6857
7746
8386
9808
9811
-----
28
219
2489
3026
3841
4565
4708
5288
5847
6175
7753
8012
9081
9490
9532

49055*1000000/2337919 = 20982microseconds

MSD

Member

Re: Exercise - Team Balancing

So, given the evidence, mine is more accurate since it got a best possible solution, and faster by a thousand times?

arithma

Member

Re: Exercise - Team Balancing

Neither. 20982microseconds = 20.982milliseconds. The difference between the two partitions up there is 1 which means it's optimal.

MSD

Member

Re: Exercise - Team Balancing

Neither. 20982microseconds = 20.982milliseconds. The difference between the two partitions up there is 1 which means it's optimal.

I guess I did not notice the unit difference, also my percentages had only 2 decimal points, so my bad. Now, let's test more demanding scenarios, shall we?
How about seed is 574, range is 100,000, and there are 1000000 players?

arithma

Member

Re: Exercise - Team Balancing

Dude, whenever the number of players is larger than the range, it means the probability to find an exact match to balance a folded partition is maximal (very close to 1).

This one is tricky: 50 numbers between 0 and 16777215; seed is 574.
I got it down to 457. I am using an assisted algorithm, so I am hand picking the results, and running it in batches to get to get a feel of the kind of results expected.

By the way, I read a little about this problem, and it's proved to be NP-Complete. Definitely not for the faint of heart.

Last edited by arithma (February 2 2011)

MSD

Member

Re: Exercise - Team Balancing

Dude, whenever the number of players is larger than the range, it means the probability to find an exact match to balance a folded partition is maximal (very close to 1).

This one is tricky: 50 numbers between 0 and 16777215; seed is 574.
I got it down to 457. I am using an assisted algorithm, so I am hand picking the results, and running it in batches to get to get a feel of the kind of results expected.

By the way, I read a little about this problem, and it's proved to be NP-Complete. Definitely not for the faint of heart.

OK, using your parameters:

Generated 50 players in 1.9532 milliseconds

100 %
Split 50 players into 2 25 player teams in 14.6484 milliseconds.

Team 1: (50.00%)
Name: Player41, Rating: 966519
Name: Player46, Rating: 1686585
Name: Player18, Rating: 1803468
Name: Player6, Rating: 1959387
Name: Player34, Rating: 2182364
Name: Player0, Rating: 2598634
Name: Player19, Rating: 3177323
Name: Player43, Rating: 3632802
Name: Player22, Rating: 3861007
Name: Player35, Rating: 4436305
Name: Player8, Rating: 6540726
Name: Player7, Rating: 8330499
Name: Player11, Rating: 8696668
Name: Player21, Rating: 8845574
Name: Player12, Rating: 9612253
Name: Player14, Rating: 10764907
Name: Player3, Rating: 10908201
Name: Player4, Rating: 11330586
Name: Player1, Rating: 12616905
Name: Player5, Rating: 13587405
Name: Player2, Rating: 14496970
Name: Player24, Rating: 14675376
Name: Player15, Rating: 15038036
Name: Player9, Rating: 15388684
Name: Player10, Rating: 16149803
Team 2: (50.00%)
Name: Player30, Rating: 54122
Name: Player26, Rating: 237176
Name: Player20, Rating: 357562
Name: Player16, Rating: 1550413
Name: Player36, Rating: 1648267
Name: Player13, Rating: 4009062
Name: Player40, Rating: 4222232
Name: Player23, Rating: 4438936
Name: Player32, Rating: 5783323
Name: Player49, Rating: 6502405
Name: Player48, Rating: 6508508
Name: Player28, Rating: 7087411
Name: Player25, Rating: 7807041
Name: Player38, Rating: 8156271
Name: Player33, Rating: 8222133
Name: Player29, Rating: 10248995
Name: Player39, Rating: 10606561
Name: Player45, Rating: 11022305
Name: Player37, Rating: 12884937
Name: Player44, Rating: 13238860
Name: Player31, Rating: 13630745
Name: Player17, Rating: 16134598
Name: Player27, Rating: 16157036
Name: Player47, Rating: 16263071
Name: Player42, Rating: 16516868

Could you post those resources about this problem?

Last edited by MSD (February 2 2011)