Project Euler Problem Two

Last time, I began working on the Project Euler problems and I set out guidelines for myself that I would attempt the problem first in C# (that I’m most comfortable with) and then try to solve the problem in some new way. Last time, I used some of the LINQ extension methods that I hadn’t previously used before. Some solutions might be in F#, Ruby, Python, etc, and I might use each “new way” more than once (since 10 lines of code doesn’t make me an expert!).

I present Project Euler Problem Two. Here is the code for the C# solution using LINQ.

    /// <summary>
    /// 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, ...
    /// By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
    /// Credit to Bill Wagner for the solution.
    /// http://tinyurl.com/4846a5
    /// I knew LINQ had to have a cool answer and I learned a lot 
    /// about what LINQ can do from this little snippet of code.
    /// I blogged this originally at https://www.peteonsoftware.com/index.php/2008/12/07/project-euler-problem-two/
    /// </summary>
    public class ProblemTwo
    {
        private static Dictionary<int, long> cachedFibonacci = new Dictionary<int, long>();
            
        public static long Solve()
        {
            var evens = (from n in Enumerable.Range(0, 4000000)
                            let value = ComputeFibonacci(n)
                            where (value%2) == 0
                            select ComputeFibonacci(n)).TakeWhile(n => n <= 4000000);
     
            return evens.Sum();
        }
     
        public static long ComputeFibonacci(int term)
        {
            long answer;
     
            if (cachedFibonacci.TryGetValue(term, out answer))
            {
                return answer;
            }
     
            if (term < 2)
            {
                answer = term;
            }
            else
            {
                answer = ComputeFibonacci(term - 1) + ComputeFibonacci(term - 2);
            }
     
            cachedFibonacci.Add(term, answer);
     
            return answer;
        }
    }

As I note in the comments, this is basically Bill Wagner’s solution to this problem. His solution was so ingenious and taught me some things about LINQ that I just had to work it in here. The compute Fibonacci method was created because other Project Euler problems in the future are going to use the Fibonacci sequence, so we should have a reproducible way to create the series. I like his use of the dictionary to be able to ask for any point in the series at any time and you will only have to compute as terms that you have not yet calculated. Caching is a good thing.

The thing that was new to me was the let keyword in the LINQ query. What Bill does is store the value of the current n into value and then says that we only want it if it is even. This allows only the even values to be used. The rest of the problem is very simple, but I just wanted to point out those two points of interest.

I also tried this problem in Ruby. You can go to an interactive ruby session in your web browser here. If you type in the following code, you can see that it also works as well.

def computeFibonacci(firstTerm, secondTerm)
	return firstTerm + secondTerm
end

firstTerm = 0
secondTerm = 1
answer = 0

while secondTerm < 4000000
	newTerm = computeFibonacci(firstTerm, secondTerm)
	if secondTerm % 2 == 0
		answer += secondTerm
	end
	firstTerm = secondTerm
	secondTerm = newTerm
end

print "Answer is ", answer

There is nothing special about this code. No whiz-bang code maneuvers. Just straight forward Ruby code. I found it very helpful to test it out at the link above and see that it worked. What is funny to me (and will likely get me in trouble) is how similar the basics of Ruby are to VB (or just BASIC) in general. It is easy to pick up because it is familiar to so many people. It was a good introductory exercise into Ruby, however, so I thought that I would share it with you.

If you have any comments or questions, please feel free to leave me a comment here.