Not yet a LINQ fan?

This example is quite pretty and really shows why we should love linq🙂

The task is to implement an algorithm which solves this problem:

Find a number consisting of 9 digits in which each of the digits from 1 to 9 appears only once. This number must also satisfy these divisibility requirements:

1.The number should be divisible by 9.
2.If the rightmost digit is removed, the remaining number should be divisible by 8.
3.If the rightmost digit of the new number is removed, the remaining number should be divisible by 7.
4.And so on, until there’s only one digit (which will necessarily be divisible by 1).

Now this is how Octavio Hernandez solves the problem using LINQ:


int[] oneToNine = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

// the query
var query =
from i1 in oneToNine
from i2 in oneToNine
where i2 != i1
&& (i1 * 10 + i2) % 2 == 0
from i3 in oneToNine
where i3 != i2 && i3 != i1
&& (i1 * 100 + i2 * 10 + i3) % 3 == 0
from i4 in oneToNine
where i4 != i3 && i4 != i2 && i4 != i1
&& (i1 * 1000 + i2 * 100 + i3 * 10 + i4) % 4 == 0
from i5 in oneToNine
where i5 != i4 && i5 != i3 && i5 != i2 && i5 != i1
&& (i1 * 10000 + i2 * 1000 + i3 * 100 + i4 * 10 + i5) % 5 == 0
from i6 in oneToNine
where i6 != i5 && i6 != i4 && i6 != i3 && i6 != i2 && i6 != i1
&& (i1 * 100000 + i2 * 10000 + i3 * 1000 + i4 * 100 + i5 * 10 + i6) % 6 == 0
from i7 in oneToNine
where i7 != i6 && i7 != i5 && i7 != i4 && i7 != i3 && i7 != i2 && i7 != i1
&& (i1 * 1000000 + i2 * 100000 + i3 * 10000 + i4 * 1000 + i5 * 100 + i6 * 10 + i7) % 7 == 0
from i8 in oneToNine
where i8 != i7 && i8 != i6 && i8 != i5 && i8 != i4 && i8 != i3 && i8 != i2 && i8 != i1
&& (i1 * 10000000 + i2 * 1000000 + i3 * 100000 + i4 * 10000 +
i5 * 1000 + i6 * 100 + i7 * 10 + i8) % 8 == 0
from i9 in oneToNine
where i9 != i8 && i9 != i7 && i9 != i6 && i9 != i5 && i9 != i4 && i9 != i3 && i9 != i2 && i9 != i1
let number = i1 * 100000000 +
i2 * 10000000 +
i3 * 1000000 +
i4 * 100000 +
i5 * 10000 +
i6 * 1000 +
i7 * 100 +
i8 * 10 +
i9 * 1
where number % 9 == 0
select number;

// run it!
foreach (int n in query)
Console.WriteLine(n);

This is very easy to read – even without any code comments. Now take a look at this solution (in cpp) from http://software.intel.com/en-us/blogs/2009/12/07/intel-parallel-studio-great-for-serial-code-too-episode-1/:


// Written by Jim Cownie (Intel), placed in the public domain.
//
// Beware, this code has bugs (both deliberate, and, probably, non-deliberate!),
// though it does produce the right answer...
//

#include "stdafx.h"

// Solve the logic problem which is to find a number consisting of 9 digits
// in which each of the digits from 1 to 9 appears only once. This number
// should satisfy the following requirements:
//
// a. The number should be divisible by 9.
// b. If the rightmost digit is removed, the remaining number should be divisible by 8.
// c. If then again the rightmost digit is removed, the remaining number should be divisible by 7.
// d. etc. until the last remaining number of one digit which should be divisible by 1.
//
// We actually solve the more general problem in which we have an N digit number in base N+1,
// since generality is good.

#include
#include

using namespace std;

typedef unsigned long long uint64;

