Offensive Power Rankings for 2008

[Bongle]

Someone (don't know if he wants to be revealed) via PM requested the algorithm I've been using, which meant I had to clean my code, which means I'm not as embarrassed to post it.

So here it is:

// opr.cpp : Defines the entry point for the console application.
//

#include "stdafx.h" // if you're not using visual studio, you'll probably have to toast this line

#include <fstream>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include "jama/jama_lu.h"

using namespace std;

struct Match
{
	Match()
	{
		memset(this,0,sizeof(Match));
	}
	int blue[3];
	int red[3];
	int blueScore;
	int redScore;
};

// reads all the match data from files copy/pasted from usfirst.org into a list of Match structures
// note that week 1, 2008 files can't be read unmodified by this function
// what I've been doing is pre-processing them doing a find-replace on AM and PM and adding " X " so that they have the right number of tab-seperated values
void ReadTeamData(string strFile,vector<Match>& lstMatches,set<int>& setTeams)
{
	ifstream inFile;
	inFile.open(strFile.c_str());
	
	if(inFile.fail())
	{
		cout<<"Error opening file"<<endl;
		return;
	}

	//int iTheoryMatchNum = 0;
	while(!inFile.eof())
	{
		char buf[512];
		Match aNewMatch;

		inFile>>buf; // "9:20"
		inFile>>buf; // "AM/PM"
		inFile>>buf; // match number

		
		inFile>>buf; // red 1		
		aNewMatch.red[0] = atoi(buf);
		inFile>>buf; // red 2
		aNewMatch.red[1] = atoi(buf);
		inFile>>buf; // red 3
		aNewMatch.red[2] = atoi(buf);

		inFile>>buf; // blue 1
		aNewMatch.blue[0] = atoi(buf);
		inFile>>buf; // blue 2
		aNewMatch.blue[1] = atoi(buf);
		inFile>>buf; // blue 3
		aNewMatch.blue[2] = atoi(buf);

		

		inFile>>buf;
		aNewMatch.redScore = atoi(buf);
		inFile>>buf;
		aNewMatch.blueScore = atoi(buf);

		if(aNewMatch.redScore < 0 || aNewMatch.redScore > 168 || aNewMatch.blueScore < 0 || aNewMatch.blueScore > 168)
		{
			cout<<"Warning.  Score of "<<aNewMatch.redScore<<" or of "<<aNewMatch.blueScore<<" is unexpectedly large or small.  The input file may be badly formatted"<<endl;
		}
		if(!setTeams.count(aNewMatch.red[0])) setTeams.insert(aNewMatch.red[0]);
		if(!setTeams.count(aNewMatch.red[1])) setTeams.insert(aNewMatch.red[1]);
		if(!setTeams.count(aNewMatch.red[2])) setTeams.insert(aNewMatch.red[2]);
		if(!setTeams.count(aNewMatch.blue[0])) setTeams.insert(aNewMatch.blue[0]);
		if(!setTeams.count(aNewMatch.blue[1])) setTeams.insert(aNewMatch.blue[1]);
		if(!setTeams.count(aNewMatch.blue[2])) setTeams.insert(aNewMatch.blue[2]);
		
		lstMatches.push_back(aNewMatch);
		
	}
}
// generates a mapping from team #s to row#s and the reverse
void GenerateTeamToRow(const set<int> setTeams,map<int,int>& mapTeamToRow,map<int,int>& mapRowToTeam)
{
	int iCounter = 0;
	for(set<int>::const_iterator i = setTeams.begin();i != setTeams.end();i++)
	{
		mapTeamToRow[*i] = iCounter;
		mapRowToTeam[iCounter] = *i;
		iCounter++;
	}
}
// increments the symmetric points in a matrix to indicate that a pair of teams played with each other
void IncMatrix(TNT::Array2D<double>& M,map<int,int> mapTeamToRow,int iTeam1,int iTeam2)
{
	int iRow1 = mapTeamToRow[iTeam1];
	int iRow2 = mapTeamToRow[iTeam2];

	M[iRow1][iRow2]++;
	if(iRow1 != iRow2)
	{
		M[iRow2][iRow1]++;
	}

}
// increments each team's score for all members of an alliance
void IncScore(TNT::Array1D<double>& S,map<int,int> mapTeamToRow,int aTeams[3],int iScore)
{
	for(int x = 0;x < 3;x++)
	{		
		int iRow = mapTeamToRow[aTeams[x]];
		S[iRow] += iScore;
	}
}
// generates our M and S data.  M is an NxN matrix where each cell(i,j) represents how many times team i played with team j
void GenerateBasicMatrix(const vector<Match>& lstMatches,const map<int,int> mapTeamToRow,TNT::Array2D<double>& M,TNT::Array1D<double>& S)
{
	// assertion: M should be fully zeroed at this point
	for(int x = 0;x < lstMatches.size();x++)
	{
		Match m = lstMatches[x];
		
		IncMatrix(M,mapTeamToRow,m.red[0],m.red[0]);
		IncMatrix(M,mapTeamToRow,m.red[1],m.red[1]);
		IncMatrix(M,mapTeamToRow,m.red[2],m.red[2]);

		IncMatrix(M,mapTeamToRow,m.red[0],m.red[1]);
		IncMatrix(M,mapTeamToRow,m.red[0],m.red[2]);
		IncMatrix(M,mapTeamToRow,m.red[1],m.red[2]);


		IncMatrix(M,mapTeamToRow,m.blue[0],m.blue[0]);
		IncMatrix(M,mapTeamToRow,m.blue[1],m.blue[1]); // teams play with themselves too!
		IncMatrix(M,mapTeamToRow,m.blue[2],m.blue[2]);

		IncMatrix(M,mapTeamToRow,m.blue[0],m.blue[1]);
		IncMatrix(M,mapTeamToRow,m.blue[0],m.blue[2]);
		IncMatrix(M,mapTeamToRow,m.blue[1],m.blue[2]);

		IncScore(S,mapTeamToRow,m.red,m.redScore);
		IncScore(S,mapTeamToRow,m.blue,m.blueScore);
	}
	
}
// zeroes out M
void InitMatrix(TNT::Array2D<double>& M)
{
	for(int x = 0;x < M.dim1();x++)
	{
		for(int y = 0;y < M.dim2();y++)
		{
			M[x][y] = 0;
		}
	}
}
// zeroes out S
void InitS(TNT::Array1D<double>& S)
{
	for(int x = 0;x < S.dim1();x++)
	{
		S[x] = 0;
	}
}
// loads all the teams going to championships
void LoadCMPTeams(string strFile,set<int>& lstTeams)
{
	ifstream inF;
	inF.open(strFile.c_str());

	if(inF.fail())
	{
		cerr<<"Failure at opening "<<strFile<<endl;
	}
	while(!inF.eof())
	{
		int iTeam;
		inF>>iTeam;		
		lstTeams.insert(iTeam);
	}
	
}
// reads in the list of regional files that we need to process
void ReadFileList(string strInput,vector <string>& lstFiles)
{
	ifstream inF;
	inF.open(strInput.c_str());
	while(!inF.eof())
	{
		string str;
		inF>>str;
		lstFiles.push_back(str);
	}
}
// writes the power ratings to <strFile>.out
void WritePowerRatings(string strFile,map<int,int> mapRowToTeam,Array1D<double> PowerRatings)
{
	ofstream outF;
	string strOutFile = strFile + ".out";
	outF.open(strOutFile.c_str());

	for(int x = 0;x < PowerRatings.dim();x++)
	{
		int iTeam = mapRowToTeam[x];
		outF<<iTeam<<"\t"<<PowerRatings[x]<<endl;
	}
	outF.close();
}
int main(int argc, char* argv[])
{
	if(argc != 2)
	{
		cout<<"Wrong number of arguments for scripted running, defaulting to using reglist.txt"<<endl;
		argv[1] = "reglist.txt";
	}
	
	vector <string> lstFiles; // all the regional text files to process
	map<int,double> mapTeamToTopScore;
	map<int,double> mapTeamToLastScore;
	map<int,string> mapTeamToBestReg;
	map<int,string> mapTeamToLastReg;
	map<int,bool> mapTeamToBestSet;
	map<int,int> mapTeamToRegCount;
	
	set<int> setAllTeams; // all teams
	set <int> lstChamps; // teams going to champs 
	ReadFileList(argv[1],lstFiles);

	LoadCMPTeams("c:\\cmpTeams.txt",lstChamps); // list of teams going to championships.  If this vector has more than zero entries, then we only print out data for teams going to champs

	for(int x = 0;x < lstFiles.size();x++)
	{		
		set<int> setTeams;		
		map<int,int> mapTeamToRow;
		map<int,int> mapRowToTeam;
		
		vector<Match > lstMatches;
		
		string strFile;		
		strFile = lstFiles[x];
		
		ReadTeamData(strFile,lstMatches,setTeams);					// reads match data
		
		GenerateTeamToRow(setTeams,mapTeamToRow,mapRowToTeam);		// maps each team to a number between 0 and N-1
				
		TNT::Array2D<double> M(setTeams.size(),setTeams.size());	// M
		TNT::Array1D<double> S(setTeams.size());					// S

		InitMatrix(M);
		InitS(S);

		GenerateBasicMatrix(lstMatches,mapTeamToRow,M,S); // makes M from the match list data		

		JAMA::LU<double> aMatrixSolver(M);
		Array1D<double> PowerRatings = aMatrixSolver.solve(S); // solves MO = S.  PowerRatings = solved O

	    
		WritePowerRatings(strFile,mapRowToTeam,PowerRatings); // writes the output for this regional to <strFile>.out

		// records a team's last and best power ratings
		for(int x = 0;x < PowerRatings.dim();x++)
		{
			if(lstChamps.size() == 0 || lstChamps.count(mapRowToTeam[x]))
			{
				
				double dPwr = PowerRatings[x];
				int iTeam = mapRowToTeam[x];
				if(setAllTeams.count(iTeam) == 0) // if this team hasn't made it into our list of all teams, add it
				{					
					setAllTeams.insert(iTeam);
				}
				mapTeamToRegCount[iTeam]++;
				if(dPwr > mapTeamToTopScore[iTeam] || mapTeamToBestSet[iTeam] == false)
				{
					mapTeamToTopScore[iTeam] = dPwr;
					mapTeamToBestReg[iTeam] = strFile;
					mapTeamToBestSet[iTeam]  =true;
				}
				mapTeamToLastScore[iTeam] = dPwr;
				mapTeamToLastReg[iTeam] = strFile;
			}
		}
	} // end of file loop
	
	// this prints out a team's last OPR and where it occurred.  If a team's best OPR occurred elsewhere, it prints that out
	cout<<"Team\tRegional Count\tLast OPR\tLast Regional\tBest OPR\tBest Regional"<<endl;
	for(set<int>::iterator i = setAllTeams.begin();i != setAllTeams.end();i++)
	{
		int iTeam = *i;

		cout<<iTeam<<"\t"<<mapTeamToRegCount[iTeam]<<"\t"<<mapTeamToLastScore[iTeam]<<"\t"<<mapTeamToLastReg[iTeam];
		
		cout<<"\t"<<mapTeamToTopScore[iTeam]<<"\t"<<mapTeamToBestReg[iTeam];			
		
		cout<<endl;
	}

	return 0;
}

Required files:
-Reglist.txt - a list of regional data to be processed. One file per line. Note that it will output a file for each file in this list, and that will be the OPR for that regional
-cmpteams.txt - A list of teams that you're interested in (for example, a list of teams going to championships). One team per line.
-the JAMA math library (see attached file). This is from the NIST, it should be ok to redistribute. You can get the actual file here: http://math.nist.gov/tnt/download.html

------------
Licensing: None, do whatever you want with it. Feel free to give me credit or something though (but you don't have to, if it'd cramp your style).