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)]

Upright

It sounds like you're asking about the fish slapping dance. That combines Monty Python and Morris Dancing... :-) – Astridastride

If this thing didn't require at least 10 characters i would've just responded with :D – Upright

why are you both yield()ing and storing values on a[] ? – Compaction

the most unpythonic about this is the use of single letters for important names – Inveterate

@javier: for no good reason. @javier and @hop: yes, i know, it was quick and dirty code. – Upright

Answer 1

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

Plywood

thank you much. i really, really need to learn the iterools library better – Upright

Answer 2

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!

Inveterate