[Tutor] OverflowError in lucky numbers script
d at davea.name
Mon Jan 23 19:42:19 CET 2012
On 01/23/2012 08:13 AM, Shreesh bhat wrote:
> I tried optimizing everything all things you guys pointed out and
> still its
> orders of magnitude away from the expected result.
> The program should check the islucky condition between range of
> numbers and iterate over that 10**5 times.
> This program slows down more than 16 secs at (1,10**8) and 1 time.
> Which approach should i follow?
You said the two end points of the range were less than 10**18, but I
didn't realize you really wanted to do the entire range, meaning first
number is 1 and last is 10**18. To do that 100,000 times in 10 secs
would mean you have to process 10**12 items per CPU clock cycle.
That's so far beyond possible that it's clear another approach is
If you're literally going to do all the possible 18 digit numbers, then
perhaps you should be doing a combinational approach. For example, once
you know whether 38 is lucky, you also know whether 83, 380, 300008000,
and 80030 are lucky. So you test all possible ordered strings the way
you're doing it now, and multiply each (0 or 1) by the number of ways
those digits could be permuted in an 18 digit space (adding zeroes in
various places, and of course reordering numbers).
So we're looking for a bunch of lists of 18 ints, where each of the int
is between 0 and 9, and with a further constraint that the digits
increase in a non-strict monatonic way. You could do that with an 18
level nested for-loop, or you could do it with recursion. Anyway, the
number of total loops changes from 10**18 to something more manageable,
basically a time roughty factorial complexity.
Once you've written that set of loops (prob. done with recursion, so it
can do a variable-sized list), you need a function that tests "is-lucky"
and another that calculates the number of permutations of that
particular combinations of terms.
More information about the Tutor