Daily Archives: January 7, 2011

The Friday Fragment

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

This Week’s Fragment

It’s NFL wildcard weekend, and analysts are all over the place in their predictions.  It’s clear who the top NFL teams are (Falcons, Pats), but less clear for teams with fewer wins, and when comparing teams that haven’t played each other in awhile.  There’s no RPI for football, but a dominance-directed graph (a.k.a., tournament graph) can provide some basic rankings.  Over the next two weeks, we’ll see if we can build such a ranking system.  Let’s start with the approach:

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.

To play along, write a description of the solution or pseudo code and post it as a comment or send it via email.  To avoid “spoilers”, simply don’t expand comments for this post.

Last Week’s Fragment – Solution

Last week’s puzzle continued with our new year’s calendar programming:

Write code to print out a month’s calendar given a month and year.

There are many implementations already available (including C code for the unix cal utility), but this was an opportunity to work it out for yourself.  I coded a Q&D web implementation in PHP; here’s the gist:

   STATIC $day_names = array('Sun', 'Mon', 'Tue', 'Wed', 'Thu', 'Fri', 'Sat');
   $days_in_month = date('t', mktime(0, 0, 0, $month, 1, $year));
   $day = 1 - date('w', mktime(0, 0, 0, $month, 1, $year));
   echo '<table border="1">';
   for ($i=0; $i<7; $i++) {
      echo '<tr border="1">';
      for ($j=0; $j<7; $j++) {
         if ($i==0)
            printf('<td border="1"><b>%s</b></td>', $day_names[$j]);
         else {
            printf('<td border="1">%s</td>',
                     ($day > 0 && $day <= $days_in_month) ? $day : '&nbsp;');
            $day++;
         }
      }
      echo '</tr>';
   }
   echo '</table><p>&nbsp;</p>';

I used the classic PHP date function tricks to get the days in month and starting day of week.  It’s running at http://derekwilliams.us/fragments/cal.php and the complete source code is here.