Velocity Reviews > Palindrome

# Palindrome

Guest
Posts: n/a

 11-14-2003
On Fri, 14 Nov 2003 11:51:02 GMT, Ron Adam <(E-Mail Removed)>
wrote:

>
>"""
>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)

Alan Kennedy
Guest
Posts: n/a

 11-14-2003
> 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[i] != p[plen-i-1]:
return False
return True

regards,

--
alan kennedy
-----------------------------------------------------
email alan: http://xhaus.com/mailto/alan

Guest
Posts: n/a

 11-14-2003
On Fri, 14 Nov 2003 14:34:23 +0000, Alan Kennedy <(E-Mail Removed)>
wrote:

>
>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[i] != 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[i] == 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
Guest
Posts: n/a

 11-14-2003
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
http://www.velocityreviews.com/forums/(E-Mail Removed)

Andrew Dalke
Guest
Posts: n/a

 11-15-2003
Skip:

...

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

palindrome_skip 89.5211577111
palindrome_dalke 11.1900866758

Andrew
(E-Mail Removed)

import re, timeit

p = re.sub(r'\W','',p.lower())
i = len(p)//2
while i and p[i] == 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),
("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():
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
"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()