import Foundation

/*
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.
Given an integer n, generate the nth sequence.
*/
/*
Thinking:
遍历数字，得到Count, Number（用栈结构，每次取出上一个数字，相同则计数，不同则Append )
计算完后展平，得到新的数字，
然后重复
*/

func countAndSay(_ n: Int ) -> String {
    //计算出 (count, Number)
    guard  n > 0 else {
        return "0"
    }

    let nStr = String(1)

    var stackArray: [(Int, Character)] = [(Int, Character)]()

    func pushStack(_ c: Character) {
        if let last = stackArray.last {
            if (last.1 == c) {
                let count = last.0 + 1
                stackArray[stackArray.count - 1] = (count, last.1)
            } else {
                stackArray.append((1, c))
            }
        } else {
            stackArray.append((1, c))
        }
    }

    func emptyStack() {
        stackArray.removeAll()
    }

    func stackToString() -> String {
        var strArray: [String] = [String]()

        for value in stackArray {
            strArray.append(String(value.0))
            strArray.append(String(value.1))
        }

        emptyStack()
        return strArray.joined()
    }

    func calc(_ nStr: String) -> String {
        for c in nStr.characters {
            pushStack(c)
        }

        return stackToString()
    }

    var newString = nStr
    for _ in (0 ..< n-1) {
        newString = calc(newString)
    }

    return newString
}

//print(countAndSay(0))
//print(countAndSay(1))
print(countAndSay(3))