Google Sheets OPR Calculator

[Rachel Lim]

I've been trying to find an easy way to calculate OPR (type in data, press a button, get OPRs) that would run on any device without requiring you to buy/download any program. After testing a couple of different methods, I ended up finding a way to run it entirely in google sheets, by making use of a combination of google scripts and sheets' array formulas.

Link to sheet:
https://docs.google.com/spreadsheets...it?usp=sharing (make a copy of it to edit)

Example input:
- green box = where data goes
- orange boxes = ways to run program (I was playing around with different ways to run custom functions, but they all do the same thing)
- Note: the gray "run function" box is the only way to run it on mobile


Example output:



Misc notes:
- It's definitely not fast, although using the update button instead of calculating it from scratch each time really helps
- Running all MICMP data (102 teams, 204 matches) took about 45sec. For reference, doing the same calculations in matlab (reading in data and outputting to a text file) took around 0.013sec
- Times are from my laptop. I didn't time it, but it's definitely slower on my phone
- I believe the first size issue you'll hit is the 255 team limit (256 is the maximum number of columns per tab, and 1 column is needed for the score vector), although it is possible you'll hit the cell size limit before that



I'm planning a couple of additions, including adding the ability to calculate multiple component OPRs at once, trying to clean up the script and see if it can be sped up, and seeing if I can do a get request in the sheet itself and automatically populate the data. I'll also work on a game-specific one next year if I have time.

If you have any other suggestions on what else would be helpful, let me know and I'll try to add it. Also, if you find any bugs in it please let me know--I tested it several times, but it's entirely possible something slipped through.

[Ether]

Originally Posted by Rachel Lim

If you have any other suggestions on what else would be helpful, let me know

Can you post a brief overview of the method/algorithm you are using to compute OPR?

For example, are you forming the normal equations matrix N (square positive definite TxT matrix, where T is the number of teams) directly from the match scores data?

Or are you forming the 2MxT binary design matrix A (where M is the number of matches)?

Once you have N (or A), how are you using that to compute OPR?

.

[nuclearnerd]

You have to make a private copy of the sheet in order to be able to view / edit the code. I haven't looked at the algorithm myself, but I've pasted the code below.

BTW, thanks for this - it's nice to have a portable calculator to use. I've been meaning to write one forever, but I never get to it and have to rely on other people posting OPR databases to CD.

function onEdit(e) {
  var s = e.source.getActiveSheet();
  if(e.range.getA1Notation() == 'L14' && s.getSheetName() == 'data') {
    if(e.value == 'calculate OPR') {
      calculateOPR();
    }
    else if(e.value == 'update OPR') {
      updateOPR();
    }
    else if(e.value == 'clear data') {
      clearData();
    }
    e.range.clearContent();
  }
}

// *** create custom menu ***
// same functionality as drop down menu or buttons
function onOpen() {
  var ui = SpreadsheetApp.getUi();
  ui.createMenu('OPR calculations')
  .addItem('calculate OPR', 'calculateOPR')
  .addItem('update OPR', 'updateOPR')
  .addItem('clear data', 'clearData')
  .addToUi();
}


