Is any solution the correct solution?

Question

I always think to myself after solving a programming challenge that I have been tied up with for some time, "It works, thats good enough".

I don't think this is really the correct mindset, in my opinion and I think I should always be trying to code with the greatest performance.

Anyway, with this said, I just tried a ProjectEuler question. Specifically question #2.

How could I have improved this solution. I feel like its really verbose. Like I'm passing the previous number in recursion.

<?php
  /* Each new term in the Fibonacci sequence is generated by adding the previous two
     terms. By starting with 1 and 2, the first 10 terms will be:

     1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

     Find the sum of all the even-valued terms in the sequence which do not exceed
     four million.
   */
   function fibonacci ( $number, $previous = 1 ) {
     global $answer;
     $fibonacci = $number + $previous;
     if($fibonacci > 4000000) return;
     if($fibonacci % 2 == 0) {
       $answer = is_numeric($answer) ? $answer + $fibonacci : $fibonacci;
     }
     return fibonacci($fibonacci, $number);
   }
   fibonacci(1);
   echo $answer;
?>

Note this isn't homework. I left school hundreds of years ago. I am just feeling bored and going through the Project Euler questions

Answer 1

I always think to myself after solving a programming challenge that I have been tied up with for some time, "It works, thats good enough".

I don't think this is really the correct mindset, in my opinion and I think I should always be trying to code with the greatest performance.

One of the classic things presented in Code Complete is that programmers, given a goal, can create an "optimum" computer program using one of many metrics, but its impossible to optimize for all of the parameters at once. Parameters such as

• Code Readabilty
• Understandability of Code Output
• Length of Code (lines)
• Speed of Code Execution (performance)
• Speed of writing code

Feel free to optimize for any one of these parameters, but keep in mind that optimizing for all of them at the same time can be an exercise in frustration, or result in an overdesigned system.

You should ask yourself: what are your goals? What is "good enough" in this situation? If you're just learning and want to make things more optimized, by all means go for it, just be aware that a perfect program takes infinite time to build, and time is valuable in and of itself.

Answer 2

Others on here have said it as well "This is part of the problem with example questions vs real business problems"

The answer to that question is very difficult to answer for a number of reasons:

• Language plays a huge role. Some languages are much more suited to some problems and so if you are faced with a mismatch you are going to find your solution "less than eloquent"
• It depends on how much time you have to solve the problem, the more time to solve the problem the more likely it is you will come to a solution you like (though the reverse is occasionally true as well too much time makes you over think)
• It depends on your level of satisfaction overall. I have worked on several projects where I thought parts where great and coded beautifully, and other parts where utter garbage, but they were outside of what I had time to address.

I guess the bottom line is if you think its a good solution, and your customer/purchaser/team/etc agree then its a good solution for the time. You might change your mind in the future but for now its a good solution.

Answer 3

I didn't actually test this ... but there was something i personally would have attempted to solve in this solution before calling it "done".

Avoiding globals as much as possible by implementing recursion with a sum argument

EDIT: Update according to nnythm's algorithm recommendation (cool!)

function fibonacci ( $number, $previous, $sum ) {
    if($fibonacci > 4000000) { return $sum; }
    else {
        $fibonacci = 3*$number + 2*$previous;
        return fibonacci($fibonnacci,2*$number+$previous,$sum+$fibonacci); 
    }
}
echo fibonacci(2,1,2);

Answer 4

Use the guideline that the code to solve the problem shouldn't take more than about a minute to execute. That's the most important thing for Euler problems, IMO.

Beyond that, just make sure it's readable - make sure that you can easily see how the code works. This way, you can more easily see how things worked if you ever get a problem like one of the Euler problems you solved, which in turn lets you solve that problem more quickly - because you already know how you should solve it.

You can set other criteria for yourself, but I think that's going above and beyond the intention of Euler problems - to me, the context of the problems seem far more suitable for focusing on efficiency and readability than anything else

Answer 5

You can avoid the mod 2 section by doing the operation three times (every third element is even), so that it reads: $fibonacci = 3*$number + 2*$previous; and the new input to fibonacci is ($fibonnacci,2*$number+$previous) I'm not familiar with php, so this is just general algorithm advice, I don't know if it's the right syntax. It's practically the same operation, it just substitutes a few multiplications for moduluses and additions.

