Calculates OPR from a single event's data that is input as csv files

OPR_Calculator.py

# Calculates OPR
# For implementation details, see
# http://www.chiefdelphi.com/forums/showpost.php?p=1129108&postcount=55

# M is 2m x n where m is # of matches and n is # of teams
# s is 2m x 1 where m is # of matches
# solve [M][x]=[s] for [x] by turning it into [A][x]=[b]

# A should end up being n x n an b should end up being n x 1
# x is OPR and should be n x 1

import sys
from time import *
import csv
from math import sqrt

class opr:

    data = []
    teamdata = []
    M = []

    def _init_(self):
        return 0
    
    def zeros(self,m,n):
        # returns the zero matrix for the supplied dimensions
        return [[0 for row in range(n)] for col in range(m)]

    def mTranspose(self,matrix):
        # returns the transpose of a matrix
        return map(lambda *row: list(row), *matrix)

    def mInverse(self,matrix):
        # TODO: implement matrix inversion
        # not nescessary for anything we have done thus far
        return -1

    def mMult(self,matrixA,matrixB):
        # returns result of multiplying A by B
        if len(matrixA[0]) != len(matrixB):
            print "Matrix dimension error!"
        else:
            result = self.zeros(len(matrixA),len(matrixB[0]))
            for i in range(len(matrixA)):
                 for j in range(len(matrixB[0])):
                    for k in range(len(matrixB)):
                        result[i][j] += matrixA[i][k]*matrixB[k][j]
            return result

    def getData(self,file):
        reader = csv.reader(open(file,"rb"))
        for num, row in enumerate(reader):
            if num != 0: # skip row containing column headers
                self.data.append([])
                self.data[num-1].append(int(row[3])) #redscore
                self.data[num-1].append(int(row[4])) #bluescore
                self.data[num-1].append(int(row[5])) #red1
                self.data[num-1].append(int(row[6])) #red2
                self.data[num-1].append(int(row[7])) #red3
                self.data[num-1].append(int(row[8])) #blue1
                self.data[num-1].append(int(row[9])) #blue2
                self.data[num-1].append(int(row[10])) #blue3

    def getTeamData(self,file):
        reader = csv.reader(open(file,"rb"))
        for num, row in enumerate(reader):
            if num != 0 and row!=[]: # skip row containing column headers
                self.teamdata.append([])
                self.teamdata[num-1].append(num-1) #teamid
                self.teamdata[num-1].append(int(row[0])) #teamnumber

    def getTeamID(self,num):
        # returns the matrix column index associated with a team number
        for ident, row in enumerate(self.teamdata):
            if(row[1]==num):
                return ident

    def getM(self):
        # puts a 1 in a row of M for each team on an alliance
        i = 0
        self.M = self.zeros(2*len(self.data),len(self.teamdata))
        while (i)<2*len(self.data):
            self.M[i][self.getTeamID(self.data[i/2][2])] = 1
            self.M[i][self.getTeamID(self.data[i/2][3])] = 1
            self.M[i][self.getTeamID(self.data[i/2][4])] = 1

            i += 1
                
            self.M[i][self.getTeamID(self.data[i/2][5])] = 1
            self.M[i][self.getTeamID(self.data[i/2][6])] = 1
            self.M[i][self.getTeamID(self.data[i/2][7])] = 1
            i += 1

    def gets(self):
        # gets each alliance's score for each match
        i = 0
        s = [[0] for row in range(2*len(self.data))]
        while i<2*len(self.data):
            s[i][0] = (self.data[i/2][0])
            i += 1
            s[i][0] = (self.data[i/2][1])
            i += 1
        return s

    def decompose(self,A,ztol=1.0e-3):
        # Algorithm for upper triangular Cholesky factorization
        # gives U
        # NOT USED!!! SEE decomposeDoolittle below

        num = len(A)
        t = self.zeros(num, num)
        for i in range(num):
            S = sum([(t[i][k])**2 for k in range(1,i-1)])
            d = A[i][i] -S
            if abs(d) < ztol:
               t[i][i] = 0.0
            else: 
               if d < 0.0:
                  raise ValueError, "Matrix not positive-definite"
               t[i][i] = sqrt(d)
            for j in range(i+1, num):
               S = sum([t[j][k] * t[i][k] for k in range(1,i-1)])
               if abs(S) < ztol:
                  S = 0.0
               try:
                   t[j][i] = (A[j][i] - S)/t[i][i]
               except ZeroDivisionError as e:
                   print e
        return(t)

    def decomposeDoolittle(self,A):
        # Algorithm for upper and lower triangular factorization
        # gives U and L; uses Doolittle factorization
        # http://math.fullerton.edu/mathews/n2003/CholeskyMod.html

        n = len(A)
        L = self.zeros(n, n)
        U = self.zeros(n, n)
        for k in range(n):
            L[k][k] = 1
            for j in range(k,n):
                U[k][j] = A[k][j]-sum(L[k][m]*U[m][j] for m in range(k))
            for i in range(k+1,n):
                L[i][k] = (A[i][k]-sum(L[i][m]*U[m][k] for m in range(k)))/float(U[k][k])
        return U,L

    def solve(self,L,U,b):
        # Algorithm from http://en.wikipedia.org/wiki/Triangular_matrix
        # Ax = b -> LUx = b. Then y is defined to be Ux
        # http://math.fullerton.edu/mathews/n2003/BackSubstitutionMod.html

        y = [[0] for row in range(len(b))]
        x = [[0] for row in range(len(b))]
        
        # Forward elimination Ly = b
        for i in range(len(b)):
            y[i][0] = b[i][0]
            for j in range(i):
                y[i][0] -= L[i][j]*y[j][0]
            y[i][0] /= float(L[i][i])
            
        # Backward substitution Ux = y
        for i in range(len(y)-1,-1,-1):
            x[i][0] = y[i][0]
            for j in range(i+1,len(y)):
                x[i][0] -= U[i][j]*x[j][0]
            x[i][0] /= float(U[i][i])
        return x

    def test(self):
        self.getM()
        s = self.gets()
        Mtrans = self.mTranspose(self.M)
        A = self.mMult(Mtrans,self.M) # multiply M' times M to get A
        b = self.mMult(Mtrans,s) # multiply M' times s to get b
        U,L = self.decomposeDoolittle(A)
        print "%%%%%%%%%%%%%OPR%%%%%%%%%%%%%%%%%%%"
        OPR = self.solve(L,U,b)
        print OPR
        