// *** calculates OPR from scratch ***
// input: alliances and scores in data tab:
// red1 red2 red3 blue1 blue2 blue3 redScore blueScore
// misc: sparse matrix and scores in data tab:
// team1 team2 team3 team4 ... teamN allianceScore      (teamX either 0 or 1 depending on whether they played that match)
// output: teams and OPRs, sorted ascending
// team1 OPR1
function calculateOPR() {
  var data = SpreadsheetApp.getActive().getSheetByName('data');
  var misc = SpreadsheetApp.getActive().getSheetByName('misc');
  var OPR = SpreadsheetApp.getActive().getSheetByName('OPR');
  
  var numMatches = data.getDataRange().getNumRows()-1; // number of matches
  var values = data.getRange(2, 1, numMatches, 8).getValues(); //get all data
  var scores = new Array();
  var teams = new Array();
  var alliances = new Array(3);
  for(var x = 0; x < 3; x++) {
    alliances[x] = new Array(numMatches*2);
  }
  var c = 0;
  var d = 0;
  
  // clear previous data
  clearCells();

  // create team, alliances, and score matrices
  for(var x = 0; x < numMatches; x++) {
    // list of all unique teams: team1 \n team2 \n ...
    for(var y = 0; y < 6; y++) {
      var unique = true;
      for(var z = 0; z < d+1; z++) {
        if(values[x][y] == teams[z]) {
          unique = false;
          break;
        }
      }
      if(unique == true) {
        teams[d] = values[x][y];
        d++;
      }
    }
    // list of all alliances: red \n blue \n ...
    for(var y = 0; y < 3; y++) {
      alliances[y][2*x] = values[x][y];
    }
    for(var y = 3; y < 6; y++) {
      alliances[y-3][2*x+1] = values[x][y];
    }
    // list of all scores: redScore \n blueScore \n ...
    for(var y = 6; y < 8; y++) {
      scores[c] = values[x][y];
      c++;
    }
  }
  
  // sort teams
  teams.sort(function(a, b) {return a - b;})
  // print out T matrix
  for(var x = 0; x < teams.length; x++) {
    OPR.getRange(x+2, 1).setValue(teams[x]);
  }
  
  // print out A matrix
  for(var x = 0; x < numMatches*2; x++) {
    for(var y = 0; y < teams.length; y++) {
      misc.getRange(x+1, y+1).setValue(0);
      for(var z = 0; z < 3; z++) { 
        if(alliances[z][x] == teams[y]) {
          misc.getRange(x+1, y+1).setValue(1);
          break;
        }
      }
    }
  }
  
  // print out b matrix
  for(var x = 0; x < numMatches*2; x++) {
    misc.getRange(x+1, teams.length+1).setValue(scores[x]);
  }
  
  // create and print formula
  var formula = createFormula(teams.length, numMatches);
  OPR.getRange(2, 2).setFormula(formula);
}


// *** updates OPR ***
// must have previously calculated with all teams
function updateOPR() {
  var data = SpreadsheetApp.getActive().getSheetByName('data');
  var misc = SpreadsheetApp.getActive().getSheetByName('misc');
  var OPR = SpreadsheetApp.getActive().getSheetByName('OPR');
   
  var numOldMatches = (misc.getDataRange().getNumRows())/2; // number of matches in previous calculation
  var numNewMatches = data.getDataRange().getNumRows() - 1; // current number of matches
  var numTeams = OPR.getDataRange().getNumRows() - 1; // number of teams
  
  
  var teams = OPR.getRange(2, 1, numTeams, 1).getValues();
  var matches = data.getRange(numOldMatches+2, 1, numNewMatches-numOldMatches+1, 8).getValues();
  
  // update A matrix
  for(var x = 0; x < numNewMatches-numOldMatches; x++) {
    for(var y = 0; y < numTeams; y++) {
      misc.getRange(2*numOldMatches + 2*x + 1, y+1).setValue(0);
      misc.getRange(2*numOldMatches + 2*x + 2, y+1).setValue(0);
      for(var z = 0; z < 3; z++) {
        if(matches[x][z] == teams[y]) {
           misc.getRange(2*numOldMatches + 2*x + 1, y+1).setValue(1);
        }
      }
      for(var z = 3; z < 6; z++) {
        if(matches[x][z] == teams[y]) {
          misc.getRange(2*numOldMatches + 2*x + 2, y+1).setValue(1);
        }
      }
    }
    misc.getRange(2*numOldMatches + 2*x + 1, teams.length+1).setValue(matches[x][6]);
    misc.getRange(2*numOldMatches + 2*x + 2, teams.length+1).setValue(matches[x][7]);
  }
  
  var formula = createFormula(numTeams, numNewMatches);
  OPR.getRange(2, 2).setFormula(formula);
}


