Rob's Blog Coding, cooking and, well, not much else

Playing with Project Euler and PHP – Part Two

This is the second instalment of me playing with Project Euler and PHP, you can check out problem one
here. In this post I'll be using the same format as before, three different
solutions to the same problem, a simple loop oriented one, a loopless one and an over engineered, object oriented one.

Problem 2: Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed one million.

As you can see from the Problem link above, in the Fibonacci sequence, the next number is the sum of previous two numbers. This is very easy to do with
a loop, we just provide it with the first two numbers and continue with the loop until the maximum is reached, keeping track of the sum of even terms as
we go. One piece of code which may not be familiar here is the variable swapping, to avoid using a temporary variable I have chosen to use
list and array.

<?php
$target = 1000000;
$sum    = 0;
for ($one=1, $two=2; $two<$target;) {
  list($one, $two) = array($two, $one+$two);
  if ($one%2==0) {
    $sum += $one;
  }
}
echo $sum . "\n";
?>

The second solution to this problem is the loopless one. This is actually one that a lot of you will be familiar with as it's one of those
sequences which is often used as an example of recursion; exactly what I'm going to use it for here. It's essentialy the same process as in the first
solution. I have used the same variable names to make it easier to see what it's doing.

<?php
function fibonacci($one, $two, $target, $sum=0)
{
  if ($two>=$target) {
    return $sum;
  }
  if ($two%2==0) {
    $sum += $target;
  }
  return fibonacci($two, $one+$two, $target, $sum);
}
echo fibonacci(1, 2, 1000000) . "\n";
?>

The third solution is the over engineered one, for this solution I'm going to use some of the same classes and interfaces used for the first problem.
Specifically I'll be using the FactorCondition and SumAction classes and the
Action and Condition interfaces. This problem doesn't lend itself to an
OO solution as well as problem one, so I'm going to have to handle this slightly differently. The executor
is going to accept two actions, one to sum values (as in the first problem) and one to encapsulate the Fibonacci sequence; and two conditions, one
to control when to stop and one to control the Fibonacci action and two conditions, one to control the fibonacci action. Let's get down to
implementing the components. I will not show the code for previously implemented classes or interfaces.

<?php
class FibonacciAction implements Action
{
  private $one = 1;
  private $two = 2;
  public function execute($value)
  {
    list($this->one, $this->two) = array($this->two, $this->one+$this->two);
  }
  public function result()
  {
    return $this->two;
  }
}
class LimitCondition implements Condition
{
  private $limit;
  public function __construct($limit)
  {
    $this->limit = $limit;
  }
  public function test($value)
  {
    return $this->limit>$value;
  }
}
?>

Once we have all the components we need to develop the executor. This executor is a little more flexible than the one used for project one as it
seperates the stop condition from the action condition and seperates the two actions out. Hopefully this model will be more useful with later problems.

<?php
class FibonacciAction implements Action
{
  private $one = 1;
  private $two = 2;
  public function execute($value)
  {
    list($this->one, $this->two) = array($this->two, $this->one+$this->two);
  }
  public function result()
  {
    return $this->two;
  }
}
class LimitCondition extends Condition
{
  private $limit;
  public function __condition($limit)
  {
    $this->limit = $limit;
  }
  public function test($value)
  {
    return $this->limit>$value;
  }
}
?>

Finally all there is to do is tie everything together and execute it.

<?php
$executor = new Executor();
$executor->setStopper(new LimitCondition(1000000));
$executor->setCondition(new FactorCondition(2));
$executor->setAction(new SumAction());
$executor->setAlgorithm(new FibonacciAction());
echo $executor->execute() . "\n";
?>

So there we have it, three more solutions to one of the Euler Project's maths problems.

Bookmark It

Playing with Project Euler and PHP

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";
[php]

<p>Here's another loopless solution using array reduce and a function which keeps track of the sum.</p>
[php]<?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?

Bookmark It