collapse Table of Contents
  1. TekPub's Mastering LINQ Challenge - Jonathan Pryor's web log
    1. TekPub's Mastering LINQ Challenge

TekPub's Mastering LINQ Challenge - Jonathan Pryor's web log

« What is mdoc? | Main | Using mdoc »

TekPub's Mastering LINQ Challenge

Justin Etheredge has posted TekPub's Mastering LINQ Challenge, in which he lays out a "little LINQ challenge." The rules:

  1. You have to blog about a single LINQ query which starts with Enumerable.Range(1,n) and produces a list of prime numbers from the range. Thus, this blog posting. (Otherwise I'd rely on my twitter response.)
  2. You can't cheat. This is determined by me, and includes hardcoding values in the results. You'll know if you cheated. Part of me wonders if just being me qualifies as cheating, but that might imply that my computer self has too large an ego </ob-##csharp-meme>.
  3. Uses no custom LINQ methods. Here I ponder what constitutes a "custom LINQ method." Is any extension method a custom LINQ method? Any utility code?
  4. Will return all of the prime numbers of the sequence. It doesn't have to be super optimal, but it has to be correct. Boy is it not super optimal (it's a one liner!), but some improvements could make it better (e.g. Memoization, hence the prior question about whether extension methods constitute a "custom LINQ method").
  5. Be one of the first 5 people to blog a correct answer and then tweet this "I just solved the @tekpub LINQ challenge: <link to post>" will get any single TekPub screencast. The time of your solution will be based on your tweet! So be prompt!

    As far as timliness, I'm writing this blog entry over four hours after my tweet, so, uh, so much for timliness.

  6. You must link to both TekPub's website and this post in your blog post.

    Done, and done.

So, the quick and dirty, not at all efficent answer (with longer identifiers as I certainly have more than 140 characters to play with:

Enumerable.Range(1, n).Where(value => 
    value <= 3
        ? true
        : Enumerable.Range(2, value - 2)
          .All(divisor => value % divisor != 0))

In English, we take all integers between 1 and n. Given a value from that sequence, if the value is less than 3, it's prime. If it's greater than three, take all numbers from 2 until value-1 and see if any of them divides value with no remainder. If none of them divide with no remainder, value is prime.

We need to use value-2 in the nested Enumerable.Range call so that we skip the value itself (since we're starting at 2).

Now, we can improve upon this in a fairly straightforward fashion if we can use additional code. For example, if we use Bart de Smet's Memoize extension method on System.Func<T, TResult>, we can skip the repeated nested Enumerable.Range call on every value, as prime numbers don't change (and thus are prime candidates for caching ;-):

Func<int, bool> isPrime = value => 
    value <= 3
        ? true
        : Enumerable.Range(2, value - 2)
          .All(divisor => value % divisor != 0))
isPrime = isPrime.Memoize();
Enumerable.Range(1, n).Where(value => isPrime(value));

Whether this latter answer matches the rules depends upon the definition of "single LINQ query" (does the definition of isPrime need to be part of the LINQ query, or just its use?) and whether Bart's Memoize extension method qualifies as a "custom LINQ method" (I don't think it is...). The downside to the memoization is that it's basically a memory leak in disguise, so I still wouldn't call it "optimal," just that it likely has better performance characteristics than my original query...

Posted on 08 Jan 2010 | Path: /development/ | Permalink
blog comments powered by Disqus