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, 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:

    require 'TournamentMatrix2.php';
    if (isset($_POST['submit'])) {

    function doTourney($scores) {
        $matrix = new TournamentMatrix2();

The calling code is in rankings.php.  You can run my code from  Paste in your own scores, or use my NFL regular season scores at  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.

Share This:
  • Print
  • Digg
  • StumbleUpon
  • Facebook
  • Yahoo! Buzz
  • Twitter
  • Google Bookmarks
  • Google Buzz
  • RSS

4 thoughts on “The Friday Fragment

  1. Joe Richardson

    (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++)
    if (d+c+m == max) && (15*d + c + .25*m == amount))
    Console.WriteLine("Dogs: " + d + " Cats: " + c + " Mice: " +m);
    Console.WriteLine("Iterations: " + i );

    Output from program is :
    Dogs: 3 Cats: 41 Mice: 56
    Iterations: 16277

    (Only 16,277 iterations instead of 1,000,000 if each loop is simply 1 to 100 )

  2. Derek Post author

    @Joel Odom
    I didn’t think of that at the time, but you’re right: this is a specialization of the knapsack problem. Fortunately, this puzzle is bounded, so it’s not NP-complete like a general purpose, unbounded knapsack algorithm would be. We want it to run faster than it took the Car Talk guys to work it out by hand :-).

  3. Derek Post author

    @Joe Richardson
    Bingo! I had to put back an open paren that the blog took away (after the if), but I ran it, and it’s fast and correct! What more could a guy ask? On the follow-up Car Talk episode, Ray and Tom talked about how they spent hours on this: Tom stayed up ’til 3 am without an answer, and Tom spent a lot of time just plugging in numbers. With a fragment of code, the computer could’ve done the hard work for them, too.

Comments are closed.