Improve pandigital algorithm

Question

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

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 — Vlad Preda
– Vlad Preda, Commented Sep 21, 2013 at 12:00
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 :) — Vlad Preda
– Vlad Preda, Commented Sep 22, 2013 at 9:22
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. — SylvainD
– SylvainD, Commented Sep 22, 2013 at 11:10

SylvainD · Accepted Answer · 2013-09-21 11:48:33Z

4

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

edited Sep 21, 2013 at 11:48

answered Sep 21, 2013 at 10:06

SylvainD

29.8k1 gold badge49 silver badges93 bronze badges

\$\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
– Vlad Preda

2013-09-21 11:30:10 +00:00
Commented Sep 21, 2013 at 11:30
\$\begingroup\$ I edited the post to be a bit more clear on the numbers I am looking for \$\endgroup\$

Vlad Preda
– Vlad Preda

2013-09-21 11:58:34 +00:00
Commented Sep 21, 2013 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
– Vlad Preda

2013-09-21 12:29:16 +00:00
Commented Sep 21, 2013 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
– Vlad Preda

2013-09-22 09:19:40 +00:00
Commented Sep 22, 2013 at 9:19

Add a comment |

Vedran Šego · Accepted Answer · 2013-09-21 12:16:56Z

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.

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 :) — Vlad Preda
– Vlad Preda, Commented Sep 21, 2013 at 12:24

Stack Exchange Network

Improve pandigital algorithm

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Improve pandigital algorithm

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions