Welcome, guest | Sign In | My Account | Store | Cart
    '''
        Level 8 palindrome solution.
    
        Re: LEVEL 8
        by KannanKV on Wed Jan 13, 2010 11:17 pm
    
        hi lambertdw , you can post it after the contest is over at
        Jan 16, [2010] 9:00 P.M I.S.T ... Thank you for your patience !!
    
        Consider pairs.
    '''
    
    data = 'abccdadba'                      # test phrase has 50 palindromes.
    
    pairs = [(i,j,)for(i,a,)in enumerate(data)
             for j in range(i+1,len(data))if a==data[j]]
    
    intermediates = [j-i-1 for (i,j,) in pairs]
    
    # table[row][col] is True iff [pair number row] surrounds [pair number col]
    table = [[0,]*len(pairs)for pair in pairs]
    for (I,(i,l,),) in enumerate(pairs):
        for (J,(j,k,),) in enumerate(pairs):
            table[I][J] = (i < j) and (k < l)
    
    
    # all pairs occur once.  I chose to treat the zero pair separately.
    # another approach would be to surround the entire data string by
    # a sentinel character, such as space " "
    occurrences = [1 for pair in pairs]     # occurrences of pairs
    
    
    # recursive memo-ized function modifies global pair occurrences count.
    def f(k,d={},):
        if k in d:                          # may be faster with try/except
            L = d[k]
            for i in range(len(pairs)):     # loop can be shortened with more logic
                occurrences[i] += L[i]      # since we need start from k+1
            return
        enclosed = table[k]
        L = occurrences[:]
        for j in range(k+1,len(pairs)):
            if enclosed[j]:
                occurrences[j] += 1
                f(j)
        d[k] = [new-old for (new,old,) in zip(occurrences,L)]
    
    for k in range(len(pairs)):             # account for even palindromes from
        f(k)                                # all pairs.
    
    evens = sum(occurrences)
    odds = (
        len(data)
        +sum(occurrence*intermediate
             for (occurrence,intermediate,) in zip(occurrences,intermediates,)))
    
    print('Palindromes:',evens+odds)

History