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 + M^{2}), 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.

Joel OdomAt first glance, I think this is the Knapsack problem:

http://en.wikipedia.org/wiki/Knapsack_problem

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++)

{

i++;

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 )

DerekPost 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 :-).

DerekPost 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.