'''
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)
