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, [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.

2 comments

David Lambert (author) 14 years, 2 months ago  # | flag

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) 11 years, 2 months ago  # | flag

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)
Python recipes (4591)
David Lambert's recipes (1)

Required Modules

  • (none specified)

Other Information and Tasks