import Foundation

func kakaoSolution1(n: Int, arr1: [Int], arr2: [Int]) -> [String] {
    func convertBinary(number: Int) -> String {
        var number = number
        var result = String(repeating: "0", count: n-1)
        var binary = String()

        while number >= 2 {
            binary.insert(Character(String(number % 2)), at: binary.startIndex)
            result.remove(at: result.startIndex)
            number = number / 2
        }
        binary.insert(Character(String(number)), at: binary.startIndex)
        result += binary
        return result
    }

    var result = [String]()
    for i in 0..<n {
        let binary1 = convertBinary(number: arr1[i]).characters.map { $0 }
        let binary2 = convertBinary(number: arr2[i]).characters.map { $0 }

        var str = String()
        for j in 0..<n {
            if binary1[j] == "1" || binary2[j] == "1" {
                str += "#"
            } else {
                str += " "
            }
        }
        result.append(str)
    }
    return result
}

func kakaoSolution2(score: String) -> Int {
    func splitScores(score: String) -> [[String?]] {
        var scores = [String]()
        var bonus = [String]()
        var option = [String?]()
        var one = String()
        for char in score.characters {
            if let num = Int(String(char)) {
                if num == 1 {
                    one = String(char)
                } else {
                    if one == "1" && char == "0" {
                        one += String(char)
                        scores.append(one)
                    } else {
                        if one == "1" {
                            scores.append(one)
                        }
                        scores.append(String(char))
                    }
                    one = String()
                }
            } else {
                if char == "#" || char == "*" {
                    option.removeLast()
                    option.append(String(char))
                } else {
                    option.append(nil)
                    bonus.append(String(char))
                }
            }
        }
        return [scores, bonus, option]
    }

    let splitResult = splitScores(score: score)
    var sum = [Int]()

    for i in 0..<splitResult.count {
        guard let score = Int(splitResult[0][i]!),
            let bonus = splitResult[1][i] else { break }
        var tempScore = score

        switch bonus {
        case "D":
            tempScore *= tempScore
        case "T":
            tempScore *= tempScore * tempScore
        default:
            break
        }

        if let option = splitResult[2][i] {
            switch option {
            case "*":
                if !sum.isEmpty {
                    sum[sum.count-1] *= 2
                }
                tempScore *= 2
            default:
                tempScore = tempScore - (tempScore * 2)
            }
        }
        sum.append(tempScore)
    }
    return sum.reduce(0) { $0 + $1 }
}

func kakaoSolution3(cacheSize: Int, cities: [String]) -> Int {
    let cities = cities.map { $0.uppercased() }
    var cache = [String]()
    var runningTime = Int()

    for city in cities {
        if cache.contains(city) {
            runningTime += 1
        } else {
            runningTime += 5
        }
        cache.append(city)
        if cache.count > cacheSize {
            cache.removeFirst()
        }
    }
    return runningTime
}

func kakaoSolution6(m: Int, n: Int, board: [String]) -> Int {
    func removeBlock(board: [String]) -> [String] {
        var boardCopy = board

        for i in 1..<m {
            let top = board[i-1]
            let bottom = board[i]
            for j in 1..<n {
                let top1 = top.characters.index(top.startIndex, offsetBy: j-1)
                let top2 = top.characters.index(top.startIndex, offsetBy: j)
                let bottom1 = bottom.characters.index(top.startIndex, offsetBy: j-1)
                let bottom2 = bottom.characters.index(top.startIndex, offsetBy: j)
                if top[top1] == top[top2] && bottom[bottom1] == bottom[bottom2] && top[top2] == bottom[bottom2] {
                    boardCopy[i-1].replaceSubrange(top1...top1, with: " ")
                    boardCopy[i-1].replaceSubrange(top2...top2, with: " ")
                    boardCopy[i].replaceSubrange(bottom1...bottom1, with: " ")
                    boardCopy[i].replaceSubrange(bottom2...bottom2, with: " ")
                }
            }
        }
        return boardCopy
    }

    var board = removeBlock(board: board)
    for i in 1..<m {
        for j in 0..<n {
            let index = board[i].index(board[i].startIndex, offsetBy: j)
            if board[i][index] == " " {
                board[i].replaceSubrange(index...index, with: String(board[i-1][index]))
                board[i-1].replaceSubrange(index...index, with: " ")
                board = removeBlock(board: board)
            }
        }
    }
    return board.map{ $0.characters.filter { $0 == " " }.count }.reduce(0) { $0 + $1 }
}