Also, make sure that you start with $number as even and the $previous as the odd one that precedes it in the sequence (you could start with $number as 2, $previous as 1, and have the sum also start at 2).

Answer 6

[shrug]

A solution should be evaluated by the requirements. If all requirements are satisfied, then everything else is moxy. If all requirements are met, and you are personally dissatisfied with the solution, then perhaps the requirements need re-evaluation. That's about as far as you can take this meta-physical question, because we start getting into things like project management and business :S

Ahem, regarding your Euler-Project question, just my two-pence:

1. Consider refactoring to iterative, as opposed to recursive
2. Notice every third term in the series is even? No need to modulo once you are given your starting term

For example

public const ulong TermLimit = 4000000;

public static ulong CalculateSumOfEvenTermsTo (ulong termLimit)
{
    // sum!
    ulong sum = 0;

    // initial conditions
    ulong prevTerm = 1;
    ulong currTerm = 1;
    ulong swapTerm = 0;

    // unroll first even term, [odd + odd = even]
    swapTerm = currTerm + prevTerm;
    prevTerm = currTerm;
    currTerm = swapTerm;

    // begin iterative sum,
    for (; currTerm < termLimit;)
    {
        // we have ensured currTerm is even,
        // and loop condition ensures it is 
        // less than limit
        sum += currTerm;

        // next odd term, [odd + even = odd]
        swapTerm = currTerm + prevTerm;
        prevTerm = currTerm;
        currTerm = swapTerm;

        // next odd term, [even + odd = odd]
        swapTerm = currTerm + prevTerm;
        prevTerm = currTerm;
        currTerm = swapTerm;

        // next even term, [odd + odd = even]
        swapTerm = currTerm + prevTerm;
        prevTerm = currTerm;
        currTerm = swapTerm;
    }
    return sum;
}

So, perhaps more lines of code, but [practically] guaranteed to be faster. An iterative approach is not as "elegant", but saves recursive method calls and saves stack space. Second, unrolling term generation [that is, explicitly expanding a loop] reduces the number of times you would have had to perform modulus operation and test "is even" conditional. Expanding also reduces the number of times your end conditional [if current term is less than limit] is evaluated.

Is it "better", no, it's just "another" solution.

Apologies for the C#, not familiar with php, but I am sure you could translate it fairly well.

Hope this helps, :)

Cheers

Answer 7

It is completely your choice, whether you are happy with a solution or whether you want to improve it further. There are many project Euler problems where a brute force solution would take too long, and where you will have to look for a clever algorithm.

Problem 2 doesn't require any optimisation. Your solution is already more than fast enough. Still let me explain what kind of optimisation is possible. Often it helps to do some research on the subject. E.g. the wiki page on Fibonacci numbers contains this formula

fib(n) = (phi^n - (1-phi)^n)/sqrt(5)

where phi is the golden ratio. I.e.

phi = (sqrt(5)+1)/2.

If you use that fib(n) is approximately phi^n/sqrt(5) then you can find the index of the largest Fibonacci number smaller than M by

n = floor(log(M * sqrt(5)) / log(phi)).

E.g. for M=4000000, we get n=33, hence fib(33) the largest Fibonacci number smaller than 4000000. It can be observed that fib(n) is even if n is a multiple of 3. Hence the sum of the even Fibonacci numbers is

fib(0) + fib(3) + fib(6) + ... + fib(3k)

To find a closed form we use the formula above from the wikipedia page and notice that the sum is essentially just two geometric series. The math isn't completely trivial, but using these ideas it can be shown that

fib(0) + fib(3) + fib(6) + ... + fib(3k) = (fib(3k + 2) - 1) /2 .

Since fib(n) has size O(n), the straight forward solution has a complexity of O(n^2). Using the closed formula above together with a fast method to evaluate Fibonacci numbers has a complexity of O(n log(n)^(1+epsilon)). For small numbers either solution is of course fine.

Answer 8

Forget about Fibonacci (Problem 2), i say just advance in Euler. Don't waste time finding the optimal code for every question.

If your answer achieves the One minute rule then you are good to try the next one. After few problems, things will get harder and you will be optimizing the code while you write to achieve that goal