// *** clears all non-header cells (data, misc, OPR tabs) ***
function clearData() {
  var data = SpreadsheetApp.getActive().getSheetByName('data');
  var rows = data.getDataRange().getNumRows();
  
  clearCells();
  data.getRange(2, 1, rows, 8).clearContent();
}


// input: integer (0, 1, ... 25, 26, 26, etc.)
// output: letter (A, B, ... Z, AA, AB, etc.)
// can only take up to ZZ
function columnToLetter(num) {
  var letter, letter1, letter2;
  if(num < 26) {
    letter = String.fromCharCode(65 + num);
  }
  else {
    letter1 = String.fromCharCode(65 + num/26 - 1);
    letter2 = String.fromCharCode(65 + num%26);
    letter = letter1 + letter2;
  }
  return letter;
}

// input: number of teams, number of matches
// output: formula
function createFormula(numTeams, numMatches) {
  var aRange = 'misc!A1:' + columnToLetter(numTeams-1) + numMatches*2;
  var bRange = 'misc!' + columnToLetter(numTeams) + '1:' + columnToLetter(numTeams) + numMatches*2;
  var formula = '=mmult(minverse(mmult(transpose(' + aRange + '), ' + aRange + ')), mmult(transpose(' + aRange + '), ' + bRange + '))';
  return formula;
}


// clears data from misc and OPR tabs (for calculations)
function clearCells() {
  var misc = SpreadsheetApp.getActive().getSheetByName('misc');
  var OPR = SpreadsheetApp.getActive().getSheetByName('OPR');
  var rows = OPR.getDataRange().getNumRows();
  
  misc.getDataRange().clearContent();
  OPR.getRange(2, 1, rows, 2).clearContent();
}

[CVR]

Rachel,

the IMPORTHTML function in google docs might be very useful to you. I've used it during many competitions to pull data from TBA and analyze it in Google Sheets.

If you put

=IMPORTHTML("https://www.thebluealliance.com/event/2016onwa","table",1)

in your google sheet, it'll pull the match results data from TBA and put it directly into the sheet. The format is a bit strange, but that can be dealt with easily enough.

I can't seem to find any of my spreadsheets, but there is a way you can have it auto-update the function. It will then load any new data from TBA, which is great for crunching numbers during competitions. Want to know what an alliance member's opr is in an upcoming match, even if this is their first event and they've only played 5 matches? Easy. (although the number may not be accurate... opr caveats and all that)

It also has the advantage of allowing you to change events (and even years) very easily since TBA uses a consistent url scheme.

[Rachel Lim]

Originally Posted by CVR

Rachel,

the IMPORTHTML function in google docs might be very useful to you. I've used it during many competitions to pull data from TBA and analyze it in Google Sheets.

If you put

=IMPORTHTML("https://www.thebluealliance.com/event/2016onwa","table",1)

in your google sheet, it'll pull the match results data from TBA and put it directly into the sheet. The format is a bit strange, but that can be dealt with easily enough.

I can't seem to find any of my spreadsheets, but there is a way you can have it auto-update the function. It will then load any new data from TBA, which is great for crunching numbers during competitions. Want to know what an alliance member's opr is in an upcoming match, even if this is their first event and they've only played 5 matches? Easy. (although the number may not be accurate... opr caveats and all that)

It also has the advantage of allowing you to change events (and even years) very easily since TBA uses a consistent url scheme.

Thank you! I'd found the UrlFetchApp class but it sounds like this might be easier, and I'll definitely look into including it.

[Rachel Lim]

Originally Posted by Ether

Can you post a brief overview of the method/algorithm you are using to compute OPR?

For example, are you forming the normal equations matrix N (square positive definite TxT matrix, where T is the number of teams) directly from the match scores data?

Or are you forming the 2MxT binary design matrix A (where M is the number of matches)?

Once you have N (or A), how are you using that to compute OPR?

.

