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

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


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


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