l = [1, 2, 3, 4, 5, 6, 7, 8, 9] n = reduce(lambda s, x: s*10 + x, l) print l, n
Archive for September, 2009
Python: From a list of digits, to a number
Tuesday, September 22nd, 2009Python: Multiple Replace
Monday, September 14th, 2009Create the dictionary used for the substitusions.
repl_dict = {'a': "aRbFR", 'b': "LFaLb"}
Pre-compile the regular expression.
regex = re.compile("(%s)" % "|".join(map(re.escape, repl_dict.keys())))
Create some text, and do the replace on it.
old = "Fa" new = regex.sub(lambda mo: repl_dict[mo.string[mo.start():mo.end()]], old)
In the example below you can see the evolution of the string which describes the Heighway Dragon at n-th step.
import re
repl_dict = {'a': "aRbFR", 'b': "LFaLb"}
regex = re.compile("(%s)" % "|".join(map(re.escape, repl_dict.keys())))
d = "Fa"
n_iterations = 5
for i in xrange(n_iterations + 1):
if i == 0: d = "Fa"
else: d = regex.sub(lambda mo: repl_dict[mo.string[mo.start():mo.end()]], d)
[ source: Active State Code ]
Python: next_permutation()
Sunday, September 13th, 2009The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.
Find the highest index i such that s[i] < s[i+1]. If no such index exists, the permutation is the last permutation.
# given s (a list of elements)
for i in reversed(xrange(len(s))):
if s[i] > s[i-1]:
break
else:
return []
i -= 1
Find the highest index j > i such that s[j] > s[i]. Such a j must exist, since i+1 is such an index.
for j in reversed(xrange(i + 1, len(s))): if s[j] > s[i]: break
Swap s[i] with s[j].
t = s[i] s[i] = s[j] s[j] = t
Reverse all the order of all of the elements after index i
s[i + 1:] = reversed(s[i + 1:])
And now the entire function:
def next_permutation(s):
for i in reversed(xrange(len(s))):
if s[i] > s[i-1]:
break
else:
return []
i -= 1
for j in reversed(xrange(i + 1, len(s))):
if s[j] > s[i]: break
t = s[i]
s[i] = s[j]
s[j] = t
s[i + 1:] = reversed(s[i + 1:])
return s
[ source: Wikipedia ]
Python: for .. else
Saturday, September 12th, 2009
r = [1, 3, 5, 11, 55, 89]
for elem in r:
if elem == 15:
print 'Found an element equal to 15'
break
else:
print 'Given array does not contain any elements equal to 15'
Dynamic Programming: Maximum Subarray Sum
Monday, September 7th, 2009Let’s say we are given an array of integers. What (contiguous) subarray has the largest sum? For example, if our array is [1, 2, -5, 4, 7, -2] then the subarray with the largest sum is [4, 7] with a sum of 11.
# read the array from stdin
vect = map(int, raw_input().split(' '))
# bounds of optimal subarray
(j, k) = (0, 1)
# left bound using for summing elements
l = 0
# sum of the elements of the optimal subarray
best = vect[0]
# sum of the elements from l to current position
sum = vect[0]
for i in xrange(1, len(vect)):
sum += vect[i]
if sum < 0: # selected subarray is not convenient
l = i + 1
sum = 0
elif sum > best:
best += vect[i]
(j, k) = (l, i)
print vect[j:k + 1]
[ source: 20bits.com ]
Python: double for loop statement
Sunday, September 6th, 2009Imagine you have a N x M matrix and you need to loop over each element of it.The first thing coming into my mind was to use a double for loop such as:
# ...
for i in xrange(N):
for j in xrange(M):
# do some action with element (i, j)
# ...
Now imagine to put this double-for statement inside a single-for one because you need to repeat the same action, let’s say, T times:
# ...
for t in xrange(T):
for i in xrange(N):
for j in xrange(M):
# do some action with element (i, j)
# ...
Wait a moment: is all i have written necessary? Why should i need to generate all the M elements every-time? Here is a pretty solution:
def Cross(a, b):
for i in a:
for j in b:
yield (i, j)
# ...
for t in xrange(T):
for (i, j) in Cross(xrange(N), xrange(M)):
# do some action with element (i, j)
# ...
[ source: Google Code Jam ]