Welcome, guest | Sign In | My Account | Store | Cart

'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
 ``` 1 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,  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. David Lambert (author) 13 years, 4 months ago

The problem statement required single characters, as well as all duplicates to count as separate palindromes.

'abb' contains 'a', 'b', 'b', and 'bb' David Lambert (author) 10 years, 4 months ago

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. Created by David Lambert on Sat, 16 Jan 2010 (MIT)

### Required Modules

• (none specified)