3
\$\begingroup\$

First of all, I am a beginner in Python trying to learn optimizations and proper coding standards.

Here is a snippet of code that checks if a number follows the rule: first AND last N digits contain all unique numbers from 1 to N, but in any order. This also means that in either first N or last N digits, each number appears exactly once.

import time

start_time = time.time()


def is_pandigital(nr, n):
    digits = ''.join(map(str, range(1, n + 1)))
    nr = str(nr)
    for i in digits:
        if str(i) not in nr[0:9]:
            return False
        if str(i) not in nr[-9:]:
            return False

    return True

assert is_pandigital(1423, 4) is True
assert is_pandigital(1423, 5) is False
assert is_pandigital(14235554123, 4) is True
assert is_pandigital(14235552222, 4) is False # !important
assert is_pandigital(1444, 4) is False
assert is_pandigital(123564987, 9) is True

pandigitals = []
# this loop is strictly for benchmarking is_pandigital
for i in range(100000, 999999):
    if is_pandigital(i, 6):
        pandigitals.append(i)

print pandigitals

print time.time() - start_time, "seconds"

When running this, the result is:

[123456, .......]
2.968 seconds

Process finished with exit code 0

The code seems to work fine, but it doesn't appear to be very efficient. Would you have any tips to improve it? Any piece of code and/or idea would be highly appreciated.

PS: I chose this loop so that any improvements to the is_pandigital function would be immediately obvious.

Example of numbers I am looking for:

321XXXXXXXXXXXXXXX132 - good

321XXXXXXXXXXXXXXX133 - not good, because the last 3 digits dont contain 1, 2 and 3

231 - good

\$\endgroup\$
  • \$\begingroup\$ Pandigital numbers have a somewhat different definition. \$\endgroup\$ – Vedran Šego Sep 21 '13 at 10:13
  • \$\begingroup\$ That is true, I worded the issue a bit weird, sorry about that. Re-wrote it slightly so it doesn't conflict with the definition of pandigital numbers. This is part of a problem on projecteuler.net \$\endgroup\$ – Vlad Preda Sep 21 '13 at 12:00
  • \$\begingroup\$ Out of curiosity, which problem is this ? \$\endgroup\$ – SylvainD Sep 21 '13 at 23:48
  • \$\begingroup\$ It was problem 104, which requested the first Fibonacci number for which the first 9 + last 9 digits were 1-9 pandigital. The script still ran for 10h before finding the result :) \$\endgroup\$ – Vlad Preda Sep 22 '13 at 9:22
  • \$\begingroup\$ 10 hours for a PE problem: you're probably doing it wrong. You can have a look at the thread now that you have a solution. An easy improvement you could/should do is to remove the n parameter as it will always be 9 and pre compute the set of numbers from 1 to 9. \$\endgroup\$ – SylvainD Sep 22 '13 at 11:10
4
\$\begingroup\$

You can rewrite your asserts without comparing to True and False:

assert is_pandigital(1423, 4)
assert not is_pandigital(1423, 5)
assert is_pandigital(14235554123, 4)
assert not is_pandigital(14235552222, 4) # !important
assert not is_pandigital(1444, 4)
assert is_pandigital(123564987, 9)

You can rewrite your benchmark with list comprehension:

# this loop is strictly for benchmarking is_pandigital
pandigitals = [i for i in range(100000, 999999) if is_pandigital(i, 6)]

Now for the algorithm itself, I must confess that I have troubles understanding what you want to do as you seem to be calling "pandigital" two different things. In any case, I have the feeling that something is wrong in your code, it seems like :

   if str(i) not in nr[0:9]:
        return False
    if str(i) not in nr[-9:]:
        return False

should be

    if str(i) not in nr[0:n]:
        return False
    if str(i) not in nr[-n:]:
        return False

and

assert not is_pandigital(9999912399999, 3)

should provide you some hints.

I'll go deeper in the code once you confirm that my understanding is correct.

Edit : I have to go, no time to run benchmarks but here are the improvements. I kept different versions to that you can take ideas out of it.

def is_pandigital(nr, n):
    nr = str(nr)
    beg=nr[0:n]
    end=nr[-n:]
    for i in map(str, range(1, n + 1)):
        if i not in beg or i not in end:
            return False
    return True

def is_pandigital(nr, n):
    nr = str(nr)
    beg=set(nr[0:n])
    end=set(nr[-n:])
    return beg==end and beg==set(map(str, range(1, n + 1)))
\$\endgroup\$
  • \$\begingroup\$ Awesome! Especially the list comprehension, which I didn't know about. The n instead of 9 fix (code initially was used to check only pandigital numbers with length 9) also fixed the assert you mentioned. \$\endgroup\$ – Vlad Preda Sep 21 '13 at 11:30
  • \$\begingroup\$ I edited the post to be a bit more clear on the numbers I am looking for \$\endgroup\$ – Vlad Preda Sep 21 '13 at 11:58
  • 1
    \$\begingroup\$ First solution - an average of 2.4 seconds (pretty big improvement), and second version has 4.2 seconds. I'll see if I can improve on your code, thank you \$\endgroup\$ – Vlad Preda Sep 21 '13 at 12:29
  • \$\begingroup\$ I managed to solve the projecteuler.net problem using your improvement. The rest of the script probably was pretty bad, since it found the result after running 10 hours, but I got it! Thank you \$\endgroup\$ – Vlad Preda Sep 22 '13 at 9:19
1
\$\begingroup\$

I'd try by sorting digits:

def adapt_nr(nr):
    nr = [ int(i) for i in list(nr) ]
    nr.sort()
    return nr

def is_pandigital(nr, n):
    nr = str(nr);
    if len(nr) < n: return False
    chk = list(range(1, n+1))
    if adapt_nr(nr[0:n]) != chk: return False
    if adapt_nr(nr[-n:]) != chk: return False
    return True

A built-in sort is quick, and all that is left to compare is that the obtained lists of digits are equal to [1,..,n].

The check itself might be faster if done with strings instead of lists:

def adapt_nr(nr):
    nr = [ int(i) for i in list(nr) ]
    nr.sort()
    return ''.join([str(i) for i in nr])

def is_pandigital(nr, n):
    nr = str(nr);
    if len(nr) < n: return False
    chk = ''.join(str(i) for i in list(range(1, n+1)))
    if adapt_nr(nr[0:n]) != chk: return False
    if adapt_nr(nr[-n:]) != chk: return False
    return True

You'll have to benchmark for yourself.

I'm a beginner in Python, so some of this can probably be written in a more pythonic way. I'll edit if I get such suggestions in the comments.

\$\endgroup\$
  • 1
    \$\begingroup\$ Quite interesting solutions. The first has an average of 6 seconds run time, while the second has an average of 10 seconds, so in this situations lists are better than strings :) \$\endgroup\$ – Vlad Preda Sep 21 '13 at 12:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.