Monthly Archives: January 2011

The Friday Fragment

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

This Week’s Fragment

The NFL has honed parity to the point where “any given Sunday” should be the new slogan.  But that’s far from the case for the NCAA.  In this era of “buy games” and weak conferences, strength of schedule (SOS) is as important as win-loss record for NCAA play.  Want to know where your team really stands?  Then, yes, look at their win/loss record, but also look at their SOS ranking.

We calculated tournament graph power rankings in a recent Friday Fragment.  For the next couple of weeks, we’ll look at ranking by record and schedule strength.  So let’s get started:

Write code to find the strength of schedule (SOS) for your favorite team using the basic Wikipedia calculation.  Start with a simple list of wins and losses, parse the results, and calculate the ratio.  For extra insight, compare it to other teams played.

To play along, post your code or URL as a comment, or send it via email.

Last Week’s Fragment – Solution

Last week, we asked for a code fragment to avoid the time-consuming substitution work required to solve a recent Car Talk Puzzler:

You’re given $100 and told to spend it all purchasing exactly 100 animals at the pet store, buying at least one of each animal.  Dogs cost $15.  Cats cost $1, and mice are 25 cents each.  Determine the equations and write code to solve them.

Joel Odom pointed out that this is a form of the classic Knapsack problem.  Indeed it is, as we’re optimizing money spent and number of animals purchased.  Fortunately, the $100 and 100 item bounds keep it in (fast) polynomial time.  Joe Richardson gave us a solution in C#:

   int d,c,m, max=100, amount=100, i=0;
   for (d=1;d<=max && 15*d<=amount;d++)  {
       for (c=1;(c<=max-d) && (15*d+c<=amount);c++)   {
           for (m=1;(m<=max-c-d) && (15*d + c + .25*m<=amount);m++) {
               i++;
               if ((d+c+m == max) && (15*d + c + .25*m == amount))
                   Console.WriteLine("Dogs: " + d + " Cats: " + c + " Mice: " +m);
           }
       }
   }
   Console.WriteLine("Iterations: " + i );

This gives us 3 dogs, 41 cats, and 56 mice, lickety-split.  On the follow-up Car Talk episode, Ray and Tom talked about how they spent hours on this puzzle: Tom stayed up until 3 am without an answer, and Ray spent a lot of time just plugging in numbers. That’s the beauty of this code fragment: let the computer do the time-consuming work!

Seedy Tea

Years ago, C and C++ were the “bread and butter” languages I used most often for my real work.  In my job, these former lingue franche have since been relegated to extension language status.  But extending (building Windows EXEs and user exit DLLs that call out to C APIs) was one of today’s todo’s, so I was back in the C coding saddle again.

Visual C++ is my trusty default tool, but for this task, I was free to use the GNU compilers.  And that brought the opportunity to use the Eclipse CDT (C/C++ Development Tooling) for the first time.  I use Eclipse for many other languages now, so why not?  A quick install from the Helios site (Help -> Install New Software) got me started.

I already had the Cygwin GNU C tools: gcc, gdb, make, etc.  But since I needed to build standalone stuff with no Cygwin runtime pre-reqs, I installed MinGW from the Wascana project.  By adding these through Eclipse, it automatically set up my environment to use the MinGW toolchain.

After launching into code, I soon faced a variety of weird errors; for example, just trying to launch my program (Run->Run As->Local C/C++ Application) resulted in: Launch failed.  Binary Not Found.  After poking around, I found that the Build Artifact settings were configured for an oddly-named unix library.  I changed them as follows:

  • Artifact Type:  Executable
  • Artifact name: ${ProjName}
  • Artifact extension: exe
  • Output prefix:    (empty)

I left the object file suffixes as the unix-like .o‘s rather than Windows .obj‘s, since that didn’t really matter. It would be nice if the CDT were more Windows-aware when it came to default settings.  “When in Rome,” dontchaknow.

After getting past the initial problems, I found that coding, running, and debugging was very, well, Eclipse-like: a good thing.  I have more to do, and will probably encounter more hiccups, but I’m determined now to finish this cup of CDT.

The Friday Fragment

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

This Week’s Fragment

Equations are a perfect fit for programming.  A small fragment of code can help you quickly compute a result, particularly when substitution or Monte Carlo methods are required: you can save time by letting the computer do the “plugging in.”

A recent Car Talk Puzzler required simultaneous equations with some trial and error.  Let’s write code to let the computer do the time-consuming substitution work for us:

You’re given $100 and told to spend it all purchasing exactly 100 animals at the pet store, buying at least one of each animal.  Dogs cost $15.  Cats cost $1, and mice are 25 cents each.  Determine the equations and write code to solve them.

To play along, post your code as a comment or send it via email.

Last Week’s Fragment – Solution

In celebration of the NFL postseason, last week’s challenge was to complete our basic our team ranking system:

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

To do this, we load up the matrix from win/loss records (I used scores from ProFootball-Fans.com), square it and add it to itself (M + M2), and then add across the rows.  I offered my initial tournament matrix class to do the math and get started.

