Rob's Blog

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.

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.