'abccdadba' contains 50 palindromes, not all unique. Examples are: 'a' at positions 0,-4, and -1. 'aa' at (0,4),(5,-1), and (5,-1) The longest is 'abdadba' This code counts the palindromes in the data variable.
Python, 57 lines
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | '''
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)
|
I participated in an http://www.annauniv.edu/ college of engineering programming competition. They asked me to post my solution to the palindrome question. So I figure, stick it here!
With memoization the program is quite fast. Because of my choice of global/local variables the result store is a little bit clever.
Tags: palindrome
The problem statement required single characters, as well as all duplicates to count as separate palindromes.
'abb' contains 'a', 'b', 'b', and 'bb'
Roger Hui points out the number of contiguous substrings in a length 9 sequence is "Since the string has 9 the number of substrings is only 45 (+/\1+i.9)" (Executable Iverson notation, www.jsoftware.com .) the problem statement needs clarification. For this problem the substrings needn't be contiguous. Since substrings length 0 aren't useful, the number combinations is 1 less than the sum of a row of Pascal's triangle, so there are <:2^9 (again, j notation) strings to check as palindromes.