Monthly Archives: February 2011

The Friday Fragment

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

This Week’s Fragment

This week, we’ll wrap up our genetic algorithm solution to our recent pet store problem:

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.  Finish implementing our genetic algorithm solution by doing the natural selection and termination.

To play along, post your code as a comment or send it via email.  If you’d like, you can build atop my current PetPurchase class; I put in placeholders for the next steps.

Last Week’s Fragment – Solution

Last week we continued our genetic algorithm solution to our recent pet store problem:

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.  Continue implementing our genetic algorithm solution.  Write code to create an initial generation (random population) of PetPurchases and create (“breed”) subsequent generations by crossover and, if desired, mutation.

We can create the initial population by adding these methods:

     /**
      * Generate a random set of counts, within reasonable constraints.
      */
     public function randomize() {
         $this->setDogCount(rand(1,6));
         $this->setCatCount(rand(1,85));
         $this->setMouseCount(rand(1,336));        
     }
     /**
      * Create a population of the given size with random individuals.
      */
     public static function createPopulation($size) {
         $population = array();
         for ($i=0; $i<$size; $i++) {
             $purchase = new PetPurchase();
             $purchase->randomize();
             array_push($population, $purchase);
         }
         return $population;
      }

And combination and mutation is done with these new methods:

     /**
      * Set my attributes from those of my parents.
      * This is also known as breeding, crossover, or recombination.
      */
     public function combine($dad, $mom) {
         $this->setDogCount(rand(0,1) == 0 ?
                             $dad->getDogCount() : $mom->getDogCount());
         $this->setCatCount(rand(0,1) == 0 ?
                             $dad->getCatCount() : $mom->getCatCount());
         $this->setMouseCount(rand(0,1) == 0 ?
                               $dad->getMouseCount() : $mom->getMouseCount());
      }
 
      /**
       * Mutate my attributes so that I'm not an exact clone of my parents.
       */
      public function mutate() {
          $this->setDogCount(rand(0,2) == 0 ?
                              rand(1,6) : $this->getDogCount());
          $this->setCatCount(rand(0,2) == 0 ?
                              rand(1,85) : $this->getCatCount());
          $this->setMouseCount(rand(0,2) == 0 ?
                              rand(1,336) : $this->getMouseCount());
      }

There are the many possible ways to go about this; breeding techniques can be quite different, but still result in a population that contains a correct (best fit) solution.

DB2 Second Steps

I’ve written about DB2 9.7 install issues, such as here and here, but neglected to record one that bugged a co-worker today.  You log into Windows after installing and are greeted by a popup message:

SQL5005C System Error. A system error, probably an I/O error, was encountered while accessing a configuration file.

It typically comes from DB2 First Steps (db2fs.exe), but that may not be obvious.

The likely cause is that you enabled DB2’s extended Windows system security (the new default), but did not add your user ID to the DB2ADMNS or DB2USERS group.  The DB2 installation program tells us to do that, but if you didn’t do the install, you may have never seen that advice.

Just add your ID to the group and problem solved.  And maybe turn off the db2fs auto-start so it doesn’t annoy you each time.

The Friday Fragment

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

This Week’s Fragment

This week, we continue our genetic algorithm solution to our recent pet store problem:

Write code to create an initial generation (random population) of PetPurchases and create (“breed”) subsequent generations by crossover and, if desired, mutation. We’ll finish by doing the natural selection and termination next week.

To play along, post your code as a comment or send it via email.  If you’d like, you can build atop my initial PetPurchase class; I put in placeholders for the next steps.

Last Week’s Fragment – Solution

Genetic algorithms have received new attention lately with interesting things like BoxCar 2D.  So with last week’s puzzle, we began looking at a genetic algorithm approach to solving a recent Friday Fragment:

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.

