The Friday Fragment

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

This Week's Fragment

It was my Friday lunch break, and since I wanted get a problem with a recent online order corrected before the weekend, I called the merchant's 800 number. After a long hold time, I finally got a representative on the phone who, horror of horrors, was a mathematics PhD working a call center job. As I cranked up the phone volume, she told me she was swamped with calls and the correction I needed was going to take awhile. She'd prefer I just go away.

• "Can you call back later?" she asked.
• "Sure. When?"
• "In a while."
• "How long?"
• "A while."
• "Can you give me an idea?" I asked.
• "Tell ya' what. Calculate pi using the Leibniz formula to nine correct digits. Use the basic algorithm with no series accelerations or transforms. Do it 10 times. When you're done, call me back."
• "OK," I mumbled and hung up.

What to do?  The coding part was easy, and there are even Leibniz implementations all over the net. But nine correct digits would take good big number support and a billion iterations of basic Leibniz. Ten successive runs of that would go well past the end of my lunch break.

Fortunately, I have a quad core machine, had seen first-hand the benefits of threading things such as this, and even wrote about it just yesterday. So I wrapped some threads around a basic implementation, ran it, and called back. Problem solved.

You never know when you, too, might have a math PhD on the other end of a customer service call. So to help you prepare for that, I invite you to this exercise:

Write code to do ten threaded runs of the basic Leibniz formula to calculate pi to nine correct digits (one billion iterations) in significantly less time than ten successive runs.

To play along, post your code as a comment or send it via email. If you'd like, you can build atop this single-threaded Ruby implementation.

Last Week's Fragment - Solution

This week, we complete a 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.

Natural selection can be done simply by sorting the current population by fitness and taking the top N individuals, like so:

     /**
      * Compare fitness levels for sorting.
      */
     public function compareFitness($purchase1, $purchase2) {
         if ($purchase1->getFitness() == $purchase2->getFitness())
             return 0;
         return ($purchase1->getFitness() > $purchase2->getFitness()) ? -1 : 1;
     }

     /**
      * Select a subset of the given population for breeding a new generation.
      * Return this subset ordered by the most fit first.
      */
     public static function select($population, $size) {
         usort($population, array('PetPurchase', 'compareFitness'));
         return array_slice($population, 0, $size);
     }

And we terminate by breeding until we either find a perfect fit or hit a generation cap:

     /**
      * Find the most fit solution by breeding the given number of generations,
      * each with the specified population size.
      * Return an array with the most fit and the number of generations created.
      */
     public static function findMostFit($generations, $populationSize) {
         $population = self::createPopulation($populationSize);
         $mostFit = new PetPurchase();
         for ($i=0; $i<$generations; $i++) {
             $population = self::select($population, $populationSize);
             if ($population[0]->getFitness() > $mostFit->getFitness())
                 $mostFit = $population[0];
             if ($mostFit->getFitness() == 100)
                 break;
             $population = self::breed($population);
         }
         return array($mostFit, $i);
      }

My completed PetPurchase class is here. I also coded a Ruby version here. Here's an example run:

      $result = PetPurchase::findMostFit(20000, 30);
      $result[0]->printMe();
      echo $result[1].' generations';

With a result:

1510 generations

As in this case, genetic algorithms often aren't the fastest or most efficient way to get a result. They're really a (slightly) directed random walk, and they're not good for well-understood solutions that don't justify the overhead of a genetic approach. But for cases where fitness is well-understood but the solution isn't, genetic algorithms can be a valuable tool.

Hopefully this simple example clearly demonstrates the evolutionary programming approach behind cool things like BoxCar 2D.