Solving Combinatory Problems with LINQ /.NET4
- by slf
I saw this article pop-up in my MSDN RSS feed, and after reading through it, and the sourced article here I began to wonder about the solution.
The rules are simple:
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:
The number should be divisible by 9.
If the rightmost digit is removed, the remaining number should be divisible by 8.
If the rightmost digit of the new number is removed, the remaining number should be divisible by 7.
And so on, until there's only one digit (which will necessarily be divisible by 1).
This is his proposed monster LINQ query:
// C# and LINQ solution to the numeric problem presented in:
// http://software.intel.com/en-us/blogs/2009/12/07/intel-parallel-studio-great-for-serial-code-too-episode-1/
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);
Octavio states "Note that no attempt at all has been made to optimize the code", what I'd like to know is what if we DID attempt to optimize this code. Is this really the best this code can get? I'd like to know how we can do this best with .NET4, in particular doing as much in parallel as we possibly can. I'm not necessarily looking for an answer in pure LINQ, assume .NET4 in any form (managed c++, c#, etc all acceptable).
