ansaurus

Question

Solving Combinatory Problems with LINQ /.NET4

Answer 1

+1 A:

Well for one thing, the last bit (concerning i9) is not necessary, since all permutations of 1-9 are divisible by 9...

BlueRaja - Danny Pflughoeft 2010-05-17 18:33:46

Answer 2

+1 A:

I don't think you can dramatically improve this query... It's actually pretty efficient already, because each step has much less possible combinations than the previous step.

What you could easily do is to factorize some code to make the query more readable. For instance, use a predicate that checks the algorithm invariant at each step, and a helper to build the numbers from the digits (rather than "inline" multiplications and additions).

Let's call Dn the digit at position N, and Xn the number made of D1...Dn. At each step N, the following statements should be true :

Dn isn't in [D1...D(n-1)]
Xn is divisible by N

In the following code, this invariant is implemented by the isValid delegate :

// Delegate with variable number of arguments
delegate TResult FuncWithParams<TArg, TResult>(params TArg[] args);

void Main()
{

    var oneToNine = Enumerable.Range(1, 9).ToArray();

    // Creates a number from its digits
    FuncWithParams<int, int> makeNumber =
        digits => digits.Aggregate(0, (acc, d) => acc * 10 + d);

    // Checks the invariant against a sequence of digits
    FuncWithParams<int, bool> isValid =
        digits => !digits.Take(digits.Length - 1).Contains(digits.Last())
                && makeNumber(digits) % digits.Length == 0;

    var query = 
        from d1 in oneToNine
        from d2 in oneToNine
        where isValid(d1, d2)
        from d3 in oneToNine
        where isValid(d1, d2, d3)
        from d4 in oneToNine
        where isValid(d1, d2, d3, d4)
        from d5 in oneToNine
        where isValid(d1, d2, d3, d4, d5)
        from d6 in oneToNine
        where isValid(d1, d2, d3, d4, d5, d6)
        from d7 in oneToNine
        where isValid(d1, d2, d3, d4, d5, d6, d7)
        from d8 in oneToNine
        where isValid(d1, d2, d3, d4, d5, d6, d7, d8)
        from d9 in oneToNine
        where isValid(d1, d2, d3, d4, d5, d6, d7, d8, d9)
        select makeNumber(d1, d2, d3, d4, d5, d6, d7, d8, d9);

    query.Dump();
}

Still pretty big, but much more readable than the original...

Thomas Levesque 2010-05-17 20:19:35

this is much easier on the eyes, but is is actually more performant?

slf 2010-05-19 15:14:21

No, it isn't. Actually, I think it's *slightly* slower than the original implementation, because of the overhead of delegate calls, but the difference is probably not big enough to notice

Thomas Levesque 2010-05-19 21:53:05

Answer 3

+2 A:

If you have access to an ImmutableList class, it can make a pretty short solution. Instead of trying each one at every stage, you pass only the remaining possibilities to the next state. Also, the number of calculations is reduced by keeping the totals at each stage.

Dim query = From i1 In Tuple.Create(0L, allNums).ChooseNextNumber(1)
            From i2 In i1.ChooseNextNumber(2) _
            From i3 In i2.ChooseNextNumber(3) _
            From i4 In i3.ChooseNextNumber(4) _
            From i5 In i4.ChooseNextNumber(5) _
            From i6 In i5.ChooseNextNumber(6) _
            From i7 In i6.ChooseNextNumber(7) _
            From i8 In i7.ChooseNextNumber(8) _
            From i9 In i8.ChooseNextNumber(9)
            Select i9.Item1

<System.Runtime.CompilerServices.Extension()> _
Private Function ChooseNextNumber(
      ByVal previous As Tuple(Of Integer, ImmutableList(Of Integer)),
      ByVal modulusBase As Integer) _
    As IEnumerable(Of Tuple(Of Integer, ImmutableList(Of Integer)))
    Return From i In previous.Item2
           Let newTotal = previous.Item1 * 10 + i
           Where newTotal Mod modulusBase = 0
           Select Tuple.Create(newTotal, previous.Item2.Remove(i))
End Function

Gideon Engelberth 2010-05-18 02:19:16

Even though I don't like the VB syntax, this is very elegant solution... +1 !

Thomas Levesque 2010-05-19 21:57:39

ansaurus

tags:

views:

answers:

Solving Combinatory Problems with LINQ /.NET4

related questions