Can anyone provide a more pythonic way of generating the morris sequence?
Question
I'm trying to generate the morris sequence in python. My current solution is below, but I feel like I just wrote c in python. Can anyone provide a more pythonic solution?
def morris(x):
a = ['1', '11']
yield a[0]
yield a[1]
while len(a) <= x:
s = ''
count = 1
al = a[-1]
for i in range(0,len(al)):
if i+1 < len(al) and al[i] == al[i+1]:
count += 1
else:
s += '%s%s' % (count, al[i])
count = 1
a.append(s)
yield s
a = [i for i in morris(30)]
Solution
itertools.groupby
seems to fit perfectly! Just define a next_morris
function as follows:
def next_morris(number):
return ''.join('%s%s' % (len(list(group)), digit)
for digit, group in itertools.groupby(str(number)))
That's all!!! Look:
print next_morris(1)
11
print next_morris(111221)
312211
I could use that to make a generator:
def morris_generator(maxlen, start=1):
num = str(start)
while len(num) < maxlen:
yield int(num)
num = next_morris(num)
Usage:
for n in morris_generator(10):
print n
results:
1
11
21
1211
111221
312211
13112221
OTHER TIPS
from itertools import groupby, islice
def morris():
morris = '1'
yield morris
while True:
morris = groupby(morris)
morris = ((len(list(group)), key) for key, group in morris)
morris = ((str(l), k) for l, k in morris)
morris = ''.join(''.join(t) for t in morris)
yield morris
print list(islice(morris(), 10))
First of all I'd make the iterator infinite and let the consumer decide, how much of it he wants. That way he could either get every morris number that is shorter than x or the first x numbers, etc.
Then there is obviously no need to store the whole list of previous morris numbers in a list, since the recursion is only n := f(n-1)
anyway.
Lastly, using itertools to give it a functional touch is always worth a geek point or two ;) I split the generator expression into several lines to make it a bit easier on the eye.
The main ugliness in this solution comes from the fact that len()
can't be called on an iterator and gives us an int where we need a str. The other hickup is the nested str.join) to flatten the whole thing into a str again.
If you want to start the sequence from arbitrary numbers, define the function like this:
def morris(morris=None):
if morris is None:
morris = '1'
[...]
If you want to turn around that generator, you can write it like this:
def morris():
morris = '1'
yield morris
while True:
print morris
morris = ''.join(''.join(t)
for t in ((str(len(list(group))), key)
for key, group in groupby(morris)))
yield morris
I'm not sure i like the splitting into two functions, but this seems to be the most readable solution:
def m_groupby(s):
for key, group in groupby(s):
yield str(len(list(group)))
yield key
def morris():
morris = '1'
yield morris
while True:
morris = ''.join(m_groupby(morris))
yield morris
Hope you like it!