Google Sheets OPR Calculator

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/d/1gpjsLtbdAGeOkfpUkhPa35qGFtKTkObVuhQNZpuUtkE/edit?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
    http://i.imgur.com/bhZmo5vh.png

Example output:
http://i.imgur.com/Q3JHn0F.png

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.

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?

.

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 
 team2 
 ...
    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 
 blue 
 ...
    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 
 blueScore 
 ...
    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();
}

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.

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:

http://i.imgur.com/y4Oc1zV.png

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.

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

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]=** equation.**

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.

*





*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).

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.

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
team2OPR
… teamNOPR. I did take the transpose to flip it, but it’s still upside down)

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]**, 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.**[/quote]

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.

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 }

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.

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.

Thank you both for your suggestions–I really appreciate the help. I finally had some time to go through them, and combined both suggestions (or at least think I did) in the code below. I’m not sure if this is what the aTeamCol] did, but I created another array to map teams to indexes (i.e. teamIndex[teamNum] = index, where teams[index] = teamNum). The new times I logged were as follows (I’m excluding the initialization time since it varies greatly each time I run it, which I suspect it has to do with my wifi connection because it runs much faster at home than when I’m out):

printing T (creating full team list, sorting it, getting unique values, printing) is too fast to time manually
printing b and A: ~21sec to create/print both
printing formula: fast

One weird thing I noted is that the first 188 rows of A (first 94 matches) are printed very quickly, then there’s a long pause (at least 15sec the last time I ran it) before the remaining lines are printed. I’m not sure what’s behind this, but I’ll look into it more.


function calculateOPR2() {
  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 alliances = data.getRange(2, 1, numMatches, 8).getValues(); //get all data
  var allTeams = new Array();
  var teams = new Array();
  var teamIndex = new Array();
  var c = 0;
  
  data.getRange(1, 14).setValue('done initializing');

  // list of all teams
  for(var x = 0; x < numMatches; x++) {
    for(var y = 0; y < 6; y++) {
      allTeams[c] = alliances[x][y];
      c++;
    }
  }
  
  data.getRange(2, 14).setValue('list of all teams');
  
  // sorts all teams
  allTeams.sort(function(a, b) {return a - b;})
  data.getRange(3, 14).setValue('list of sorted teams');
  
  // list of all unique teams;
  c = 1;
  teams[0] = allTeams[0];
  teamIndex[teams[0]] = 0;
  OPR.getRange(2, 1).setValue(teams[0]);
  for(var x = 1; x < allTeams.length; x++) {
    if(allTeams[x] != allTeams[x-1]) {
      teams[c] = allTeams[x];
      teamIndex[teams[c]] = c;
      OPR.getRange(c+2, 1).setValue(teams[c]);
      c++;
    }
  }
  
  data.getRange(3, 14).setValue('list of unique teams');
  
  for(var x = 0; x < numMatches; x++) {
    // create and set b
    misc.getRange(2*x+1, teams.length+1).setValue(alliances[x][6]);
    misc.getRange(2*x+2, teams.length+1).setValue(alliances[x][7]);
    
    // create and set A
    for(var y = 0; y < teams.length; y++) {
      misc.getRange(2*x+1, y+1).setValue(0);
      misc.getRange(2*x+2, y+1).setValue(0);
    }
    misc.getRange(2*x+1, teamIndex(alliances[x][0])]+1).setValue(1);
    misc.getRange(2*x+1, teamIndex(alliances[x][1])]+1).setValue(1);
    misc.getRange(2*x+1, teamIndex(alliances[x][2])]+1).setValue(1);
    misc.getRange(2*x+2, teamIndex(alliances[x][3])]+1).setValue(1);
    misc.getRange(2*x+2, teamIndex(alliances[x][4])]+1).setValue(1);
    misc.getRange(2*x+2, teamIndex(alliances[x][5])]+1).setValue(1);
  }
  
  var formula = createFormula(teams.length, numMatches);
  OPR.getRange(2, 2).setFormula(formula);
}

