Palindrome

[Ron Adam]

"""
Test if a string is a palindrome.
"""
import re

def palindrome_test(p):
p = p.lower()
p = re.sub(r'\W','',p)
while p:
if p[:1] == p[-1:]:
p = p[1:-1]
else:
break
if (len(p) <= 1):
return True
else:
return False

I notice right after I posted it, I can simplify the test function a
bit more.

import re
def palindrome_test(p):
p = p.lower()
p = re.sub(r'\W','',p)
while p and p[:1] == p[-1:]:
p = p[1:-1]
return (len(p) <= 1)


_Ron Adam

 

[Alan Kennedy]

I notice right after I posted it, I can simplify the test function a
bit more.

import re
def palindrome_test(p):
p = p.lower()
p = re.sub(r'\W','',p)
while p and p[:1] == p[-1:]:
p = p[1:-1]
return (len(p) <= 1)

Ron,

If I were going to follow this approach, I would try to eliminate any
copying, like so:

def palindrome_test(p):
p = p.lower()
p = re.sub(r'\W','',p)
plen = len(p)
for i in xrange(plen/2):
if p != p[plen-i-1]:
return False
return True

regards,

 

[Ron Adam]

If I were going to follow this approach, I would try to eliminate any
copying, like so:

def palindrome_test(p):
p = p.lower()
p = re.sub(r'\W','',p)
plen = len(p)
for i in xrange(plen/2):
if p != p[plen-i-1]:
return False
return True

regards,

Good point. Ok, how about like this?

"""
Test if a string is a palindrome.
"""
import re
def palindrome_test(p):
p = re.sub(r'\W','',p.lower())
i = len(p)//2
while i and p == p[-i-1]: i -= 1
return not i

palindrome_list = [
"A",
"ab",
"Oo!",
"Bolton",
"This is not a palindrome!",
"Was it a car or a cat I saw?",
"No 'H' type, mate, no spot stops one tame python!",
"A man, a plan, a cat, a ham, a yak, a yam, a hat, a
canal--Panama!",
]

for p in palindrome_list:
print '"'+p+'"',
if palindrome_test(p):
print 'is a palindrome.'
else:
print 'is not a palindrome.'

 

[Andrew Dalke]

Alan Kennedy

The possibility of the same feature occurred to me. However, I'm still
not sure if this would solve the problem. How would the "pivot point"
be recognised by such an augmented regex engine? i.e. how would it
recognise the point at which it should stop capturing, reverse the
sequence and start matching again?

Back-tracking. Suppose there was such a thing as
(.*).?\~1
where the \~1 matches the reverse of the first group.
Now match that pattern against
NOON

The (.*) matches all the way up to "NOON" then tries and
failes to match both the .? and the \~1

It backtracks one so that
(.*) matches "NOO"
and the N remains. The .? matches the N but the \~1 does not
so it backtracks so that the .? matches nothing, but still the \~1
does not match the N.

It backtracks another so that
(.*) matches "NO"
and the "ON" remains. The .? first matches with the "O" leaving
the "N", but \~1 doesn't match that, so it backtracks so that
the .? matchs nothing, leaving "ON" for the \~1. This matches!

In other words, it goes through a lot of work to do the matching,
and would take O(N) backtracks to work.

But that's not quite correct. An implementation is free to
analyze the pattern and notice that it's being asked to search
for a palindrome then insert special case code for that pattern.

Perhaps one would need to also implement a feature whereby the length
of the entire string could be made available within expressions, so
that the size of a capture group could be limited to the first half of
the string? I.E. Something along the lines of

^(.{strlen/2}).?\~1$

Yup. That would work as well. There are all sorts of
special things one could capture in a regex-like language.
Perl 'solves' it by allowing any match to call out to embedded
Perl code, which is free to tell the matcher to stop or
continue matching.

One of these days I'll find the time to dig out my old course notes
and books :#)

Friedl's regexp book (from ORA) is quite good.

Andrew
(e-mail address removed)

 

[Andrew Dalke]

Skip:

Oh, then how about:

...

At the end are the three solutions I saw posted, from Ron Adam,
Skip, and me (modified). The times are

palindrome_adam 128.152670758
palindrome_skip 89.5211577111
palindrome_dalke 11.1900866758

Andrew
(e-mail address removed)


import re, timeit


# from Ron Adam
def palindrome_adam(p):
p = re.sub(r'\W','',p.lower())
i = len(p)//2
while i and p == p[-i-1]: i -= 1
return not i

# from Skip Montanaro
def palindrome_skip(s):
s = re.sub("[^A-Za-z0-9]+", "", s).lower()
return s == s[::-1]

# from Andrew Dalke
foldcase = []
punctuation = []
for i in range(256):
c = chr(i)
if c.isalnum(): # note 'alnum' instead of 'alpha' ...
foldcase.append(c.lower())
else:
foldcase.append(c)
punctuation.append(c)
foldcase = "".join(foldcase)
punctuation = "".join(punctuation)
del c, i

def palindrome_dalke(s):
t = s.translate(foldcase, punctuation)
return t == t[::-1]

verify_data = [
("A man, a plan, a canal -- Panama!", True),
("1234", False),
("123321", True),
("12321", True),
("Madam, I'm Adam.", True),
("A", True),
("ab", False),
("Oo!", True),
("Bolton", False),
("This is not a palindrome!", False),
("Was it a car or a cat I saw?", True),
("No 'H' type, mate, no spot stops one tame python!", True),
("A man, a plan, a cat, a ham, a yak, a yam, a hat, a canal--Panama!",
True),
]

def verify():
for tester in (palindrome_adam, palindrome_skip,
palindrome_dalke):
for s, result in verify_data:
assert tester(s) == result, (tester, s)
print "Verified"

_time_val = None

def find_times():
global _time_val
_time_val = verify_data[-1][0] # the long "a man, a plan ... Panama"
one
for tester in ("palindrome_adam", "palindrome_skip",
"palindrome_dalke"):
timer = timeit.Timer(setup = "import __main__ as M",
stmt = "M." + tester + "(M._time_val)")
t = timer.timeit()
print tester, t

if __name__ == "__main__":
verify()
find_times()