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?)
 
 
 
 */


func logger(_ s: CustomStringConvertible) {
    
    print(s)
}

class Solution {
    var perf = 0
    
    
    
//    func concat(key: Int, cache: Cache, s: String) -> Cache {
//        
//        
//        
//        var newCache = cache
//        let halfKey = key / 2
//        let olds = cache[halfKey]!
//        let start = halfKey
//        let end = s.count - halfKey
//        
//        guard halfKey <= 0 else { return cache }
//        guard start >= 0 && end <= s.count - 1 && end >= start else { return cache }
//        
//        for i in start...end {
//            
//            guard let p = olds[i] else { continue }
//            
//            let left = i - 1
//            let right = (i + lastTwoKey + 1)
//            
//            let leftChar = s.safeStr(i: left)
//            let rightChar = s.safeStr(i: right)
//            
//            if leftChar == rightChar {
//                let newValue = leftChar + p + rightChar
//                newCache[key]![i - 1] = newValue
//            }
//        }
//        
//        
//        return newCache
//    }
    
    
    
    func expandTwos(cache: Cache, s: String) -> Cache {
        
        perf += 1
        
        var newCache = cache
        
        let olds = cache[1]!
        let start = 0
        let end = s.count - 1 - 1
        
        guard start >= 0 && end <= s.count - 1 && end >= start else { return cache }
        
        for i in start...end {
            
//            guard let p = olds[i] else { continue }
            
            perf += 1
            
            let left = i
            let right = (i + 1)
            
            let leftChar = s.safeStr(i: left)
            let rightChar = s.safeStr(i: right)
            
            if leftChar == rightChar {
                let newValue = leftChar + rightChar
                newCache[2]![i] = newValue
            }
        }
        
        return newCache
        
        
    }
    
    func expandEven(key: Int, cache: Cache, s: String) -> Cache {
        
        perf += 1
        
        var newCache = cache
        let lastTwoKey = key - 2
        let olds = cache[lastTwoKey]!
        let start = 1
        let end = (s.count - 1) - lastTwoKey
        
        logger("expand even")
        logger(start)
        logger(end)
        
        
        for i in start...end {
            
            perf += 1
            
            guard let p = olds[i] else { continue }
            
            let left = i - 1
            let right = (i + (lastTwoKey - 1) + 1)
            
            let leftChar = s.safeStr(i: left)
            let rightChar = s.safeStr(i: right)
            
            if leftChar == rightChar {
                let newValue = leftChar + p + rightChar
                newCache[key]![i - 1] = newValue
            }
        }
        
        return newCache
    }
    
    func expandOdd(key: Int, cache: Cache, s: String) -> Cache {
        
        perf += 1
        
        var newCache = cache
        let twoAgoKey = key - 2
        let olds = cache[twoAgoKey]!
        let delta = (twoAgoKey / 2) + 1
        
        let start = delta // needs to expand 1 left, so start 1 inset
        let end = s.count - delta - 1 // need -1 here?
        
        guard start >= 0 && end <= s.count - 1 && end >= start else { return cache }
        
        logger("expand odd")
        logger(start)
        logger(end)
        
        for i in start...end {
            
            perf += 1
            
            guard let p = olds[i] else { continue }
            
            let left = (i - delta)
            let right = (i + delta)
            
            let leftChar = s.safeStr(i: left)
            let rightChar = s.safeStr(i: right)
            
            if leftChar == rightChar {
                let newValue = leftChar + p + rightChar
                newCache[key]![i] = newValue
            }
        }
        
        return newCache
    }

    
    
    func longestPalindrome(_ s: String) -> String {
        
        perf += 1
  
        var cache = Cache()
        var onesCache = CachedPalindromes()
        s.enumerated().forEach { onesCache[$0.offset] = String($0.element) }
        cache[1] = onesCache
        
        cache[2] = CachedPalindromes()
        cache = expandTwos(cache: cache, s: s)
        var key = 3
        
        
        while true {
            perf += 1
            
            cache[key] = CachedPalindromes()
            
            if key % 2 == 0 {
                let expanded = expandEven(key: key, cache: cache, s: s)
                cache = expanded
            } else {
                let updated = expandOdd(key: key, cache: cache, s: s)
                cache = updated
            }
            
//            print(key)
//            print(cache[key])
            
            key += 1

            if key > s.count { break }
        }
        
        if s.isEmpty {
            return ""
        } else if s.count == 1 {
            return String(s.first!)
        }
        
        
        for i in (2...s.count).reversed() {
            perf += 1
            if let vals = cache[i] {
                for i in 0..<s.count {
                    if let p = vals[i] {
                        return p
                    }
                }
            }
        }
        
        if let first = s.first {
            return String(first)
        }

        fatalError()
    }
}




let input = "abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababa"





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

//assertCompletePallindrome(input)

fatalError()


//let bigInput2 = "XOOXOOXOOXOOX"
//let bigInput2 = "XXOOXX"

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


//assertCompletePallindrome(bigInput2)


//
//assert(Solution().longestPalindrome("321123211232112") == "21123211232112")
assert(Solution().longestPalindrome("44444444444444443333333334444444444444444") == "44444444444444443333333334444444444444444")
assert(Solution().longestPalindrome("auieo") == "a")
assert(Solution().longestPalindrome("a") == "a")
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)
//
//