I’m not sure what the time to create the matrices is exactly, but I’ll try to time the difference between creating them and printing them sometime soon. I don’t know how much time is taken up by printing to the spreadsheet, but that may account for some of the differences, because I’ve run similar programs to this outside of google scripts, with even larger data sets, and it’s significantly faster.

Hi Rachel.

I think you missed the boat here.

Your code has three passes through the matches, and the final pass has an inner loop which loops through the teams.

The pseudo-code I posted does a single pass through the 8col match data, with no inner loops in that single pass. That single pass accomplishes everything you need.

Give it a try!

Yep…I realized what you meant after I posted it.

I also figured out what’s taking so much time: it’s the repeated .getRange().setValue(). There’s another function, setValues() that allows me to print the entire array at once that really speeds it up.

However, the array must be a consistent size, so I had to keep the loop to create T so I could initialize A. It also seems like fill() doesn’t work in scripts, so I had to loop through T to set A to zero, otherwise when I printed out A it’d be filled with “NOT_FOUND”. I did cut out the loop for b (not sure why I had it there in the first place).

Although I did manage to implement your pseudo-code, the only method I found to make that work would be to print A directly (instead of creating the array first), which took longer than looping. It also results in the OPRs not being sorted, which is a convenience I’d sacrifice a bit of time for.

Hopefully that now addresses your point? I’ll post my updated code once I clean it up a bit.

Can’t you simply initialize A with a single command (no looping) to a size greater than what you expect is needed? And when you so initialize it, doesn’t it set all the array elements to zero (some languages do)?

It also seems like fill() doesn’t work in scripts,

I find it hard to imagine the script language provides no way to zero an array without looping through all its elements.

so I had to loop through T to set A to zero

why do you need to “loop through T” to set A? Just initialize the entire array A to zero before beginning the processing of the 8col data

otherwise when I printed out A…

I meant to ask this earlier: What does “print out” mean in this context, and why do you need to do that?

It also results in the OPRs not being sorted, which is a convenience I’d sacrifice a bit of time for.

Please read my earlier post#15 in this thread.

Hopefully that now addresses your point?

Not really. But if you’re satisfied with what you have I won’t bug you :slight_smile:

I could do something like set A to the number of matches. I’m not sure if it’s really worth it, or how much longer it’d take to set that many cells, but I guess that’s the alternative.

Array values are set to null (I think–if I set a cell value to that, it comes out as either “undefined” or “NOT_FOUND” depending on whether I set an individual cell or range)

I find it hard to imagine the script language provides no way to zero an array without looping through all its elements.

I think javascript has 2 ways to do that: fill() and apply(), neither of which seems to work in google scripts.

why do you need to “loop through T” to set A? Just initialize the entire array A to zero before beginning the processing of the 8col data

Each row of A is T elements long, and I need to set each value to 0. I can’t find another way to do it (see above).

I meant to ask this earlier: What does “print out” mean in this context, and why do you need to do that?

Setting the cells in a certain range to those values (using .getRange().setValues()). Basically google sheets has matrix formulas but google scripts doesn’t seem to have an equivalent, so it’s easier for me to put the matrices into a sheet, set the formula, and do the final calculations directly in the spreadsheet.

Please read my earlier post#15 in this thread.

I know I can sort it after, or set an equation to create another column sorted, but it makes it more complicated.

Not really. But if you’re satisfied with what you have I won’t bug you :slight_smile:

I understand the reason to optimize it further, but in this case I think I’ll spend the time adding in some additional functionality (like importing data automatically, multiple components, etc.). I never intended this to replace other, faster methods of calculating OPR, since other languages (especially matlab/octave) are just inherently faster at these calculations. I was mainly looking for an easy method where I could ask someone at a competition to run it without them needing to do more than type in values / press a button, and get a sorted list out of it.

This has been an interesting conversation though, so thank you for that.

I will be updating the posted spreadsheet with the new script soon (currently cleaning it up a bit, but it should be up by tonight) for anyone who wants it.