if __name__ == "__main__":
    start = clock()
    instance = opr()
    instance.getTeamData("worteam.csv")
    instance.getData("wor.csv")
    instance.test()
    end = clock()
    print "Took ",end-start," seconds"

wor.csv is available at: http://dl.dropbox.com/u/4474682/wor.csv
worteam.csv is available at http://dl.dropbox.com/u/4474682/worteam.csv

Expected output is:

%%%%%%%%%%%%%OPR%%%%%%%%%%%%%%%%%%%
[[11.66399513336657], [20.131888997817327], [-2.709236725069581], [13.498663183948505], [15.648860336662972], [6.0692737883152885], [21.540385569938184], [-2.6577991723737484], [5.2648537035575576], [7.5905299160519375], [-5.428985373802822], [4.474239121889076], [22.39166545407237], [4.091840216170913], [8.250062898508267], [-4.0797479264466565], [10.857177408066839], [19.740110172113646], [9.368161945071593], [7.008524784440165], [4.944055414387343], [8.157905922655607], [7.023435662147433], [-1.3957042133587962], [6.417321147981935], [3.7302702077026244], [5.566154693660647], [15.462768583709883], [4.07044065667128], [7.220130881210887], [6.2165001844047], [3.156665279939849], [11.698043536844668], [5.100881943076859]]
Took  0.450803246777  seconds