[exercise] Palindromes

[Matthew Fernandez]

Sorry things are running a bit late due to my disorganisation over the
holiday season. For this month I'm setting the following task: write a
function that determines whether a string is a palindrome (the same
forwards and backwards).

For those who want something more advanced: write a function that
returns the longest palindromic substring of a given string. E.g. The
input "hello world" would generate output "ll". I can't immediately
think of an efficient algorithm for doing this, so I'd be interested
to see what you come up with.

If you have something you'd like to talk about for next month's tools,
let me know. Otherwise I'll regale you all with tales of Bamboo, a
regression test server.

[Tom Allen]

My attempt in (bad) Python.

#!/usr/bin/env python

# coding: utf-8

"""

Returns true if a given string is palindromic.

Tom Allen, 22nd Nov, 2011

"""

import sys

from math import floor

def IsPalindromic( string ):

# Returns true if a given string is palindromic.

safeString = str(string).lower()

for i in range(0, int(floor(len(safeString)/2)) ):

if safeString[i] != safeString[len(safeString)-i-1]:

return False

return True

if __name__ == '__main__':

if IsPalindromic(sys.argv[1]):

sys.stdout.write("String \'"+sys.argv[1]+"\' is a palindrome.")

else:

sys.stdout.write("String \'"+sys.argv[1]+"\' is not a palindrome.")

Cheers,

Tom

[Matthew Fernandez]

Nice, but why do you convert the string to lower case?

[Tom Allen]

The spec was incomplete, so I made an assumption... :-)

[Matthew Fernandez]

Assumptions are always welcome :)

Some tidbits before my attempt:
- I discovered http://altdevblogaday.com/ today, a great blog about
game development. The authors are of mixed experience and expertise,
but all quite good writers. If you need a better reason, John Carmack
blogs here.
- Many of us have been using Python as a lingua franca for algorithms
on this list. Is anyone in favour of another language to use as the
common denominator? I know Julian's vote is for Ruby.

My attempt follows below. It's pretty ugly, but I was after a solution
that was O(n^2). I'm not thoroughly convinced of its correctness and
suggestions are welcome.

#!/usr/bin/env python
import sys

# Start and end indicies of the largest palindrome found thus far.
max_start = 0
max_end = 0

s = sys.stdin.read()

for i in range(0, len(s) - 1): # For each character in s.

# Find the largest palindrome with an odd number of letters beginning with
# the single character we are currently looking at.
odd_end = odd_start = i
while odd_start != -1 and odd_end != len(s) and s[odd_start] == s[odd_end]:
odd_start -= 1
odd_end += 1

# If the one found was greater than the current leader...
if odd_end - odd_start - 2 > max_end - max_start:
max_start = odd_start + 1
max_end = odd_end - 1

if i < len(s) - 1:
# Find the largest palindrome with an even number of letters beginning
# with the current character and the next character.
even_start = i
even_end = i + 1
while even_start != -1 and even_end != len(s) and
s[even_start] == s[even_end]:
even_start -= 1
even_end += 1

# If the one found was greater than the current leader...
if even_end - even_start - 2 > max_end - max_start:
max_start = even_start + 1
max_end = even_end - 1

sys.stdout.write('The largest palindrome is: "%s"\n' % s[max_start:max_end + 1])