Playing with Project Euler and PHP

20th January 2008

I recently discovered Project Euler and fell in love. It is absolutely brilliant, concise, interesting and often fiendishly difficult mathematical problems which can be solved programatically. A little later I heard about Jorge Ortiz's post using the Project Euler problems to introduce functional programming techniques in Scala, which got me wondering how many different ways I could solve some of these problems with PHP.

So far I've tackled the problems in three different ways, a traditional PHPesque way, probably the most familiar to most PHP developers; a loopless way, using functional programming paradigms; and finally an absurdly over-engineered solution.

Problem 1: Add all the natural numbers below 1000 that are multiples of 3 or 5.

This is a pretty easy problem all round, in a traditional 'loopy' way it might look like this. We just loop through all the numbers adding those which are factors of 3 or five to the sum.

<?php
$sum = 0;
for ($i=1; $i<100000; $i++) {
  if ($i%3==0 || $i%5==0) {
    $sum+=$i;
  }
}
echo $sum . "\n";

Doing this without loops, although not immediately obvious is also quite easy to understand. We create a range, fitler out any elements which aren't factors of 3 or 5 and sum those which are left.

<?php
$sum = array_sum(
  array_filter(
    range(1, 99999),
    create_function('$i', 'return $i%3==0 || $i%5==0;')
  )
);
echo $sum . "\n";

Here's another loopless solution using array reduce and a function which keeps track of the sum.

<?php
$sum = array_reduce(
  range(1, 99999),
  create_function('$sum, $i', 'return ($i%3==0 || $i%5==0) ? $sum+$i : $sum;')
);
echo $sum . "\n";

OK, now that we've done two sensible (and hopefully interesting ones) I think it's time for something a little tounge-in-cheek. Yes, it's time for the over-engineered solution. This solution is based around three interfaces, Iterator (from the SPL), Condition and Action.

<?php
interface Condition
{
  public function test($value);
}
 
interface Action
{
  public function apply($value);
  public function result();
}

So, first we need a basic Iterator to generate our numbers (from 1 to 100000 in increments of 1).

<?php
class LinearGenerator implements Iterator
{
  private $start, $end, $increment;
  private $current;
 
  public function __construct($start, $end, $increment)
  {
    $this->start     = $start;
    $this->end       = $end;
    $this->increment = $increment;
  }
 
  public function current()
  {
    return $this->current;
  }
 
  public function key()
  {
    return $this->current;
  }
 
  public function next()
  {
    $this->current += $this->increment;
  }
 
  public function rewind()
  {
    $this->current = $this->start;
  }
 
  public function valid()
  {
    return isset($this->current) && $this->current <= $this->end;
  }
}

Next we need to sort out our conditions. This is a little more complex as we need two different types of condition, one for testing whether a number is a multiple of of another number and one for tying together two other conditions in an 'OR'.

<?php
class FactorCondition implements Condition
{
  private $factor;
  public function __construct($factor)
  {
    $this->factor = $factor;
  }
 
  public function test($value)
  {
    return $value % $this->factor == 0;
  }
}
 
class OrCondition implements Condition
{
  private $conditions = array();
  public function add(Condition $condition)
  {
    $this->conditions[] = $condition;
  }
 
  public function test($value)
  {
    foreach ($this->conditions as $condition) {
      if ($condition->test($value)) {
        return true;
      }
    }
    return false;
  }
}

Almost there now, next we need the component which will keep track of the sum so far, the Action.

<?php
class SumAction implements Action
{
  private $sum = 0;
  public function apply($value)
  {
    $this->sum += $value;
  }
  public function result()
  {
    return $this->sum;
  }
}

Finally we need something to pull it all together, the Executor.

<?php
class Executor
{
  private $generator, $condition, $action;
  public function setGenerator(Iterator $generator)
  {
    $this->generator = $generator;
  }
  public function setCondition(Condition $condition)
  {
    $this->condition = $condition;
  }
  public function setAction(Action $action)
  {
    $this->action = $action;
  }
  public function execute()
  {
    foreach ($this->generator as $value) {
      if ($this->condition->test($value)) {
        $this->action->apply($value);
      }
    }
    return $this->action->result();
  }
}

Now that we've put together our enterprise-ready, future-proof, dynamic solution; let's use it.

<?php
$executor = new Executor();
$executor->setGenerator(new LinearGenerator(1, 1000, 1));
$condition = new OrCondition();
$condition->add(new FactorCondition(3));
$condition->add(new FactorCondition(5));
$executor->setCondition($condition);
$executor->setAction(new SumAction());
 
echo $executor->execute();

Have you got any other solutions to the problem?

One comment so far

Posted by Travis Swicegood on 2008-01-22
Well, for starters you left out the Factory Method for creating the result. Then there's the Composite object called ProjectEulerProblem1 that wraps it entirely in an object... :-)

Leave a reply