On 01/23/2012 05:55 PM, Steven D'Aprano wrote:
On Mon, Jan 23, 2012 at 10:01:33PM +0000, Alan Gauld wrote:
Just to be clear this has nothing to do with Python. It doesn't matter
what programming language you choose there is not a PC on Earth that can
do what you want using the technique you are using in 16 seconds.
I don't believe that you could do it with the fastest supercomputer on
earth. If you have to test 10**18 numbers in 16/10**5 seconds, that
gives you less than 0.0000000000002 nanoseconds per test.
This isn't a question of tweaking the code to make it run faster, you
need a fundamentally different approach to the problem, as Alan says.
Either that, or we have completely misunderstood the constraints of the
puzzle.
I gave such an example approach, at 1:42 (actually, much earlier, but I
forgot to change my send-from field, so Tutor bounced my message). You
can search for the message using the string "to do all the possible 18
digit numbers".
I can solve the problem of finding how many lucky numbers in the entire
range 1 through 10**18 in a reasonable time. I haven't coded the entire
algorithm, but most of it exists, and takes 97 seconds for generating
and testing for luckiness the 4,686,824 possible distinct sets of
digits. Thus my outer loop goes around 4.6 million times, rather than
10**18 times. Incidentally, I made the 18 an argument to main(), so
it's easy to test on smaller values.
What I generate are all possible lists of digits, all of length 18, in
which the digits are in sorted order. All that remains is multiplying
the 1 or 0 for each of these 4.7 million lists by a
number-of-permutations figure, which shouldn't be too hard to get. It
would trivially be 18 factorial, except that there are variable numbers
of duplicates among those 18 digits. Anyway, I claim that it won't add
more than a few percent to finish the task. Call it 100 seconds. lots
more than the 16 seconds originally specified for doing it 10,000
times. There are undoubtedly ways to optimize my code; I made no real
attempt to be optimal. I just was worried about the algorithm.
Only catch is that we might not want all 10**18 numbers. If we want a
few million of them, all around 10**17, the original approach will work
fine. And if we want them all, my approach will work. I haven't come
up with a way to generalize either for things like "solve it for the
range 1234567890123456 through twice that value".
--
DaveA
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
