gistfile1.txt

import Foundation

extension String {
    func safeStr(i: Int) -> String {
        guard i >= 0 && i < self.count else {
            fatalError()
        }
        return String(self[self.index(self.startIndex, offsetBy: i)])
    }
    func safeChar(i: Int) -> Character {
        guard i >= 0 && i < self.count else { fatalError() }
        return self[self.index(self.startIndex, offsetBy: i)]
    }
    func str(s: Int, e: Int) -> String {
        guard s >= 0 && s < self.count else { fatalError() }
        guard s <= e else { fatalError() }
        return String(self[index(startIndex, offsetBy: s)...index(startIndex, offsetBy: e)])
    }
}

typealias Palindrome = String
typealias PalindromeIndex = Int
typealias CachedPalindromes = [(PalindromeIndex, Palindrome)]
typealias PallindromeCacheIndex = Int
typealias Cache = [PallindromeCacheIndex: CachedPalindromes]

func pFormatted(_ p: [String?]) -> [(Int, String)] {
    
    let indexedAndCompacted = p.enumerated().flatMap { xs -> [(Int, String)] in
        if let e = xs.element {
            return [(xs.offset, e)]
        } else {
            return []
        }
    }
    
    return indexedAndCompacted
}


/*
 
 TODO: optimizations

 no n-squared in concats.  presort, or use arithmetic to more smartly go linear over candidate
 
 even/odd expand, pre-filter / limiter arrays to those that can grow.
 e.g. when we go to 35, we can remove all 34's (for even expanding), what about even concatting? (two key arrays for concat/expand  or merge/expand?)
 
 
 
 */

class Solution {
    var perf = 0
    
    func longestPalindrome(_ s: String) -> String {
  
        var cache = Cache()
  
        let firstPs = s.enumerated().map { ($0.offset, String($0.element))  }
        
        cache[1] = firstPs
        
        var key = 1
        
        while true {
            
            key += 1
            
            let isEven = key % 2 == 0
            let isOdd = !isEven
            
            cache[key] = CachedPalindromes()
            
            func concat(key: Int) -> [(Int, String)] {
                
                let olds = cache[key]!
                
                var news = [(Int, String)]()
                
                for p1 in olds {
                    
                    // TODO: N*N
                    for p2 in olds {
                        guard p2 != p1 else { continue }
                        
                        let larger = p1
                        let smaller = p2
                        
                        // larger == later
                        
                        if smaller < larger
                            && larger.0 - smaller.0 == key
                            && larger.1 == smaller.1
                        {
                            let newStr = smaller.1 + larger.1
                            news.append((larger.0 - key, newStr))
                            news.append(((larger.0 + key) - 1, newStr))
                        }
                    }
                }
                
                return news
            }
            
            
            
            func expandEven(key: Int) -> [(Int, String)] {
                
                if key == 0 { return [] }
                
                let olds = cache[key]!
                
                var news = [(Int, String)]()
                
                for old in olds {
                    
                    let expandsLeft = old.0 - 1 >= 0
                    guard expandsLeft else { continue }
                    
                    let expandsRight = old.0 + key <= s.count - 1
                    guard expandsRight else { continue }
                    
                    let expandsEquality = s.safeStr(i: old.0) == s.safeStr(i: old.0 + key)
                    guard expandsEquality else { continue }
                    
                    if expandsLeft && expandsRight && expandsEquality {
                        news.append(old)
                    }
                }
                
                return news
            }
            
//            func merge(key: Int) -> [(Int, String)] {
//
//                let olds = cache[key]!
//
//                for ps in olds {
//                    for ps2 in olds {
//                        guard ps2 != ps else { continue }
//
//                        if ps2.1
//
//                    }
//
//                }
//
//
//                return []
//            }
            
            
            func expandOdd(key: Int) -> [(Int, String)] {
            
                
                let olds = cache[key]!
                
                var news = [(Int, String)]()
                
                for old in olds {
                    
                    if old.0 - 1 >= 0
                        && old.0 + key + 1 < s.count - 1
                        && s.safeStr(i: old.0) == s.safeStr(i: old.0 + key + 1){
                        
                        news.append(old)
                    }
                }
                
                return news
            }
            
            
            
            
            
            if isEven {
                
                let r = concat(key: key / 2)
                cache[key]!.append(contentsOf: r)
                
                let r2 = expandEven(key: key - 2)
                cache[key]!.append(contentsOf: r2)
                
            } else {
                
//                let r = merge(key : (key - 2) + 1)
                
                

                let r2 = expandOdd(key: key - 2)
//                cache[key]! = r2
                
                cache[key]!.append(contentsOf: r2)
                
                
                
            }
            
            if key == s.count { break }
            
            continue
            
            
            
            // pause
//
//            if isEven {
//
//                // EVEN CONCAT
//
//                let halfKey = (key / 2)
//                let halfPallindromes = cache[halfKey]!
//
//                // since we're look to left, we start at key, it will find left by half key
//                var startingAt = halfKey
//                var endingAt = (s.count - 1) - (halfKey - 1) //remember key is off by 1 from index
//
//                if startingAt <= endingAt {
//
//                    for i in startingAt...endingAt {
//                        guard  let el = halfPallindromes[i] else { continue }
//                        if let toLeft = halfPallindromes[i - key] {
//                            if toLeft == el {
//                                let newValue = toLeft + el
//                                cache[key]![i - key] = newValue
//                                cache[key]![i + halfKey] = newValue
//                            }
//                        }
//                    }
//                }
//
//
//
//                // EVEN EXPAND
//                let lastEven = key - 2
//                startingAt = lastEven
//                endingAt  = (s.count) - lastEven
//
//                if startingAt <= endingAt {
//
//                    if let twoAgoPallindromes = cache[key - 2] {
//
//                        for i in startingAt...endingAt {
//                            guard let el = twoAgoPallindromes[i] else { continue }
//
//                            let toLeft = s.safeStr(i: i - 1)
//                            let toRight = s.safeStr(i: i + key + 1)
//
//                            if toLeft == toRight {
//                                cache[key]![i - 1] = toLeft + el + toRight
//                                cache[key]![i - key] = toLeft + el + toRight
//                            }
//                        }
//                    }
//                }
//
//
//            }
//
//
//            if isOdd {
//
//                // ODD MERGE
//
//                let halfKey = (key / 2) + 1
//                guard halfKey > 0 else { fatalError() }
//                let halfPallindromes = cache[halfKey]!
//                var startingAt = halfKey - 1
//                var endingAt = s.count - halfKey
//
//
//                // TODO: need this?
//                //                if startingAt > endingAt {
//                //                    endingAt = 0
//                //                    startingAt = 0
//                //                }
//
//                for i in startingAt...endingAt {
//                    guard i - 1 >= 0 && i + 1 < s.count else { fatalError() }
//
//                    if
//                        let leftMerge = halfPallindromes[i - 1],
//                        let rightMerge = halfPallindromes[i + 1] {
//
//                        if leftMerge == rightMerge {
//                            let merged = String(leftMerge.dropLast()) + rightMerge
//                            cache[key]![i - (halfKey - 1)] = merged
//                            cache[key]![i + (halfKey - 1)] = merged
//                        }
//                    }
//                }
//
//                // ODD EXPAND
//
//                // no worry about 1's. (no-op)
//                let twoAgoKey = key - 2
//                let twoAgoPallindromes = cache[twoAgoKey]!
//
//                // we're expanding out 1 so contract insets
//                startingAt = twoAgoKey
//                endingAt = (s.count - twoAgoKey) - 1
//
//
//                // TODO: need this?
////                if startingAt > endingAt {
////                    endingAt = 0
////                    startingAt = 0
////                }
//
//                for i in startingAt...endingAt {
//                    guard let el = twoAgoPallindromes[i] else { continue }
//
//                    let toLeft = s.safeStr(i: i - twoAgoKey)
//                    let toRight = s.safeStr(i: i + twoAgoKey)
//
//                    if toLeft == toRight {
//                        cache[key]![i] = toLeft + el + toRight
//                    }
//                }
//            }
//
//
//
//            if key == s.count { break }
        }
        
        
//        for i in (0...s.count).reversed()   {
//            let ps = cache[i]!
//
//            for p in ps {
//
//                if p != nil {
//                    return p!
//                }
//            }
//        }
        
        
        
        

        fatalError() // HAHAH
    }
}