I'm forming matrices A, b, and T: T is the list of teams (Tx1), b is the list of scores (2Mx1), and A is a matrix of which teams were playing which matches represented as 0s and 1s (2MxT). I think that's the same A you're referring to, but if not, A was created so that if team2, team3, and team5 played a match and got 100 points at an event with 10 teams, that row in the matrix would look like this:

0 1 1 0 1 0 0 0 0 0

And that row in b would be 100.

A and b are printed into the "misc" tab (b is the right-most column). T is printed directly into row 1 of the OPR tab. The equation to solve for OPR is put into the second row of the OPR tab:

=mmult(minverse(mmult(transpose(misc!A1:CX408), misc!A1:CX408)), mmult(transpose(misc!A1:CX408), misc!CY1:CY408))

which is the line (A'*A)\(A'*b) in your octave/matlab code


For anyone confused over what those equations do, it's just solving the following equation:




That equation is generated in the code because the size/location of the matrices varies (the one above is for MICMP data), which as Brendan said, you can access by making a copy of the sheet.


If that doesn't answer your question or I wasn't clear about something please let me know.

[Caleb Sykes]

Do you have a good idea of which operation(s) are taking up the most time for your program? You mentioned 45 seconds total runtime earlier, if you could break this down a bit more we could find out where to make improvements.

Most of this time probably comes from the createFormula function, but it would be good to check before working on alternative solutions to the [A][x]=[b] equation.

[Ether]

Originally Posted by Rachel Lim

I'm forming matrices A, b, and T: T is the list of teams (Tx1), b is the list of scores (2Mx1), and A is a matrix of which teams were playing which matches represented as 0s and 1s (2MxT). I think that's the same A you're referring to...

Yes, that is called the "design matrix" of the system of linear equations. In the case of FRC OPR, it is dichotomous (binary) and very sparse.

The equation to solve for OPR is put into the second row of the OPR tab:

=mmult(minverse(mmult(transpose(misc!A1:CX408), misc!A1:CX408)), mmult(transpose(misc!A1:CX408), misc!CY1:CY408))

That may well be your problem right there.

Try replacing that entire mess with one call to the LINEST function of Google Sheets.


EDIT: make sure the 3rd parameter in the LINEST function call is FALSE.

[Ether]

LINEST(alliance_scores_column_vector, 2M-by-T_design_matrix_A, FALSE, TRUE)

If that last parameter is true, you get not only the least-squares model coefficients (OPRs), but also a lot of extra statistics (that you may or may not want).

[Ether]

If you find that your code for creating A, b, and T is the time-consuming culprit, try creating the T-by-T N matrix and the T-by-1 d column vector directly, rather than computing them from A and b.

[Rachel Lim]

Originally Posted by Caleb Sykes

Do you have a good idea of which operation(s) are taking up the most time for your program? You mentioned 45 seconds total runtime earlier, if you could break this down a bit more we could find out where to make improvements.

Most of this time probably comes from the createFormula function, but it would be good to check before working on alternative solutions to the [A][x]=[b] equation.

My last run took about 50 seconds to finish, approximately broken down as follows:

