Palindrome

[Ben Finney]

Re: Palindrome

On Thu, 13 Nov 2003 23:16:50 GMT, Andrew Dalke wrote:[color=blue]
> Gerrit Holl[color=green]
>> Are you looking for:
>> 20:58:42:232:0 >>> def ispalindrome(s) :
>> 20:58:42:232:0 ... return s == s[::-1][/color]
>
> No. The OP wanted to strip special characters and normalize case, so
> that A man, a plan, a canal -- Panama! would be allowed as a
> palindrome.[/color]

Here's mine.

I have yet to try this on the world's longest palindrome:

<http://www.norvig.com/palindrome.html >

=====
#!/usr/bin/env python

""" Module for palindrome determination
"""

import string

def is_palindrome( str ):
""" Determine if str is a palindrome
"""

# Assume false until proven otherwise
is_pal = False

# Remove punctuation and whitespace
passthrough_tbl = string.maketran s( '', '' )
remove_chars = string.whitespa ce + string.punctuat ion
str = string.translat e( str, passthrough_tbl , remove_chars )

# Remove capitalisation
str = string.lower( str )

# Determine if massaged string matches its reverse
is_pal = ( str == str[::-1] )

return is_pal


if( __name__ == '__main__' ):
candidates = [
"",
"Foo",
"FooF",
"Foof",
"Foxof",
"Madam, I'm Adam.",
"Ten animals I slam in a net.",
"Lapses? Order red roses, pal.",
"A man, a plan, a canal -- Panama!",
"Satan, oscillate my metallic sonatas.",
"Eva, can I stack Rod's sad-ass, dork cats in a cave?",
]
for str in candidates:
print ( "'%s':" % str ),
print is_palindrome( str )

=====

--
\ "I wish I had a dollar for every time I spent a dollar, because |
`\ then, yahoo!, I'd have all my money back." -- Jack Handey |
_o__) |
Ben Finney <http://bignose.squidly .org/>

[Peter Otten]

Re: Palindrome

Ben Finney wrote:
[color=blue]
> I have yet to try this on the world's longest palindrome:
>
> <http://www.norvig.com/palindrome.html >[/color]
[color=blue]
> is_pal = ( str == str[::-1] )[/color]

For really long palindromes, you might not want to reverse the whole string:

p.endswith(p[:len(p)//2:-1])

Peter

[Alan Kennedy]

Re: Palindrome

[Alan Kennedy][color=blue][color=green]
>> ... There must be some way to have a
>> single fixed regular expression that can be used to test every
>> palindrome.[/color][/color]

[Andrew Dalke][color=blue]
> There isn't such a way. Regular expressions cannot match
> strings of the form a**n b**n a**n (pumping lemma). That's
> a palindrome so there are palindromes which cannot be
> matched by regular expressions.[/color]

Thanks Andrew.

I read up on the topic after posting yesterday (because I had this
vague niggling doubt). After finding that what you stated above is
true, I realised that the vague niggling doubt was actually the memory
of my old compiler-theory lecturer laughing at me :-D

Here's a nice page I found that discusses this and other related
topics.

FINITE STATE AUTOMATA AND REGULAR EXPRESSIONS

http://www.cs.princeton.edu/introcs/71regular/

[color=blue]
> There are tricks. "regular expressions" aren't actually regular
> and can be used to match things like a**n b**m a**n (because
> of the \1 feature). However, there still isn't enough to match
> a palindrome of arbitrary length. (It would be trivial to add such
> a feature -- let \~1 match the reverse of the first match then
> ^(.*).?\~1$
> would match all palindromes... slowly. But no such feature
> exists in any regexp engine I know of.)[/color]

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?

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$

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

regards,

--
alan kennedy
-----------------------------------------------------
check http headers here: http://xhaus.com/headers
email alan: http://xhaus.com/mailto/alan

[Ron Adam]

Re: Palindrome

On Thu, 13 Nov 2003 17:32:06 +0000, Alan Kennedy <alanmk@hotmail .com>
wrote:
[color=blue]
>
>I'm not too happy with it though. There must be some way to have a
>single fixed regular expression that can be used to test every
>palindrome.
>
>regards,[/color]


Thought I'd give it a try too. This is what I came up with. I used
the regular expression re.sub() function to remove the punctuation and
spaces.

The really hard part was trying to come up with a palindrome that has
the word python in it. :-)

_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

palindrome_list = ["Bolton",
"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!",
"Was it a car or a cat I saw?",
"This is not a palindrome!"]

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

[Ron Adam]

Re: Palindrome

On Fri, 14 Nov 2003 11:51:02 GMT, Ron Adam <radam2@tampaba y.rr.com>
wrote:
[color=blue]
>
>"""
>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[/color]


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]

Re: Palindrome

Ron Adam wrote:[color=blue]
> 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)[/color]

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
-----------------------------------------------------
check http headers here: http://xhaus.com/headers
email alan: http://xhaus.com/mailto/alan

[Skip Montanaro]

Re: Palindrome

Andrew> Gerrit Holl[color=blue][color=green]
>> Are you looking for:
>> 20:58:42:232:0 >>> def ispalindrome(s) :
>> 20:58:42:232:0 ... return s == s[::-1][/color][/color]

Andrew> No. The OP wanted to strip special characters and
Andrew> normalize case, so that
Andrew> A man, a plan, a canal -- Panama!
Andrew> would be allowed as a palindrome.

Oh, then how about:

import re
def ispalindrome(s) :
s = re.sub("[^A-Za-z0-9]+", "", s).lower()
return s == s[::-1]

for s in (
"A man, a plan, a canal -- Panama!",
"1234",
"123321",
"Madam, I'm Adam."):
print s, "->", ispalindrome(s)

Skip

[Ron Adam]

Re: Palindrome

On Fri, 14 Nov 2003 14:34:23 +0000, Alan Kennedy <alanmk@hotmail .com>
wrote:
[color=blue]
>
>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,[/color]

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]

Re: Palindrome

Alan Kennedy[color=blue]
> 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?[/color]

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.
[color=blue]
> 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$[/color]

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.
[color=blue]
> One of these days I'll find the time to dig out my old course notes
> and books :#)[/color]

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

Andrew
dalke@dalkescie ntific.com

[Andrew Dalke]

Re: Palindrome

Skip:[color=blue]
> Oh, then how about:[/color]
...

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_dalk e 11.1900866758

Andrew
dalke@dalkescie ntific.com


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[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.app end(c)
foldcase = "".join(foldcas e)
punctuation = "".join(punctua tion)
del c, i

def palindrome_dalk e(s):
t = s.translate(fol dcase, 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_ada m, palindrome_skip ,
palindrome_dalk e):
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_ad am", "palindrome_ski p",
"palindrome_dal ke"):
timer = timeit.Timer(se tup = "import __main__ as M",
stmt = "M." + tester + "(M._time_val)" )
t = timer.timeit()
print tester, t

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