in [Python]

From: Steven D'Aprano on 19 May 2010 17:45 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 19 May 2010 17:51 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 19 May 2010 21:36 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 19 May 2010 23:40 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 20 May 2010 10:37
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 |