From: Steven D'Aprano on
On Wed, 19 May 2010 22:58:22 +0200, superpollo wrote:

> In [266]: del(sum)


del is a statement, not a function, so the brackets are pointless. This
is like writing:

x = (1)

instead of

x = 1

`del sum` is all you need.



--
Steven
From: Steven D'Aprano on
On Wed, 19 May 2010 21:58:04 +0200, superpollo wrote:

> ... how many positive integers less than n have digits that sum up to m:
>
> In [197]: def prttn(m, n):

Does the name "prttn" mean anything? I'm afraid I keep reading it as a
mispelling of "print n".


[...]
> s = str(i)
> sum = 0
> for j in range(len(s)):
> sum += int(s[j])

Rather than iterating over an index j = 0, 1, 2, ... and then fetching
the jth character of the string, you can iterate over the characters
directly. So the inner loop is better written:

for c in s:
sum += int(c)




--
Steven
From: Richard Thomas on
For this kind of problem you should avoid all that stringification. I
find it best to deal with sequences of digits of a fixed length and go
from there. For example:

def count1(m, n, cache={}):
"""Number of digit sequences of length `n` summing to `m`."""
if n < 0 or m < 0:
return 0
elif n == 0:
return int(m == 0)
elif (m, n) in cache:
return cache[m, n]
# This is an optimisation using the combinatoric choose function.
#elif m < 10:
# result = choose(n + m - 1, n - 1)
else:
result = 0
for digit in xrange(min(10, m + 1)):
result += count1(m - digit, n - 1)
cache[m, n] = result
return result

Notice the caching of results. With this we can compute the required
thing quite easily:

def count2(m, n):
"""Number of numbers less than `n` whose digits sum to `m`."""
result = 0
digits = map(int, str(n))
length = len(digits)
for idx, digit in enumerate(digits):
for seq_digit in xrange(digit):
seq_limit = m - seq_digit
seq_length = length - idx - 1
result += count1(seq_limit, seq_length)
m -= digit
return result

Essentially we move through the number left to right, choose digits
less than the digit in the number and count digit sequences to fill
the remainder. Then fix the actual digit and step forward.

An approach like this avoids the relatively slow stringification
process and makes decent use of caching and iteration (both easy and
efficient in Python).

In [1]: count2(25, 10000)
Out[1]: 348

In [2]: timeit count2(25, 10000)
100000 loops, best of 3: 12.6 us per loop
From: John Posner on
On 5/19/2010 5:51 PM, Steven D'Aprano wrote:
> On Wed, 19 May 2010 21:58:04 +0200, superpollo wrote:
>
>
> Rather than iterating over an index j = 0, 1, 2, ... and then fetching
> the jth character of the string, you can iterate over the characters
> directly. So the inner loop is better written:
>
> for c in s:
> sum += int(c)
>

Or, as a one-liner (and not shadowing the built-in *sum* function):

mysum = sum(map(int, str(i)))

-John
From: superpollo on
Steven D'Aprano ha scritto:
> On Wed, 19 May 2010 22:58:22 +0200, superpollo wrote:
>
>> In [266]: del(sum)
>
>
> del is a statement, not a function, so the brackets are pointless. This
> is like writing:
>
> x = (1)
>
> instead of
>
> x = 1
>
> `del sum` is all you need.

sorry about that, thanks a lot!

bye