To complete this, we add methods to our TournamentMatrix class to parse the scores (parseScores) and compute the powers (computePowers).  My updated class is here as TournamentMatrix2.php.  Calling it from a web page is straightforward:

<?php
    require 'TournamentMatrix2.php';
    if (isset($_POST['submit'])) {
        doTourney($_POST['scores']);
    }

    function doTourney($scores) {
        $matrix = new TournamentMatrix2();
        $matrix->parseScores($scores);
        $matrix->computePowers();
        show_powers($matrix->getPowers());
    }
?>

The calling code is in rankings.php.  You can run my code from http://derekwilliams.us/fragments/tourney.html.  Paste in your own scores, or use my NFL regular season scores at http://derekwilliams.us/fragments/nflscores.txt.  For this NFL data, you’ll see that the top 10 power rankings are:

Rank Team Power
1 Patriots 91
2 Falcons 85
3 Jets 84
4 Ravens 79
5 Chiefs 77
6 Bears 76
7 Saints 74
8 Giants 71
9 Steelers 69
10 Eagles 69

Pretty much what you’d expect (the Packers are #13).  If only the playoffs had cooperated.

Rewire, then Plugin

I thought it would be nice to add a Nike+ widget to this blog, so I did a bit of searching.  It didn’t take long to find the cool Nike+ WordPress Plugin by Mark Rickert.  However, upon installing and configuring it, I found it failed during the curl authentication calls with:

Can not retrieve data from Nike.com.
Error: there is no user information in the request

No worries, my Nike+ data is publicly accessible, so this type of authentication is really unnecessary and only slows the retrieval time. So I edited the plugin code (nikePlus.php) to change from using up-front authentication to passing my ID on each call.

While I was in there, I also did a bit of customization and cleanup: removed unimportant details, tweaked heading levels, trimmed some things to improve performance, etc.  But I deliberately kept it simple.  That’s the beauty of these plug-ins: they’re easy to customize and tune.  Scroll down to the “Nike+ Stats” and “Recent Runs” in the right-hand column and you’ll see it.

Hats off to Mark for a handy plugin which not only was a nice add to this site, but sparked my interest in possible further Nike+ coding.

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.

Default This

It’s a common problem with new Windows DB2 installs on corp-rat machines: you try to create a new database or do some other such sysadm or secadm operation and all you get in return is:

SQL1092N <User> does not have the authority to perform the requested command or operation.

It stems from using a domain ID but not having access to the corp-rat directory (Active Directory, LDAP, whatever), either because you’re disconnected or because group enumeration is disabled.  I’ve written about it here (in the comments), and so have many others, including the IBM DB2 Program Director’s thorough treatment, How to Develop DB2 Applications on an Airplane.  The fix is quick and simple:

db2set -g DB2_GRP_LOOKUP=LOCAL,TOKENLOCAL

Followed by a DB2 restart (db2stop & db2start) for good measure.  It can be verified with:

db2set -all | find /i “grp”

It’s familiar (classic, even) by now, but all too easy to forget: a co-worker who knew it well forgot about it during today’s work.  So I’m thinking this should either be a DB2 default, or added as an install-time option/reminder.  This is right up there with db2empfa, db2_skipdeleted, db2_awe, and other such knobs where the behavior was so commonly preferred it became the new default.

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.

PHP Ecterators

“…When in the why and the wherefore is neither rhyme nor reason?”

Shakespeare, The Comedy of Errors II.2

When it comes to the common workhorse task of iterating over a collection, there are nearly as many approaches as there are languages. And these varied implementations often demonstrate the relative strengths or weaknesses of each platform.  In languages with dynamic typing and closures, iterating over collections is typically succinct and elegant. Lacking these benefits, you get code-bloat train wrecks like C++ iterators and templates.

Fortunately, good approaches often get reused. Both Ruby and Smalltalk have what I alone call the ecterators: those venerable iterator methods whose names, inspired by Alice’s Restaurant, end in “ect”: select, reject, collect, inject, and detect.  In a single line of code, you can apply a code block across a collection and get the result.  I often think in terms of the ecterators, so I miss them when working in a language that doesn’t have them.

Such was the case recently when working in PHP.  Modern versions of PHP have helpful functions like array_filter, array_reduce, and array_map, and with PHP 5.3’s lambdas/blocks and closures, you can create a Ruby-like feel.  But those non-rhyming names and inconsistent parameters just don’t do it for me.  You might say PHP lacks some reason and a lot of rhyme.  So I took a moment to write some simple alias functions, like so:

        function select($array, $callback) {
            return array_filter($array, $callback);
        };
        function collect($array, $callback) {
            return array_map($callback, $array);
        };
        function inject($array, $initial, $callback) {
            return array_reduce($array, $callback, $initial);
        };

So now I can write familiar code:

        $numbers = array(1, 2, 3, 4, 5);
        $even_numbers = select($numbers, function ($ea) { return $ea % 2 == 0; });
        $squares = collect($numbers, function ($ea) { return $ea * $ea; });
        $sum = inject($numbers, 0, function ($sum, $ea) { return $sum + $ea; });

There, reason and rhyme.