class number
{
int nDigits; // number of digits in the number
int * digits; // space for the digits of the number
public:
// Null constructor
number(int n)
{
nDigits = n;
digits = new int [nDigits];
for (int i=0; i<nDigits; i++)
digits[i] = 0;
}

// Copy constructor
number (const number & other)
{
nDigits = other.nDigits;
digits = new int [nDigits];

for (int i=0; i<=nDigits; i++)
digits[i] = other.digits[i];
}

// Set the value of a specific digit of the number
void setDigit(int digit, int value)
{
digits[digit] = value;
}

// Obtain the value of the nd leftmost digits of the number,
// or the whole number by default.
uint64 value (int nd=0) const
{
if (nd == 0)
nd = nDigits;

uint64 v = 0;
for (int i=0; i<nd; i++)
v = v*(nDigits+1) + digits[i];
return v;
}

// Format the leftmost nd digits of the number, or the whole number by default.
string format(int nd=0) const
{
if (nd == 0)
nd = nDigits;
string s;
for (int i=0; i<nd; i++)
{
int d = digits[i];
char c = d =1; i--)
{
if ((value(i) % i) != 0)
return false;
}

return true;
}
};

static bool * usedDigits;
static int numDigits = 9;

// Build all possible numDigits digit numbers which have unique digits
// and test whether they meet the required criteria.
// We recursively walk the tree of possible numbers, maintaining the
// information about what digits have already been used in "usedDigits".
static void generateAndTest(number n, int depth)
{
if (depth == numDigits)
{
if (n.validate())
{
// We have a solution. Print it, and demonstrate that
// it meets the divisibility criteria.
cout << "Solution is " << n.format() <=1; i--)
{
cout << n.format (i) << " % " << i << " = " << n.value(i)%i << endl;
}
}
return;
}

// Try all the available digits for this position in the number.
for (int i=0; i 1)
numDigits = _wtoi(argv[1]);
usedDigits = new bool [numDigits];
for (int i=0; i<numDigits; i++)
usedDigits[i] = false;
number n(numDigits);

generateAndTest(n, 0);

return 0;
}

Even with all the code annotations I can hardly get my head around how this works.

Once again – the strength of Linq really is that it is much better at expressing the intention of the code.

Probably the cpp solution could be better performant, but according to the writer, the linq solution actually performs within one second (“much less than a second”), – wauw!

Linq fan it is😉

