Daily Archives: January 28, 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!