Given an integer n, generate the nth count and say sequence

Question

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

Answer 1

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

Answer 2

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