We could encode candidate solutions using a simple associative array with the number of dogs, cats, and mice, but I decided to create a class (PetPurchase) and use instance variables, like so:

     class PetPurchase {
         private $dogCount, $catCount, $mouseCount;

Here’s a very simple fitness function I wrote – a method on PetPurchase.  There are many possible answers.

     public function getFitness() {

         // There must be at least one of each animal:
         if ($this->getDogCount() == 0 ||
             $this->getCatCount() == 0 ||
             $this->getMouseCount() == 0)
              return 0;

         $countError = abs(100 - $this->getTotalCount());
         $amountError = abs(100 - $this->getTotalCost());

         if ($countError > 50 || $amountError > 50)
             return 0;
         else
             return 100 - ($countError + $amountError);
     }

For the rest of this initial code, see http://derekwilliams.us/fragments/PetPurchase1.php.txt.

The Friday Fragment

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.

Rank Name Record Win % RPI
1 Auburn 14-0-0 1.000 0.694
2 LSU 11-2-0 0.846 0.660
3 Oklahoma 12-2-0 0.857 0.652
4 Arkansas 10-3-0 0.769 0.646
5 Alabama 10-3-0 0.769 0.638
6 Texas A&M 9-4-0 0.692 0.633
7 Stanford 12-1-0 0.923 0.632
8 TCU 13-0-0 1.000 0.631
9 Missouri 10-3-0 0.769 0.629
10 Ohio St. 12-1-0 0.923 0.628
11 Oregon 12-1-0 0.923 0.627
12 Michigan St. 11-2-0 0.846 0.622
13 Boise St. 12-1-0 0.923 0.621
14 Oklahoma St. 11-2-0 0.846 0.620
15 Florida St. 10-4-0 0.714 0.616

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.

Old Coffee

Recent turns of events have moved me onto a new application to be written atop an old platform.  The stack consists of WebSphere AD 5, J2EE 1.4 (with EJB), Struts 1.2, and some Rube Goldberg approaches.  It’s outdated and bloated, but since there’s no time to shift to anything modern, we’ll add more new code atop it.

It’s a very common problem these days.

Over a decade ago, many said that J2EE would become the “COBOL of the 21st Century.”  That prediction has come true, but not in a good way.  By saying that, proponents meant “ubiquitous,” but what we got instead was “entrenched” and “obsolete.”

This is largely due to the size of the ship and the number of course corrections.  J2EE is a huge designed-by-committee camel that dramatically shifted with each major release as it crushed under its own weight.  And with each successive round, the champions of lighter enterprise Java (Rod Johnson, Bruce Tate, Anil Hemrajani, etc.) have either seen their solutions become bloatware themselves, or have abandoned enterprise Java altogether.  No wonder J2EE is now called the dead man walking.

J2EE’s size and needless complexity have worked against each other.  Newer, better, lighter solutions eventually came around, but bloated, entrenched projects found it difficult or impossible to move to them.

While it doesn’t hold a candle to dynamic languages, I actually like Java and parts of J2EE (cleanly-designed servlets, JSPs, and services are good things).  It’s just the bloat and do-overs which accompany it that drive me nuts.  I’ve often wondered why Java and C++ fall victim to this far more than other languages.  Perhaps it’s the culture and personality that comes with static typing: the classic security vs. freedom trade-off.  Folks who are attracted to J2EE’s everything in triplicate and research project mindset often don’t understand the costs of technical debt or the benefits of clean and simple design.

Maybe I’m just too accustomed to quickly building apps that have maximum function with minimum code.  I’ll code in whatever language is required, but I will not abandon my push for agility, simplicity, and elegance.

The Friday Fragment

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

This Week’s Fragment

Let’s continue 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.

To play along, post your code or URL as a comment, or send it via email.  If you’d like, you can build atop last week’s code and data.

Last Week’s Fragment – Solution

Last week’s puzzle introduced us to strength of schedule calculations for NCAA teams, or any team for that matter:

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.

I wrote a basic PHP Team class to parse the results, house the records and opponents, and calculate strength of schedule.  Here’s the gist of it:

   public function computeStrengthOfSchedule() {
      foreach ($this->getOpponents() as $opponent) {
          if (!is_null($team = self::getTeam($opponent))) {
              $opponentWins += $team->getWins();
              $opponentGames += $team->getWins() + $team->getLosses();
              foreach ($team->getOpponents() as $opponentOpponent) {
                  if (!is_null($team2 = self::getTeam($opponentOpponent))) {
                       $opponentOpponentWins += $team2->getWins();
                       $opponentOpponentGames += $team2->getWins() + $team2->getLosses();
                  }
              }
          }
      }
      if ($opponentGames > 0)
          $or = $opponentWins / $opponentGames;
      if ($opponentOpponentGames > 0)
          $oor = $opponentOpponentWins / $opponentOpponentGames;
      $this->setStrengthOfSchedule(((2*$or) + $oor)/3);
 }

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

SMS

Whenever I serve as coach or team manager, I find it helpful to send out text messages for quick, last minute updates or reminders. To do this, I create email distribution lists with addresses based on the SMS gateways that each carrier supports (for example, Verizon’s is vtext.com).  Each new season brings new cell phone numbers that must be converted to email addresses.

The only challenge is determining which carrier “owns” a given cell phone number.  I’ve used the brute-force approach of trying all carriers for each number, but it’s much better to nail down the right one to begin with.  At times, I’ve asked folks to tell me their carriers, but that’s somewhat a pain.  Lately, I’ve relied on web sites like fonefinder.net to do the lookup for me.  Due to local number portability (LNP) and carrier changes, this is imperfect, but it’s close enough, and the rejected emails can be tweaked as needed.

I wrote a quick front-end to Fone Finder to convert a batch of phone numbers.  If you’re interested, check it out.  Due to the large number of crawlers and form spammers that hit this blog site, I’ll probably disable it soon, but feel free to grab the source code and run it yourself.