15 responses to “Not yet a LINQ fan?

  1. Here is a solution to the problem using F# (version 1.9.6.16).

    I must anticipate a potential problem. The F# code below needs a width of 72 columns to show up properly. Additionally, it is important that the code is properly indented; otherwise, it will not execute.

    There are 2 overall objectives. First, prepare an enumeration over all candidates. Second, produce a subset from the candidacy list that meets the criteria given in the problem statement.

    The first step is achieved by recognizing and solving the surrogate problem: Generate all permutations of the list [1;2;3;4;5;6;7;8;9]. The first step is more complicated, so let’s stub it in the code below as the function “PermutationsOfDegree”, and jump to the second step, i.e.: filtering the full set of permutations to find the subset that meets the given criteria. Given the full set of permutations (not implemented yet) here is one way to query the solution (program execution begins at the Compute function):

    let PermutationsOfDegree degree : int list list =
    raise 347
    digits |> Seq.fold (fun accum next -> 10 * accum + next) 0;;

    let MeetsCriteria (digits:int seq) =
    // There is no reason to test the first digit since
    // (any integer)~mod~1 is zero; thus, we begin the
    // search at the 2nd digit. The forall function tests
    // whether all elements satisfy the predicate.
    seq { 2..Seq.length digits }
    |> Seq.forall (fun m ->
    (digits |> Seq.take m |> DigitsToNumber) % m = 0);;

    let Compute =
    printfn “Computing…”
    PermutationsOfDegree 9
    |> List.filter (fun candidate -> candidate |> MeetsCriteria)
    |> List.map (fun digits -> digits |> DigitsToNumber);;

    Copy and paste the previous code (after the PermutationsOfDegree function has been implemented, which is done below) into the F# interactive window, and wait. The computation should complete in 20 to 30 seconds. The result is:

    val Compute : int list = [381654729]

    For the benefit of those unfamiliar with F#, I’ll decompose the Compute function, which is essentially the program’s driver. Since the computation takes a little time to complete we begin with the notification “Computing…”. Next, the PermutationsOfDegree function returns a matrix (a list of lists) where each row is a permutation. This matrix is then operated on by a filter (the “|>” is the forward-pipe operator; it allows you to chain functions together, effectively delivering the output of the previous computation to the next function; according to the book “Expert F#” by Don Syme, Adam Granicz, and Antonio Cisternino, p.45, “[t]he |> ‘forward pipe’ operator is perhaps the most important operator in F# programming.”). The filter function operates on each row of the matrix (here the row is called “candidate” and is one of the permutations). So, use the forward pipe to send a candidate to the MeetsCriteria function. The filter will collect only those candidates that meet the criteria. Last, convert each successful permutation to a base-10 number by sending the permutation to the DigitsToNumber function.

    One final observation, before continuing, is to casually note how indices do not play a role. LINQ can also take advantage of this style. For example, the MeetsCriteria function prepares to build base-10 numbers by “taking” m digits from the start of a given permutation. Thus “1” means take 1 element, “2” means take 2 elements, and so on. To be sure, [1;2;3] |> Seq.take 2 means “take the first 2 elements of the list”. If this is forward piped to Seq.to_list, we end up with [1;2]. Incidentally, this approach of avoiding indices is why neither “n-1” nor the like are observed. Much more can be said about this, but that is beyond the scope.

    To enable the above solution, replace the PermutationsOfDegree function with the following implementation:

    let PermutationsOfDegree degree : int list list =
    (* The Distribute and Permute functions come from sections
    6.4.13 and 6.4.14 of Jon Harrop’s F# for Scientists;
    they are slightly changed, so any errors are mine. *)
    let rec Distribute e = function
    | [] -> [[e]]
    | x :: xs’ as xs ->
    (e :: xs) :: [ for xs in Distribute e xs’ -> x :: xs ]
    let rec Permute = function
    | e :: t -> List.concat (List.map (Distribute e) (Permute t))
    | [] -> [[]]
    Permute [1..degree];;

    The following indicates how the algorithm works.

    The permutations of [1;2] are:

    [ [1;2]; [2;1] ]

    To get the permutations of [1;2;3], insert 3 in all possible ways to each list of the previous result, which yields:

    [ [ [3;1;2];[1;3;2];[1;2;3] ]; [ [3;2;1];[2;3;1];[2;1;3] ] ]

    For other permutation algorithms and further discussion the reader may wish to consult Donald E. Knuth’s The Art of Computer Programming – Volume 4 – Generating All Tuples and Permutations (Fascicle 2), section 7.2.1.2.

    • I have read that LINQ had some of its inspiration from functional programming, so one would expect to find similarities, and undeniably it shares characteristics with functional programming, but I am no expert in that regard. I think the important simplification of the problem was recognizing that the only possible set of candidates come from the set of all permutations of degree 9. At that point it easily becomes an exercise of brute force iteration through the set, so we can expect LINQ to perform nicely as well. Before I continue, I have a strong suspicion that the “greater than” symbol and the “less than symbol” are the culprits of the prior code deletion. For example, I suspect in the C++ code, those #include statements probably had such symbols, but they are not present in the code. Here are their HTML escape forms (minus the spacing and quotes): “& g t ;” and “& l t ;”. I’m not sure if that will help somehow. I mention this also because the C# code below contains the same characters, but I will replace them with something else; for the time being a less than symbol will be |L| and a greater than symbol will be |G|. Suppose we had a way, in C#, to generate all permutations. The following LINQ code, which is nearly in one-to-one correspondence with the F# code, will give us the answer we seek:

      // Horner’s method
      Func|L|IEnumerable|L|int|G|, int|G| digitsToNumber =
      digits =|G| digits.Aggregate(0, (a, n) =|G| 10 * a + n);

      var q =
      from p in PermutationsOfDegree(9)
      let meetsCriteria =
      // Be careful here. We could say (2, 8) and be like
      // the F# code, but the second argument here is “how
      // many” from the first agument, so to avoid a logical
      // error, we’ll test mod 1 as well (it is still very
      // fast).
      Enumerable.Range(1, 9)
      .All(m =|G| digitsToNumber(p.Take(m)) % m == 0)
      where meetsCriteria
      select p;

      foreach (var i in q)
      {
      Debug.WriteLine(digitsToNumber(i));
      }

      That’s pretty nice! (Don’t forget to clean up the |L| and |G| symbols.)

      We could use the C++ STL next_permutation function to generate all permutations, and call that from C#, since the .NET Framework easily accommodates such a solution, but instead, I will implement the method in C#. Here it is; don’t forget to remove the |L| and |G| symbols:

      // Based on Knuth algorithm L section 7.2.1.2 (see reference above).
      private static IEnumerable|L|int[]|G| PermutationsOfDegree(int degree)
      {
      LinkedList|L|int[]|G| permutations = new LinkedList|L|int[]|G|();
      int[] a = Enumerable.Range(0, degree + 1).ToArray();
      int n = a.Length – 1;
      while (a[0] == 0)
      {
      permutations.AddLast(a.Skip(1).ToArray());
      int j = n – 1;
      while (a[j] |G|= a[j + 1])
      {
      j–;
      }
      // According to Knuth the algorithm would terminate here if
      // j=0, but I put that in the while condition, so if there
      // are bugs, one might look here first.
      int l = n;
      while (a[j] |G|= a[l])
      {
      l–;
      }
      Interchange(a, j, l);
      int k = j + 1;
      l = n;
      while (k |L| l)
      {
      Interchange(a, k, l);
      k++;
      l–;
      }
      }
      return permutations;
      }
      private static void Interchange(int[] digits, int i, int j)
      {
      int t = digits[i];
      digits[i] = digits[j];
      digits[j] = t;
      }

      • I don’t know how to write for the internet. That smiley face should have been “8 )”.

    • Hey DKR – I was taking a look at some Python – just for the fun of it – and came up with this solution – quite expressive, I think?

      https://retkomma.wordpress.com/2010/07/28/rocking-with-python/

      Br. Morten

  2. It appears that the formatting was altered, so do not expect the F# code to work without a little manipulation. Somehow part of the code was deleted (perhaps due to some F# symbols). Specifically, the PermutationsOfDegree function has some strange instructions indeed! I meant for that function to throw (raise) the NotImplementedException for the purpose of explaining the second part of the solution first. It also appears to be doing a fold operation, which was actually the single instruction of the DigitsToNumber function, which is nowhere to be found other than by hints. Now having stated that, and having anticipated that the same thing will occur with this posting attempt, I will repost the code with most of the comments removed (incidentally, upon testing the code this time, it completed consistently in about 6 seconds; the reason is attributable to rebooting my computer):

    let PermutationsOfDegree degree : int list list =
    (* The Distribute and Permute functions come from sections
    6.4.13 and 6.4.14 of Jon Harrop’s F# for Scientists;
    they are slightly changed, so any errors are mine. *)
    let rec Distribute e = function
    | [] -> [[e]]
    | x :: xs’ as xs ->
    (e :: xs) :: [ for xs in Distribute e xs’ -> x :: xs ]
    let rec Permute = function
    | e :: t -> List.concat (List.map (Distribute e) (Permute t))
    | [] -> [[]]
    Permute [1..degree];;

    let DigitsToNumber (digits:int seq) =
    digits |> Seq.fold (fun accum next -> 10 * accum + next) 0;;

    let MeetsCriteria (digits:int seq) =
    seq { 2..Seq.length digits }
    |> Seq.forall (fun m ->
    (digits |> Seq.take m |> DigitsToNumber) % m = 0);;

    let Compute =
    printfn “Computing…”
    PermutationsOfDegree 9
    |> List.filter (fun candidate -> candidate |> MeetsCriteria)
    |> List.map (fun digits -> digits |> DigitsToNumber);;

    • Thanks a lot for your update; it looks very exciting – to be honest I had some trouble making it work today, but I guess it had a natural explanation (and yeah, I love the wordpress html formatter as well…). I’ll definitely try it out tomorrow when I get near an F# installation and get a chance to digg into it:-)

    • To assist the reader in getting the indentation right, I have prefixed each line of code with the number of spaces you will need to insert. As a sidelight (and in case one is curious), the following LINQ code was used to lighten the effort (I used LINQPad (a free utility) to perform the operation):

      var q =
      from i in Regex.Split(code, “\r?\n”)
      let n = Regex.Match(i, @”^(\x20+)”)
      .Groups[1].Value.Length
      select n + “:” + i.Trim();

      q.Aggregate((a,n) => a + “\r\n” + n).Dump();

      ==Next, the F# code with indentation notes==

      0:let PermutationsOfDegree degree : int list list =
      4:(* The Distribute and Permute functions come from sections
      7:6.4.13 and 6.4.14 of Jon Harrop’s F# for Scientists;
      7:they are slightly changed, so any errors are mine. *)
      4:let rec Distribute e = function
      6:| [] -> [[e]]
      6:| x :: xs’ as xs ->
      8:(e :: xs) :: [ for xs in Distribute e xs’ -> x :: xs ]
      4:let rec Permute = function
      6:| e :: t -> List.concat (List.map (Distribute e) (Permute t))
      6:| [] -> [[]]
      4:Permute [1..degree];;
      0:
      0:let DigitsToNumber (digits:int seq) =
      4:digits |> Seq.fold (fun accum next -> 10 * accum + next) 0;;
      4:
      0:let MeetsCriteria (digits:int seq) =
      4:seq { 2..Seq.length digits }
      4:|> Seq.forall (fun m ->
      20:(digits |> Seq.take m |> DigitsToNumber) % m = 0);;
      4:
      0:let Compute =
      4:printfn “Computing…”
      4:PermutationsOfDegree 9
      4:|> List.filter (fun candidate -> candidate |> MeetsCriteria)
      4:|> List.map (fun digits -> digits |> DigitsToNumber);;

      • Thanks a lot for the very talented suggestion!

        For convenience – in the case anyone else wishes to play with this – I have saved your suggestion in a text file at http://www.box.net/shared/stfbuu008v.

        On my pc this executes in just a few seconds, and it seems that this is more dynamic than the LINQ expression, so I guess that I will definitely be looking more into functional programming🙂 Comparing it to the c++ example is really crazy..

        Once again, thanks a lot🙂

        Br. Morten

      • Is there any way you can move my latest comment to the end? I thought by clicking any of the “Reply” links it would do that for me automatically (as that is what seemed to have happened the last time).

      • Sorry, I just made another comment, so let me clarify. The comment I want moved, so that it follows your “May 4, 2010 at 2:38 pm” comment, is my comment dated “May 4, 2010 at 6:36 pm”. That is, if it is not too much trouble.

      • Hi, I’ve just taken a look at it – I don’t have much control over these WordPress features. Though, ff you repost it at the bottom I think that I can remove the “wrong” posts:-)

        Br. Morten

      • Here is the repost, so you may try to delete the other. Thanks.

        I have read that LINQ had some of its inspiration from functional programming, so one would expect to find similarities, and undeniably it shares characteristics with functional programming, but I am no expert in that regard. I think the important simplification of the problem was recognizing that the only possible set of candidates come from the set of all permutations of degree 9. At that point it easily becomes an exercise of brute force iteration through the set, so we can expect LINQ to perform nicely as well. Before I continue, I have a strong suspicion that the “greater than” symbol and the “less than symbol” are the culprits of the prior code deletion. For example, I suspect in the C++ code, those #include statements probably had such symbols, but they are not present in the code. Here are their HTML escape forms (minus the spacing and quotes): “& g t ;” and “& l t ;”. I’m not sure if that will help somehow. I mention this also because the C# code below contains the same characters, but I will replace them with something else; for the time being a less than symbol will be |L| and a greater than symbol will be |G|. Suppose we had a way, in C#, to generate all permutations. The following LINQ code, which is nearly in one-to-one correspondence with the F# code, will give us the answer we seek:

        // Horner’s method
        Func|L|IEnumerable|L|int|G|, int|G| digitsToNumber =
        digits =|G| digits.Aggregate(0, (a, n) =|G| 10 * a + n);

        var q =
        from p in PermutationsOfDegree(9)
        let meetsCriteria =
        // Be careful here. We could say (2, 8 ) and be like
        // the F# code, but the second argument here is “how
        // many” from the first agument, so to avoid a logical
        // error, we’ll test mod 1 as well (it is still very
        // fast).
        Enumerable.Range(1, 9)
        .All(m =|G| digitsToNumber(p.Take(m)) % m == 0)
        where meetsCriteria
        select p;

        foreach (var i in q)
        {
        Debug.WriteLine(digitsToNumber(i));
        }

        That’s pretty nice! (Don’t forget to clean up the |L| and |G| symbols.)

        We could use the C++ STL next_permutation function to generate all permutations, and call that from C#, since the .NET Framework easily accommodates such a solution, but instead, I will implement the method in C#. Here it is; don’t forget to remove the |L| and |G| symbols:

        // Based on Knuth algorithm L section 7.2.1.2 (see reference above).
        private static IEnumerable|L|int[]|G| PermutationsOfDegree(int degree)
        {
        LinkedList|L|int[]|G| permutations = new LinkedList|L|int[]|G|();
        int[] a = Enumerable.Range(0, degree + 1).ToArray();
        int n = a.Length – 1;
        while (a[0] == 0)
        {
        permutations.AddLast(a.Skip(1).ToArray());
        int j = n – 1;
        while (a[j] |G|= a[j + 1])
        {
        j–;
        }
        // According to Knuth the algorithm would terminate here if
        // j=0, but I put that in the while condition, so if there
        // are bugs, one might look here first.
        int l = n;
        while (a[j] |G|= a[l])
        {
        l–;
        }
        Interchange(a, j, l);
        int k = j + 1;
        l = n;
        while (k |L| l)
        {
        Interchange(a, k, l);
        k++;
        l–;
        }
        }
        return permutations;
        }
        private static void Interchange(int[] digits, int i, int j)
        {
        int t = digits[i];
        digits[i] = digits[j];
        digits[j] = t;
        }

  3. Hi friends,

    Nice to read it..I am newbie in LINQ world ….

    So can you just tell me where should I start to get a good jump to LINQ

    Thank you
    sandesh daddi
    http://www.sanshark.com

    • I found Pro LINQ: Language Integrated Query in C# 2008 (Windows.Net) by Joseph C. Rattz to be of great use. I also see there is a 2010 version of that book due in June 2010, but I wouldn’t place any bets that you’ll see the book come out on the expected publish date (not because of the book or publisher, but simply because it is safe to assume that such deadlines are difficult to meet). I searched a little, but I could not confirm the following notion: I think the newer version of that book will discuss the parallel concepts of LINQ. So my advice is tentatively: Buy an inexpensive used version of the 2008 edition (if you just cannot wait, and I do not advise you to wait), but be on the lookout for the 2010 edition. You may also be interested in LINQPad, which is a free application for quickly implementing LINQ programs (and other .NET technology). It is found here: http://www.linqpad.net/. One of the creators of LINQPad, Joseph Albahari, has authored, along with Ben Albahari, the excellent C# in a Nutshell editions, namely and presently is C# 4.0 in a Nutshell: The Definitive Reference. I do not own it yet, but I own version 3.0, and it has nice coverage of LINQ, and I think it is a safe bet that the version 4.0 book covers parallel LINQ. The description of the book that I read stated that it covers parallel concepts, but I do not know enough about C#4.0 to know what parallel concepts outside of LINQ may exist, so we’ll just leave it at the 99.999% level of certainty.

  4. Pingback: Rocking with Python « Linguistic forms

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s