'''
Level: Medium

The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

countAndSay(1) = "1"
countAndSay(n) is the way you would "say" the digit string from countAndSay(n-1),
which is then converted into a different digit string.

To determine how you "say" a digit string,
split it into the minimal number of groups so that each group
is a contiguous section all of the same character.
Then for each group, say the number of characters, then say the character.
To convert the saying into a digit string,
replace the counts with a number and concatenate every saying.

For example, the saying and conversion for digit string "3322251":

"../../../Material/countandsay.jpeg"

Given a positive integer n, return the nth term of the count-and-say sequence.



Example 1:

Input: n = 1
Output: "1"
Explanation: This is the base case.
Example 2:

Input: n = 4
Output: "1211"
Explanation:
countAndSay(1) = "1"
countAndSay(2) = say "1" = one 1 = "11"
countAndSay(3) = say "11" = two 1's = "21"
countAndSay(4) = say "21" = one 2 + one 1 = "12" + "11" = "1211"


Constraints:

1 <= n <= 30

'''

'''

5 -> 11 + 12 + 21 = 111221
6 -> 31 + 22 + 11 = 312211

'''


class Solution(object):

    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        from itertools import groupby
        say_map = {}
        def rec(n):

            k = [list(j) for i, j in groupby(say_map[str(n)])]
            res = ""
            for x in k:
                res += "{}{}".format(len(x), x[0])
            return res
        if n == 1:
            return "1"

        say_map["1"] = "1"
        for i in range(1, n):
            res_next = rec(i)
            say_map[str(i+1)] = res_next
            if i == n-1:
                return res_next



n = 4
assert "1211" == Solution().countAndSay(n)
print(Solution().countAndSay(30))