1sec: get sheets, get ranges, initialize arrays, etc.
23sec: get unique team list, get alliance teams (T) and scores (b) in 2Mx3 and 2Mx1 formats respectively
printing team list was nearly instantaneous so I couldn't get a time on that
25sec: creating and printing out A matrix (2MxT)
printing b, creating/printing the formula, and doing the calculations for the formula were all very fast (i.e. fast enough I couldn't time them)

These times were all done by hand, I'll see tonight if I can add in a timer, but I think these give the rough percentages. I believe most of the time is taken up by looping through arrays, especially T while looking for unique teams and creating the A matrix. I could probably print A and b directly instead of creating the alliances/scores arrays which would save some time. If you have any suggestions on what else to try, let me know.

Originally Posted by Ether

LINEST(alliance_scores_column_vector, 2M-by-T_design_matrix_A, FALSE, TRUE)

If that last parameter is true, you get not only the least-squares model coefficients (OPRs), but also a lot of extra statistics (that you may or may not want).

I don't think much time is actually taken by the final calculation, but this is definitely cleaner.
However, is there a reason this is giving me team OPRs in the reverse transpose of the team vector? (And a reason for the added zero at the end?)

(i.e. i'm getting teamNOPR, teamN-1OPR, ... team1OPR, 0 instead of team1OPR \n team2OPR \n ... teamNOPR. I did take the transpose to flip it, but it's still upside down)

Originally Posted by Ether

If you find that your code for creating A, b, and T is the time-consuming culprit, try creating the T-by-T N matrix and the T-by-1 d column vector directly, rather than computing them from A and b.

Is N = [A^T][A], where each row corresponds to the sum of all the rows from A where a given team played? (and thus d is [A^T][b], or the sum of all the alliance scores from matches where that team played)

I'm not sure if this would necessarily be much faster, since it'd still require looping through the team matrix to form N (and now it'd require it to form d too), but I can definitely try it.

[Caleb Sykes]

Originally Posted by Rachel Lim

These times were all done by hand, I'll see tonight if I can add in a timer, but I think these give the rough percentages. I believe most of the time is taken up by looping through arrays, especially T while looking for unique teams and creating the A matrix. I could probably print A and b directly instead of creating the alliances/scores arrays which would save some time. If you have any suggestions on what else to try, let me know.

Here would be my suggestions for speeding up the unique team search and creating the A matrix:
Unique team search: Make an array of size 6*(matches), let's call it [C].
Place every team from the match list into a unique spot in this array.
Sort [C]
Either delete duplicates within [C] or map unique teams into your "teams" matrix.
This process should go much faster than your current method goes, and it has the added bonus of giving you a sorted list so you don't have to sort it later.

Creating the A matrix:
Create a LUT that maps teams to their index in the sorted "teams" matrix.
Set all entries of the A matrix to zero.
Fill the A matrix using something like this (pseudocode):

for each half-match
    for each team in the half-match
        A[half-match number][LUT(team)] = 1
    end for
end for

This should also save time since you are cycling through far fewer values.

[Ether]

Originally Posted by Rachel Lim

I believe most of the time is taken up by looping through arrays, especially T while looking for unique teams and creating the A matrix.

There should be no looping involved.

Here's some pseudo-code which creates A, b, and T with one non-looping pass thru the 8column data

//one pass thru the 8col data;
//for each row do the following:
 
//populate the b column vector (alliance scores):
b[++ib]=rs; b[++ib]=bs; 

//assign a unique Column Number to each team:
f1(r1); f1(r2); f1(r3); f1(b1); f1(b2); f1(b3);
  

//populate the A matrix:
row++;
A[row,aTeamCol[r1]]=1;
A[row,aTeamCol[r2]]=1;
A[row,aTeamCol[r3]]=1;
row++;
A[row,aTeamCol[b1]]=1;
A[row,aTeamCol[b2]]=1;
A[row,aTeamCol[b3]]=1;


function f1(n:word); //n is team number
 if aTeamCol[n]==0 { Col++; aTeamCol[n]=Col; T[Col]=n }

[Ether]

Originally Posted by Ether

There should be no looping involved.

Here's some pseudo-code which creates A, b, and T with one non-looping pass thru the 8column data

I just ran that code on my 10-year-old desktop PC using a simple non-compiled (scripting) language.

It took 220 milliseconds to read your 8column data (102 teams and 204 matches)
from a disk file and populate A, b, and T.

I would hope Google's scripting language could do the same in a comparable time.

[Ether]

Originally Posted by Ether

Here's some pseudo-code which creates A, b, and T with one non-looping pass thru the 8column data

Compute the OPR column vector using LINEST on A and b, and place it next to the T column vector (actual team numbers), so you can sort by OPR or Team Number if you like.