Rocking with Python

Python and Ruby have been so hyped in the .NET community for the last couple of months so I decided to attempt to solve this problem using IronPython – originally inspired by a Linq solution posted by Octavio Hernandes.

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).

I was amazed when I first saw how easy Linq could solve this problem. But … then I found Python. Now – check this out:

import clr
import IronPython.Modules

def validate(n, denominator):
     if denominator == 1: return True
     if int(n) % denominator != 0: return False
     return validate(n[:len(n)-1], denominator - 1)

for x in IronPython.Modules.PythonIterTools.permutations("123456789"):
     joined = ''.join(x)
     if validate(joined, 9): print(joined)

10 lines – slam dunk! Since this is my first Python code lines ever, I apologize to the Python purists in advance – but hey, I just had to advocate this 🙂 And yes, it does perform.

For a comparison between Linq and C++ solutions please check out my earlier block post on this. Remember to go though the comments where an F# solution is also suggested.


4 responses to “Rocking with Python

  1. This is only a test. I want to see if I can correctly delineate angle brackets in WordPress (please feel free to delete this posting).

    &gr; <
    < >
    Func<IEnumerable, int>
    Func<IEnumerable<int>, int>
        Func<IEnumerable<int>, int>

  2. I like it: Succinct and understandable.

    I did a lot of writing previously, so I may have concealed a concise LINQ version of the solution, which was essentially the same as the F# solution. In the code below, the PermutationsOfDegree method is merely a placeholder and must be implemented for the solution to work (e.g.: via the C++ STL permutation function, or the IronPython permutation function you used, or the C#/F# solutions I implemented at the original posting page). For comparison, here is that LINQ solution (hopefully I did a better job formatting it this time):

    // Horner's method
    Func<IEnumerable<int>, int> digitsToNumber =
        digits => digits.Aggregate(0, (a, n) => 10 * a + n);

    // Query
    var q =
        from p in PermutationsOfDegree(9)
        let meetsCriteria = Enumerable.Range(1, 9)
            .All(m => digitsToNumber(p.Take(m)) % m == 0)
        where meetsCriteria
        select digitsToNumber(p).ToString();

    // Output
    Debug.Write(q.Aggregate((a, n) => a + "\r\n" + n));

  3. I was recently reading the Python documentation and it became apparent (and it is also stated explicitly) that Python supports functional programming, so the question arose how a Python functional solution might appear. Here is one such realization:

    import clr
    from IronPython.Modules.PythonIterTools import permutations
    from IronPython.Modules.FunctionTools import partial

    def Compute():
        modList = range(9, 0, -1) # i.e.: [9,8,7,6,5,4,3,2,1]
        test = lambda p, m: int(”.join(p[:m])) % m == 0
        criteria = lambda p: all(map(partial(test, p), modList))
        for i in filter(criteria, permutations(‘123456789’)):

    The execution is not so fast, but still less than a minute, and in this case it is sufficient for me.

  4. Good to see non-Python users advocating Python!

    The last solution here (in python) is not as clean as searching through the permutations, but it runs instantly.

Leave a Reply

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

You are commenting using your 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