Category: Linq

Linq

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 http://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.

Linq

Project Euler Problem One

Leonhard Euler, from http://www.crossingwallstreet.com/euler-1000.png(From their website) Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

I decided to take a crack or two at these, even though a trillion people have done these before me (32,022 registered answers as of the time that I’m writing this). My goal is to try to do this in whatever way occurs to me at first, and then to try to solve the problem using some new technique. Over the course of solving these problems, I want to try to dig a little into F#, Ruby, C# 3.0, or whatever seems like it might be cool 🙂

Today, I attack Problem One. I’ve included the answer in the comments, so don’t read on if you don’t want to know.

namespace ProjectEuler
{
    /// <summary>
    /// Problem 1
    /// 05 October 2001
    /// If we list all the natural numbers below 10 
    /// that are multiples of 3 or 5, we get 3, 5, 6 
    /// and 9. The sum of these multiples is 23.
    ///  
    /// Find the sum of all the multiples of 3 or 5 below 1000.
    /// 
    /// The answer is 233168
    /// </summary>
    public class Problem1
    {
        public int SolveProblem()
        {
            int answer = 0;

            for (int i = 1; i < 1000; i++)
            {
                if (IsMultipleOfThreeOrFive(i))
                {
                    answer += i;
                }
            }
            
            return answer;
        }

        public static bool IsMultipleOfThreeOrFive(int number)
        {
            return (((number % 3) == 0) || ((number % 5) == 0));
        }
    }
}

Okay, that was a snoozefest. I was reading in the Pro LINQ book (the one that gave me this post) and I found Enumerable.Range. Do the wonders of LINQ never cease? Enumerable.Range will generate a range of numbers for you so that you don’t have to do a loop. Then, you could use that range to then perform a lambda on (the divisible by 3 or 5 check) and then just sum the remaining list. It turns out that this kind of thing is *exactly* what LINQ will just knock out for you. Check the resulting code.

using System.Linq;
namespace ProjectEuler
{
    /// <summary>
    /// Problem 1
    /// 05 October 2001
    /// If we list all the natural numbers below 10 
    /// that are multiples of 3 or 5, we get 3, 5, 6 
    /// and 9. The sum of these multiples is 23.
    ///  
    /// Find the sum of all the multiples of 3 or 5 below 1000.
    /// 
    /// The answer is 233168
    /// </summary>
    public class Problem1
    {
        public int SolveProblem()
        {
            var problemSet = from i in
                             Enumerable.Range(1, 999)
                             where (((i % 3).Equals(0)) || ((i % 5).Equals(0)))
                             select i;

            return problemSet.Sum();
        }
    }
}

Same answer? Check. Learned and used something new in the process? Check. Looks like I win the nerd prize!

Code Tips

Enumerable.Intersect, Enumerable.Except, and Enumerable.Union

Pro LINQ: Language Integrated Query in C# 2008I love when things come up just in time for me to need them for a project that I’m involved in. Currently, I need to take a bunch of results and find only the intersection of those results. I was contemplating doing some lambdas to compare the lists, but then I was reading Pro LINQ: Language Integrated Query in C# 2008 and I found the Intersect() method. (Note: Thanks to Jeff Meyer for loaning me the book in such a timely fashion.)

The code looks like this:

using System;
using System.Collections.Generic;
using System.Linq;

namespace Linq
{
    class Program
    {
        static void Main(string[] args)
        {
            var listOne = new List<int>() { 1, 2, 3, 4, 5};
            var listTwo = new List<int>() { 3, 4, 5, 6, 7};

            var intIntersect = listOne.Intersect(listTwo);

            foreach (var i in intIntersect)
            {
                Console.WriteLine(i);
            }
        }
    }
}

What is output is

3
4
5

There are two important things to note. First of all, you can use any IEnumerable to perform an Intersect. Secondly, it is important to realize that you are comparing from the first list to the second list. This isn’t important when doing an Intersect(), but lets look at another example.

using System;
using System.Collections.Generic;
using System.Linq;

namespace Linq
{
    class Program
    {
        static void Main(string[] args)
        {
            var listThree = new string[] { "Pete", "On", "Software" };
            var listFour = new string[] { "Joel", "On", "Software" };

            var stringExcept = listThree.Except(listFour);

            foreach (var s in stringExcept)
            {
                Console.WriteLine(s);
            }
        }
    }
}

The output of this code is

Pete

In this example, I used a string array instead of a generic List to show that other IEnumerables could be used. When calling the Except() method, I get the unique value(s) from the first IEnumerable. Intersect() would have returned

On
Software

and if I had written

var stringExcept = listFour.Except(listThree);

it would have returned

Joel

so much more care is needed when using Except() to ensure exactly which group has the unique values that you want to keep. However, there is one more thing you can do. What if you want to find every distinct value between the two lists? You would do something like the following

using System;
using System.Collections.Generic;
using System.Linq;

namespace Linq
{
    class Program
    {
        static void Main(string[] args)
        {
            var listThree = new string[] { "Pete", "Pete", "On", "Software" };
            var listFour = new string[] { "Joel", "On", "Software", "Software" };

            var uniqueStrings = listFour.Union(listThree);

            foreach (var s in uniqueStrings)
            {
                Console.WriteLine(s);
            }
        }
    }
}

which returns

Joel
On
Software
Pete

The above shows all of the unique values from the first group and any of the unique values that the second group brings to the party that the first group didn’t already have.

This is pretty powerful stuff if you have to process lists and should ensure that you are doing the most efficient operations possible. Linq is, of course, pretty exciting stuff and as I uncover more nuggets from the Pro LINQ: Language Integrated Query in C# 2008 book, I will share them here.