Velocity Reviews > Palindrome

# Palindrome

Ulrich Schramme
Guest
Posts: n/a

 11-13-2003
Georgy Pruss wrote:

> I know what is a palindrome, but I can make up dozen things
> the program could do with the palindrom.
> G-:
>

I´m sorry, but it seems that I misunderstood your previous posting.

--
-- Ulli
www.u-schramme.de

Alan Kennedy
Guest
Posts: n/a

 11-13-2003
[Ulrich Schramme]
> there might be a million ways to solve the palindrome problem. I think
> that another good way would be the use of regular expressions.

The same occurred to me, so I had a go. This is as well as I was able
to do in my lunchtime.

#-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
import re

ignore = """ ",.'`!?-"""

def isPalindrome(s):
testphrase = re.sub("[%s]" % ignore, '', s)
numtomatch = len(testphrase)/2
regx = "(\S)?"
for x in range(numtomatch):
regx = "(\S)%s(\%d)" % (regx, numtomatch-x)
rxc = re.compile(regx, re.I)
result = rxc.match(testphrase)
return result is not None

phrases = [
"Able was I, `ere I saw Elba",
"A man, a plan, a canal, Panama",
"Go Hang a Salami! I'm a Lasagna Hog!",
"Sit on a Potato Pan, Otis",
"Too Hot to Hoot",
"So Many Dynamos",
"Santa, Oscillate My Metallic Sonatas",
"Knob, testes set? Set. Bonk!",
]

if __name__ == "__main__":
print "Palindromes:"
for phrase in phrases:
if isPalindrome(phrase):
print "Yes: '%s'" % phrase
else:
print "No : '%s'" % phrase
#-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

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,

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

Gerrit Holl
Guest
Posts: n/a

 11-13-2003
Runic911 wrote:
> Does anyone know how i can fix my Palindrome program?

A palindrome program?

Are you looking for:
20:58:42:232:0 >>> def ispalindrome(s):
20:58:42:232:0 ... return s == s[::-1]
20:58:42:232:0 ...
20:58:57:232:1 >>> ispalindrome("bolton")
False
20:59:15:232:3 >>> ispalindrome("mooiezepeninepezeioom")
True
20:59:27:232:4 >>> ispalindrome("")
True

?

yours,
Gerrit.

--
276. If he hire a freight-boat, he shall pay two and one-half gerahs
per day.
-- 1780 BC, Hammurabi, Code of Law
--
Asperger Syndroom - een persoonlijke benadering:
http://people.nl.linux.org/~gerrit/
Kom in verzet tegen dit kabinet:
http://www.sp.nl/

Andrew Dalke
Guest
Posts: n/a

 11-13-2003
Alan Kennedy:
> 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.

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.

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

Andrew
http://www.velocityreviews.com/forums/(E-Mail Removed)

Andrew Dalke
Guest
Posts: n/a

 11-13-2003
Gerrit Holl
> Are you looking for:
> 20:58:42:232:0 >>> def ispalindrome(s):
> 20:58:42:232:0 ... return s == s[::-1]

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.

Andrew
(E-Mail Removed)

Ben Finney
Guest
Posts: n/a

 11-13-2003
On Thu, 13 Nov 2003 23:16:50 GMT, Andrew Dalke wrote:
> Gerrit Holl
>> Are you looking for:
>> 20:58:42:232:0 >>> def ispalindrome(s):
>> 20:58:42:232:0 ... return s == s[::-1]

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

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.maketrans( '', '' )
remove_chars = string.whitespace + string.punctuation
str = string.translate( 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",
"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
Guest
Posts: n/a

 11-14-2003
Ben Finney wrote:

> I have yet to try this on the world's longest palindrome:
>
> <http://www.norvig.com/palindrome.html>

> is_pal = ( str == str[::-1] )

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

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

Peter

Skip Montanaro
Guest
Posts: n/a

 11-14-2003
Andrew> Gerrit Holl
>> Are you looking for:
>> 20:58:42:232:0 >>> def ispalindrome(s):
>> 20:58:42:232:0 ... return s == s[::-1]

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.

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",
print s, "->", ispalindrome(s)

Skip

Alan Kennedy
Guest
Posts: n/a

 11-14-2003
[Alan Kennedy]
>> ... There must be some way to have a
>> single fixed regular expression that can be used to test every
>> palindrome.

[Andrew Dalke]
> 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.

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

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/

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

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

Guest
Posts: n/a

 11-14-2003
On Thu, 13 Nov 2003 17:32:06 +0000, Alan Kennedy <(E-Mail Removed)>
wrote:

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

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.

"""
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.'