14. Count And Say

This problem was recently asked by Google: A look-and-say sequence is defined as the integer sequence beginning with a single digit in which the next term is obtained by describing the previous term. An example is easier to understand:

1      #
11     # one 1's
21     # two 1's
1211   # one 2, and one 1.
111221 # one 1, one 2, and two 1's.

Your task is, return the term of this sequence.

def look_and_say(num):
  result = '1'
  for _ in range(1, num):
    new_rsult = '' # new_rsult = '12'
    chr = result[0] # chr = '1'
    count = 0
    for c in result: # '1', '2'
      if chr == c: 
        count += 1
      else:
        new_rsult += str(count) + chr # '11'
        count = 1
        chr = c # '2'

    result = new_rsult + str(count) + chr #'1112'

  return result

print(look_and_say(5))

The time-complexity of a recursive algorithm like this is tricky to calculate. But, we can see that the numbers are growing exponentially in length intuitively

This indicates exponential time-complexity. In actuality (according to wikipedia), the precise value is that the length grows by λ = 1.303577269034 each generation

1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211
11131221133112132113212221
3113112221232112111312211312113211
1321132132111213122112311311222113111221131221
11131221131211131231121113112221121321132132211331222113112211