Playing with Project Euler and PHP – Part Two

20Jan/080

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