|
Re: Offensive Power Rankings for 2008
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:
Code:
// 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). |