CODEWITHSUNDEEP
pythonoptimization
Tam Coton
Tam Coton

Reputation: 864

How do I optimise this Python code?

I'm doing a coding challenge for fun and to work on my skills - some of you may remember the Advent of Code challenge from last December, I'm working through that. I've got this code as the solution to one of the problems, which works, but it's uselessly slow.

inp = "1113122113"

def iterate(num):
    pos = 0
    new = ""
    while pos < len(num):
        counter = 0
        d = num[pos]
        for i in range(pos, len(num)):
            if num[i] == d:
                counter += 1
            else:
                break
        new+=str(counter)
        new+=str(d)
        pos += counter
    print len(new)
    return new

for i in range (50):
    inp = iterate(inp)

Past iteration 35 or so, it gets to the point where it's taking several minutes for each iteration. The object is to generate a look-and-say sequence - so 1 goes to 11, then 21, 1211, 111221, 3112211 and so on. I need to find the length of the string after the 50th iteration, but it's 360154 characters long after 40 iterations and my code just isn't optimised enough to handle strings that long in a reasonable time. Can anyone give me some pointers?

Upvotes: 0

Views: 106

Answers (1)

Patrick Haugh
Patrick Haugh

Reputation: 60944

Using itertools.groupby will make this very fast.

from itertools import groupby
def next_say(s):
    return ''.join(str(sum(1 for _ in g))+k for k, g in groupby(s))

def iterate(num):
    """Generator that yields the first num iterations"""
    val = '1'
    for i in range(num):
        val = next_say(val)
        yield val

https://docs.python.org/2/library/itertools.html#itertools.groupby

Upvotes: 1

Related Questions