2
\$\begingroup\$

I am solving interview questions from here.

Problem : Given an integer n, generate the nth count and say sequence. The count-and-say sequence is the sequence of integers beginning as follows: 1, 11, 21, 1211, 111221, ...

1 is read off as one 1 or 11.

11 is read off as two 1s or 21.

21 is read off as one 2, then one 1 or 1211.

Note : The sequence of integers will be represented as a string.

Example: if n = 2, the sequence is 11.

How should I further optimize my solution?

def count_and_say(num):
        string = '11'
        cnt = 0
        new_string = []
        if num == 1:
            return "1"
        while num != 2:
            cnt += 1
            for i in range(len(string)):
                if i+1 != len(string):
                    if string[i] == string[i+1]:
                        cnt += 1
                    else:
                        new_string.append(str(cnt)+string[i])
                        cnt = 1
                else:
                    new_string.append(str(cnt)+string[i])
            cnt = 0
            num -= 1
            string = ''.join(new_string)
            new_string = []
        return string
\$\endgroup\$

2 Answers 2

4
\$\begingroup\$

In each step of the "count-and-say sequence" (which is more usually called the "look-and-say sequence") you have to find the groups of consecutive runs of identical digits. So if you have the value 111221, these groups are 111, 22, and 1. Python has a built-in function itertools.groupby for finding groups in an iterator, and using this function, the look-and-say step becomes:

new_value = ''
for digit, group in groupby(value):
    count = sum(1 for _ in group)
    new_value += str(count) + digit
value = new_value

which can be rearranged into a single expression:

value = ''.join(str(sum(1 for _ in group)) + digit
                for digit, group in groupby(value))

and so the whole sequence can be generated like this:

from itertools import groupby

def look_and_say(value='1'):
    "Generate the look-and-say sequence starting at value."
    while True:
        yield value
        value = ''.join(str(sum(1 for _ in group)) + digit
                        for digit, group in groupby(value))

To select only the \$n\$th value of the sequence, use itertools.islice:

next(islice(look_and_say(), n - 1, None))
\$\endgroup\$
3
\$\begingroup\$

Add tests

For this type of exercice, it is easy to write simple tests so that you can have a quick feedback when you break something as you write/rewrite your function.

If you do this as part of an interview, it'll show you have good habits.

You could use a proper test framework or just write simple code:

TESTS = {
    1:  '1',
    2:  '11',
    3:  '21',
    4:  '1211',
    5:  '111221',
    6:  '312211',
    7:  '13112221',
    8:  '1113213211',
    9:  '31131211131221',
    10: '13211311123113112211',
    11: '11131221133112132113212221',
    12: '3113112221232112111312211312113211',
    13: '1321132132111213122112311311222113111221131221',
    14: '11131221131211131231121113112221121321132132211331222113112211',
}

if __name__ == "__main__":
    for n, expected in TESTS.items():
        res = count_and_say(n)
        if res != expected:
             print("Error for %d : got %s expected %s" % (n, res, expected))

Style

Python has a style guide called PEP 8. Among other things, it gives guidelines about indentation. The recommendation is 4 spaces. (I am not sure if the 8 space indent was intended or not in your question).

Code re-organisation

You could re-order your condition checks and use elif to save a level of indentation.

You could define new_string = [] at the beginning of the while loop so that you do not need to reset it at the end of the loop.

def count_and_say(num):
    if num == 1:
        return "1"
    string = '11'
    cnt = 0
    while num != 2:
        new_string = []
        cnt += 1
        for i in range(len(string)):
            if i+1 == len(string):
                new_string.append(str(cnt)+string[i])
            elif string[i] == string[i+1]:
                cnt += 1
            else:
                new_string.append(str(cnt)+string[i])
                cnt = 1
        cnt = 0
        num -= 1
        string = ''.join(new_string)
    return string

Loop with the proper tools

Instead of using a convoluted while loop to perform n iterations, you could use a simple for loop.

Taking this chance to have cnt initialised at the beginning of the loop, we'd have something like:

def count_and_say(num):
    if num == 1:
        return "1"
    string = '11'
    for i in range(num - 2):
        cnt = 1
        new_string = []
        for i in range(len(string)):
            if i+1 == len(string):
                new_string.append(str(cnt)+string[i])
            elif string[i] == string[i+1]:
                cnt += 1
            else:
                new_string.append(str(cnt)+string[i])
                cnt = 1
        string = ''.join(new_string)
    return string

Loop with the proper tools

I highly recommend Ned Batchelder's talk "Loop like a native". Basically, anytime you use something like for xxx in range(len(yyy)), there is a better way to do it. In your case, enumerate can help you to write things in a clearer way.

Taking this chance to:

  • change how cnt works by being a bit more natural: set it to 0 and increment it in all cases

  • move the final iteration out of the loop

You'd get something like;

def count_and_say(num):
    if num == 1:
        return "1"
    string = '11'
    for i in range(num - 2):
        cnt = 0
        new_string = []
        for i, c in enumerate(string):
            cnt += 1
            if i+1 != len(string) and c != string[i+1]:
                new_string.append(str(cnt)+c)
                cnt = 0
        new_string.append(str(cnt)+c)
        string = ''.join(new_string)
    return string

Remove non-required edge cases

In the original code, we start from '11' and perform num-2 iterations. This is similar to starting from '1' and performing num-1 iterations. Then we don't need to handle num == 1 as a special case:

def count_and_say(num):
    string = '1'
    for i in range(num - 1):
        cnt = 0
        new_string = []
        for i, c in enumerate(string):
            cnt += 1
            if i+1 != len(string) and c != string[i+1]:
                new_string.append(str(cnt)+c)
                cnt = 0
        new_string.append(str(cnt)+c)
        string = ''.join(new_string)
    return string

Handle the prev, not the next

This is mostly a matter of personal preference but you could make you do not need to handle indices by working with the previous character instead of the next.

You'd get something like:

def count_and_say(num):
    string = '1'
    for i in range(num - 1):
        cnt = 0
        new_string = []
        prev_c = None
        for c in string:
            if prev_c is not None and prev_c != c:
                new_string.append(str(cnt)+prev_c)
                cnt = 0
            cnt += 1
            prev_c = c
        new_string.append(str(cnt)+c)
        string = ''.join(new_string)
    return string
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.