11 April 2007

The Stanford GraphBase: 1990 Football Season

This book is -as the title says- a platform for combinatorial computing, based on literate programming also developed by Knuth. It has good sets of data, samples and good and speak at length on of them.

There are several challenge problems and one on unsolved most popular is the 1990 season football: Stanford against Harvard. In the book appears Knuth's best solution, however later appears a research made by Buel Chandler with genetic algorithm obtaining a better result and lately in 2002 Mark Cooke found an even better (the best until now).

Despite to these solution this is a similar to TSP, where still is unknown the best solution, then you can give time to research on this problem.

A nice problem was to do a Regular Expression to parse from the file of games the teams, score and stats from reporters. My best solution is this huge RegExp: (which is accurate enough and to be used with java.util.regexp).

([A-Z]\\&?\\-?)+\\ (([A-Z][a-z]*\\\\?\\&?\\,?\\-?\\ ?)+\\(([A-Z][a-z]+\\-?\\'?\\ ?(\\\\\\&)?\\ ?)+\\)([A-Z][a-z]+\\ ?\\-?)+)\\;[0-9]*\\,[0-9]*\\;[0-9]*\\,[0-9]*

There are 120 teams (nodes) with 638 games (edges). The following graph shows the season:

Knuth has provided all the files for the Stanford Combinatorial platform, where you can find the football.dat file with all the teams and games between them. Above is the graph representing the whole season and following is the data in a more graph viewing of the games (different from the original file that is a single row result of a game pattern).

My Blog List

Blog Archive


The views expressed on this blog are my own and do not necessarily reflect the views of Oracle.