The Friday Fragment

It's Friday, and time again for the Friday Fragment: our weekly programming-related puzzle.

This Week's Fragment

In celebration of the NFL playoffs, we continue our team ranking system. It's time to implement our tournament matrix:

Write code to use a tournament matrix (built from win/loss records) to compute power rankings for a set of teams.

As described below, you load up the matrix, square it and add it to itself (M + M2), and then add across the rows. To play along, provide either the URL or the code for the solution. You can post it as a comment or send it via email. If you’d like, you can build atop the simple tournament matrix class I started.

Last Week's Fragment - Solution

Last week's challenge was to propose a fragment of design, not code for ranking teams based on win/loss records. I suggested using a dominance-directed graph (a.k.a., tournament graph):

Propose an algorithm to use a tournament graph to compute power rankings. Start with simple list of wins and losses (Team A beat Team B, Team B beat Team C, etc.) and propose a way to rank the teams.

You start by creating a matrix (two-dimensional array) from the win-loss results and assign a zero or one to each cell: one if the row-wise team beat the team in that column; otherwise, zero. You then compute the powers of each vertex (in the matrix-represented graph) using the formula M + M2 (add the matrix to the result of squaring itself). From the resulting matrix, sum each row to get the power of each team. There's a nice, brief description at the bottom of this page: http://aix1.uottawa.ca/~jkhoury/graph.htm.

The benefit of this approach is it considers "transitive wins:" if Team A beats Team B and Team B beats Team C, Team A gets some credit over Team C, even if they never played. The downside is that football isn't always transitive.

So finish the code and plug in some records. Let's see how our power matrix compares to reality.