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

This Week’s Fragment

Genetic algorithms have received new attention lately with interesting things like BoxCar 2D.  And while some of the research around them may seem mysterious, the basic approach is quite simple.  Let’s revisit a recent Friday Fragment and apply evolutionary techniques to solve it:

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.  Start implementing a genetic algorithm solution – determine how to encode candidate solutions (individuals) and code the fitness function.

To play along, post your code as a comment or send it via email.  You can refer back to Joe’s conventional programming solution if you’d like; the point here is to re-structure it into a genetic algorithm in order to learn this approach first-hand.

Last Week’s Fragment – Solution

Last week’s puzzle continued our team ranking system based on win/loss records and strength of schedule (SOS):

Write code to calculate the RPI (Ratings Percentage Index) for a set of teams using the basic Wikipedia calculation.  Present the teams ordered by RPI.

I updated my PHP Team class (now TeamRPI) to calculate RPI and sort the results. Here are the changes:

     public function computeRPI() {
         ... // (code up to here is the same as last week)
         $this->setRPI((0.25 * $this->getWinPercent())
                         + (0.5 * $or) + (0.25 * $oor));
     }
     public static function sortByRPI() {
         usort(self::$allTeams, array('TeamRPI', 'compareRPI'));
     }
     public function compareRPI($team1, $team2) {
        if ($team1->getRPI() == $team2->getRPI())
           return 0;
        return ($team1->getRPI() > $team2->getRPI()) ? -1 : 1;
     }

While at it, I improved performance by using an associative array:

     private static function addTeam($team) {
        self::$allTeams[$team->getName()] = $team;
     }
     public static function getTeam($name) {
         return self::$allTeams[$name];
     }

You can run this at  http://derekwilliams.us/fragments/rpi.html, which also includes links to the source code and 2010 NCAA Football data.

Here are the top 15 RPI rankings it calculates from this data, which is similar to other pure RPI rankings.

This shows some interesting things when compared to polls and other ranking systems, such as one reason why TCU is moving to the Big East.