Prev: Delete files from FTP Server older then 7 days. Using ftputil andftplib.
Next: struct
From: Bryan on 22 May 2010 10:18
I wrote:
> I came up with a recursive memo-izing algorithm that
> handles 100-digit n's.
[...]

I made a couple improvements. Code below.

-Bryan

#---------------------

_nds = {}
def ndsums(m, d):
""" Count d-digit ints with digits suming to m.
"""
assert m >= 0 and d >= 0
m = min(m, d * 9 - m) # exploit symmetry
if m < 0:
return 0
if m == 0 or d == 1:
return 1
if (m, d) not in _nds:
_nds[(m, d)] = sum(ndsums(m - i, d - 1)
for i in range(min(10, m + 1)))
return _nds[(m, d)]


def prttn(m, n):
assert m >= 0 and n > 0
count = 0
dls = [int(c) for c in reversed(str(n))]
while dls:
msd = dls.pop()
count += sum(ndsums(m - d, len(dls)) for
d in range(min(msd, m + 1)))
m -= msd
return count


#----------------------
# Testing

from bisect import bisect_right

def slow_prttn(m, n):
return sum(1 for k in range(m % 9, n, 9)
if sum(int(i) for i in str(k)) == m)

_sums = [0, {}]
def tab_prttn(m, n):
upto, sums = _sums
if n >= upto:
for i in range(upto, n):
dsum = sum(int(c) for c in str(i))
sums.setdefault(dsum, []).append(i)
_sums[0] = n
if m not in sums:
return 0
return bisect_right(sums[m], n - 1)

for n in range(1, 1234567):
digits = [int(c) for c in str(n)]
for m in range(9 * len(digits)):
count = tab_prttn(m, n)
assert prttn(m, n) == count
if n < 500:
assert slow_prttn(m, n) == count
if count == 0:
break
if n % 1000 == 0:
print('Tested to:', n)
From: Raymond Hettinger on 24 May 2010 10:14
On May 19, 12:58 pm, superpollo <ute...(a)esempio.net> wrote:
> ... how many positive integers less than n have digits that sum up to m:
>
> In [197]: def prttn(m, n):
>      tot = 0
>      for i in range(n):
>          s = str(i)
>          sum = 0
>          for j in range(len(s)):
>              sum += int(s[j])
>          if sum == m:
>              tot += 1
>      return tot
>     .....:
>
> In [207]: prttn(25, 10000)
> Out[207]: 348
>
> any suggestion for pythonizin' it?

Your code is readable and does the job just fine.
Not sure it is an improvement to reroll it into a one-liner:

def prttn(m, n):
return sum(m == sum(map(int, str(x))) for x in range(n))
>>> prttn(25, 10000)
348

Some people find the functional style easier to verify because of
fewer auxilliary variables and each step is testable independently.
The m==sum() part is not very transparent because it relies on
True==1, so it's only readable if it becomes a common idiom (which it
could when you're answering questions of the form "how many numbers
have property x").

If speed is important, the global lookups can be localized:

def prttn(m, n, map=itertools.imap, int=int, str=str, range=range):
return sum(m == sum(map(int, str(x))) for x in range(n))

Raymond



From: Jean-Michel Pichavant on 24 May 2010 10:50
Jerry Hill wrote:
> On Wed, May 19, 2010 at 3:58 PM, superpollo <utente(a)esempio.net> wrote:
>
>> ... how many positive integers less than n have digits that sum up to m:
>>
> ...
>
>> any suggestion for pythonizin' it?
>>
>
> This is how I would do it:
>
> def prttn(m, n):
> """How many positive integers less than n have digits that sum up to m"""
> total = 0
> for testval in range(n):
> sumofdigits = sum(int(char) for char in str(testval))
> if sumofdigits == m:
> total += 1
> return total
>
> I added a docstring to the function, saying what it does, and what the
> arguments are supposed to represent. I also moved the
> convert-to-string-and-sum-the-digits logic into a single generator
> expression that's passed to the builtin sum function. Oh, and I tried
> to use slightly more expressive variable names.
>
>
my favorite solutio nso far.

@ OP

What means prttn ? is it any Dutch word :D ? m & n are also very poors
argument names.
I will be difficult to name properly the function, as it is doing
something ... I don't find the word, something like un-intuitive. Sounds
like homework.

def how_many_positive_integers_less_than_n_have_digits_that_sum_up_to_m(m, n)


:o)

JM

PS : read http://tottinge.blogsome.com/meaningfulnames/

<http://tottinge.blogsome.com/meaningfulnames/>
From: Matteo Landi on 24 May 2010 10:51
What about avoiding the string conversion and use mod/div operations
in order to create a list of digits for a number?

Now that you have the sequences it's easy to count which sums up to m.

On Mon, May 24, 2010 at 4:14 PM, Raymond Hettinger <python(a)rcn.com> wrote:
> On May 19, 12:58 pm, superpollo <ute...(a)esempio.net> wrote:
>> ... how many positive integers less than n have digits that sum up to m:
>>
>> In [197]: def prttn(m, n):
>> tot = 0
>> for i in range(n):
>> s = str(i)
>> sum = 0
>> for j in range(len(s)):
>> sum += int(s[j])
>> if sum == m:
>> tot += 1
>> return tot
>> .....:
>>
>> In [207]: prttn(25, 10000)
>> Out[207]: 348
>>
>> any suggestion for pythonizin' it?
>
> Your code is readable and does the job just fine.
> Not sure it is an improvement to reroll it into a one-liner:
>
> def prttn(m, n):
> return sum(m == sum(map(int, str(x))) for x in range(n))
>>>> prttn(25, 10000)
> 348
>
> Some people find the functional style easier to verify because of
> fewer auxilliary variables and each step is testable independently.
> The m==sum() part is not very transparent because it relies on
> True==1, so it's only readable if it becomes a common idiom (which it
> could when you're answering questions of the form "how many numbers
> have property x").
>
> If speed is important, the global lookups can be localized:
>
> def prttn(m, n, map=itertools.imap, int=int, str=str, range=range):
> return sum(m == sum(map(int, str(x))) for x in range(n))
>
> Raymond
>
>
>
> --
> http://mail.python.org/mailman/listinfo/python-list
>



--
Matteo Landi
http://www.matteolandi.net/
From: superpollo on 24 May 2010 16:34
Jean-Michel Pichavant ha scritto:
> Jerry Hill wrote:
>> On Wed, May 19, 2010 at 3:58 PM, superpollo <utente(a)esempio.net> wrote:
>>
>>> ... how many positive integers less than n have digits that sum up to m:
>>>
>> ...
>>
>>> any suggestion for pythonizin' it?
>>>
>>
>> This is how I would do it:
>>
>> def prttn(m, n):
>> """How many positive integers less than n have digits that sum up
>> to m"""
>> total = 0
>> for testval in range(n):
>> sumofdigits = sum(int(char) for char in str(testval))
>> if sumofdigits == m:
>> total += 1
>> return total
>>
>> I added a docstring to the function, saying what it does, and what the
>> arguments are supposed to represent. I also moved the
>> convert-to-string-and-sum-the-digits logic into a single generator
>> expression that's passed to the builtin sum function. Oh, and I tried
>> to use slightly more expressive variable names.
>>
>>
> my favorite solutio nso far.
>
> @ OP
>
> What means prttn ?

i already answered this downthreads...

> something ... I don't find the word, something like un-intuitive. Sounds
> like homework.

it is not.
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5 6 7 8 9
Prev: Delete files from FTP Server older then 7 days. Using ftputil andftplib.
Next: struct