let s = Solution()
//let r = s.longestPalindrome(input)
//print("answer \(r) in \(s.perf) steps")
//
func assertCompletePallindrome(_ p: String) {
    assert(Solution().longestPalindrome(p) == p)
}



let bigInput2 = "XOOX"


let r2 = s.longestPalindrome(bigInput2)
print(s.perf)
print(r2)





//
//assert(Solution().longestPalindrome("321123211232112") == "21123211232112")
//assert(Solution().longestPalindrome("44444444444444443333333334444444444444444") == "44444444444444443333333334444444444444444")

//assertCompletePallindrome("4333333334")
//assert(Solution().longestPalindrome("3210123210012321001232100123210123") == "3210123210012321001232100123210123")
//assert(Solution().longestPalindrome("aba") == "aba")
//assert(Solution().longestPalindrome("abcde") == "a")
//assert(Solution().longestPalindrome("aaabbbaaa") == "aaabbbaaa")
//assert(Solution().longestPalindrome("FaaabbbaaaG") == "aaabbbaaa")
//assert(Solution().longestPalindrome("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa") == "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa")
//assert(Solution().longestPalindrome("eabcb") == "bcb")
//assert(Solution().longestPalindrome("ac") == "a")
//
//
//assert(Solution().longestPalindrome("bbb") == "bbb")
//assert(Solution().longestPalindrome("bbbbb") == "bbbbb")
//assert(Solution().longestPalindrome("bbbb") == "bbbb")
//assert(Solution().longestPalindrome("bbbbbb") == "bbbbbb")
//
//assert(Solution().longestPalindrome("aaabbbbaaa") == "aaabbbbaaa")
//
//
//assertCompletePallindrome("aaaaaaaaaaaaaa")
//
//assertCompletePallindrome("aabbaabbaabbaabbaa")
//assertCompletePallindrome("")
//
//assert(Solution().longestPalindrome("a") == "a")
//assert(Solution().longestPalindrome("aa") == "aa")
////
////
//let bigInput = "321012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210123210012321001232100123210123"
//let bigExpectation = "321012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210123"
//
//
//
//let r2 = s.longestPalindrome(bigInput)
////
//print("input")
//print(bigInput)
////
//print("my result")
//print(r2)
////
//print("expected")
//print(bigExpectation)
////
////print(r.count)
////print(bigExpectation.count)
////
//assert(r2 == bigExpectation)
//
//