Palindrome

Discussion in 'Python' started by Runic911, Nov 13, 2003.

  1. Runic911

    Runic911 Guest

    Does anyone know how i can fix my Palindrome program?

    s = raw_input('Enter a String: ')
    punctuation = '%$!*.,-:? ;()\'\"\\'
    i = 0
    h = 0
    t = 0
    p = ''
    z = 0
    while s!= ' ':
    while i <= len(s) - 1:
    punct = s
    if punctuation.find(punct) == -1:
    p = p + punct
    i = i + 1
    t = p.lower()
    t[h] == t[len(t)-1-h]
    Runic911, Nov 13, 2003
    #1
    1. Advertising

  2. Runic911

    Ben Finney Guest

    On 13 Nov 2003 03:31:35 GMT, Runic911 wrote:
    > Does anyone know how i can fix my Palindrome program?
    >
    > i = 0
    > h = 0
    > t = 0
    > p = ''
    > z = 0


    You can start by using mnemonic variable names. These ones make the
    algorithm a chore to read. Feel free to re-post it when you've done so.

    --
    \ "I believe in making the world safe for our children, but not |
    `\ our children's children, because I don't think children should |
    _o__) be having sex." -- Jack Handey |
    Ben Finney <http://bignose.squidly.org/>
    Ben Finney, Nov 13, 2003
    #2
    1. Advertising

  3. Runic911

    Georgy Pruss Guest

    Knowing what your program should do, could also help.
    G-:

    "Runic911" <> wrote in message news:...
    | Does anyone know how i can fix my Palindrome program?
    |
    | s = raw_input('Enter a String: ')
    | punctuation = '%$!*.,-:? ;()\'\"\\'
    | i = 0
    | h = 0
    | t = 0
    | p = ''
    | z = 0
    | while s!= ' ':
    | while i <= len(s) - 1:
    | punct = s
    | if punctuation.find(punct) == -1:
    | p = p + punct
    | i = i + 1
    | t = p.lower()
    | t[h] == t[len(t)-1-h]


    --
    Georgy Pruss
    E^mail: 'ZDAwMTEyMHQwMzMwQGhvdG1haWwuY29t\n'.decode('base64')
    Georgy Pruss, Nov 13, 2003
    #3
  4. Georgy Pruss wrote:
    > Knowing what your program should do, could also help.
    > G-:
    >


    As far as I know is a palindrome a word that you can read from both
    sides. Sorry, but English is not my native language. So I don´t have an
    English example handy. But the German name 'OTTO' is a palindrome.


    --
    -- Ulli
    www.u-schramme.de
    Ulrich Schramme, Nov 13, 2003
    #4
  5. Runic911

    Andrew Dalke Guest

    Hi Runic911,

    You probably want this

    t = p.lower()
    t[h] == t[len(t)-1-h]

    to do something. As it is now you don't report anything.
    Looking at it some more I see it has several other problems.
    The code starting at 't=p.lower()' needs to be dedented a
    few levels so it is outside of the 'while s != '':' loop.
    Also, that should be 'if s != '':' and likely doesn't
    even need to be there at all.

    In addition, you could shorten it by quite a bit by using
    some of this higher-level functions available in Python.
    Here's some pointers.

    1) get rid of puncutation in one step rather than several.

    You can use the re module for that, as in

    >>> s = "A man, a plan, a canal -- Panama!"
    >>> import re
    >>> re.sub(r'[%$!*.,:? ;()\'\"\\-]', '', s)

    'AmanaplanacanalPanama'
    >>>


    This is tricky, in part because the '-' must be at the end of pattern.
    You could also use the translate function, as in

    >>> punctuation = '%$!*.,-:? ;()\'\"\\'
    >>> identity = "".join([chr(i) for i in range(256)])
    >>> s.translate(identity, punctuation)

    'AmanaplanacanalPanama'
    >>>


    This is also tricky because you have to use an identity
    translation table. (On the other hand, done correctly this
    could also convert everything to lower case.) I would
    like a function which only removed a selected set of
    characters.

    Or you could make your own function for it

    >>> def remove_punctuation(s):

    .... letters = []
    .... for c in s:
    .... if c not in punctuation:
    .... letters.append(c)
    .... return "".join(letters)
    ....
    >>> remove_punctuation(s)

    'AmanaplanacanalPanama'
    >>>


    You could put this all into your palindrome code but
    it's usually easier to understand your code if each
    step does one thing. By the way, an experienced
    Python programmer might write this function as

    def remove_punctuation(s):
    return "".join([c for c in s if c not in punctuation])

    (since I didn't test this one, odds are good there's
    a typo ;)

    2) convert everything to the same case. If you use
    the regular expression way then use the lower() method,
    which you know about already.

    The translate function can do it like this

    >>> for upper, lower in zip(string.ascii_uppercase, string.ascii_lowercase):

    .... foldcase[ord(upper)] = lower
    ....
    >>> foldcase = "".join(foldcase)
    >>> s

    'A man, a plan, a canal -- Panama!'
    >>> s.translate(foldcase, punctuation)

    'amanaplanacanalpanama'
    >>>


    3) instead of comparing the string to itself, make a
    new string which is a reverse of the old one and compare
    the strings to each other

    In newer Pythons (2.3) you can use [::-1] as a way
    to slice the string backwards. Here's some examples

    >>> s

    'A man, a plan, a canal -- Panama!'
    >>> s[::-1]

    '!amanaP -- lanac a ,nalp a ,nam A'
    >>> t = s.translate(foldcase, punctuation)
    >>> t

    'amanaplanacanalpanama'
    >>> t[::-1]

    'amanaplanacanalpanama'
    >>>


    Since t == t[::-1] you know they are palindromes.

    For older Pythons you'll need to turn the string
    into a list of characters, reverse the list, and turn
    it back into a string, as in

    >>> chars = list(s)
    >>> chars

    ['A', ' ', 'm', 'a', 'n', ',', ' ', 'a', ' ', 'p', 'l', 'a', 'n', ',', ' ',
    'a', ' ', 'c', 'a', 'n',
    'a', 'l', ' ', '-', '-', ' ', 'P', 'a', 'n', 'a', 'm', 'a', '!']
    >>> chars.reverse()
    >>> chars

    ['!', 'a', 'm', 'a', 'n', 'a', 'P', ' ', '-', '-', ' ', 'l', 'a', 'n', 'a',
    'c', ' ', 'a', ' ', ',',
    'n', 'a', 'l', 'p', ' ', 'a', ' ', ',', 'n', 'a', 'm', ' ', 'A']
    >>> "".join(chars)

    '!amanaP -- lanac a ,nalp a ,nam A'
    >>>


    This should be enough information for you to make a
    very nice palindrome function.

    Andrew
    Andrew Dalke, Nov 13, 2003
    #5
  6. Runic911 wrote:
    > Does anyone know how i can fix my Palindrome program?
    >
    > s = raw_input('Enter a String: ')
    > punctuation = '%$!*.,-:? ;()\'\"\\'
    > i = 0
    > h = 0
    > t = 0
    > p = ''
    > z = 0
    > while s!= ' ':
    > while i <= len(s) - 1:
    > punct = s
    > if punctuation.find(punct) == -1:
    > p = p + punct
    > i = i + 1
    > t = p.lower()
    > t[h] == t[len(t)-1-h]



    I´m not very experienced with Python but I think you could do it in a
    more simple way.


    inp = raw_input('Enter a string: ')

    pal = []
    rev = []
    for c in inp:
    if c.isalnum():
    pal.append(c.upper())
    rev.append(c.upper())
    rev.reverse()
    if pal == rev:
    print '"' + inp + '" ' + 'is a palindrome.'
    else:
    print '"' + inp + '" ' + 'is no palindrome.'



    --
    -- Ulli
    www.u-schramme.de
    Ulrich Schramme, Nov 13, 2003
    #6
  7. Runic911

    Andrew Dalke Guest

    Ulrich Schramme:
    > I´m not very experienced with Python but I think you could do it in a
    > more simple way.


    Looks good to me. And it shows that I'm no longer able to help out
    beginning programmers since my solution is along the lines of

    inp = raw_input('Enter a string: ')

    punctuation = '%$!*.,-:? ;()\'\"\\'
    foldcase = [chr(i) for i in range(256)]
    for upper, lower in zip(string.ascii_uppercase, string.ascii_lowercase):
    foldcase[ord(upper)] = lower
    foldcase = "".join(foldcase)

    t = inp.translate(foldcase, punctuation)
    if t != t[::-1]:
    print '"' + inp + '" ' + 'is a palindrome.'
    else:
    print '"' + inp + '" ' + 'is not a palindrome.'

    Faster, but with a startup cost and a high learning curve.
    It's what I would use for my own code.

    A slightly easier to understand and slower version is

    inp = raw_input('Enter a string: ')
    punctuation = '%$!*.,-:? ;()\'\"\\'
    identity = "".join([chr(i) for i in range(256)])

    t = inp.translate(identity, punctuation).lower()
    if t != t[::-1]:
    ...

    Yours is definitely easiest to understand so best for
    the OP.

    Cheers,
    Andrew
    Andrew Dalke, Nov 13, 2003
    #7
  8. Andrew Dalke wrote:
    > Ulrich Schramme:
    >
    >>I´m not very experienced with Python but I think you could do it in a
    >>more simple way.

    >
    >
    > Looks good to me. And it shows that I'm no longer able to help out
    > beginning programmers since my solution is along the lines of
    >
    > inp = raw_input('Enter a string: ')
    >
    > punctuation = '%$!*.,-:? ;()\'\"\\'
    > foldcase = [chr(i) for i in range(256)]
    > for upper, lower in zip(string.ascii_uppercase, string.ascii_lowercase):
    > foldcase[ord(upper)] = lower
    > foldcase = "".join(foldcase)
    >
    > t = inp.translate(foldcase, punctuation)
    > if t != t[::-1]:
    > print '"' + inp + '" ' + 'is a palindrome.'
    > else:
    > print '"' + inp + '" ' + 'is not a palindrome.'
    >
    > Faster, but with a startup cost and a high learning curve.
    > It's what I would use for my own code.
    >
    > A slightly easier to understand and slower version is
    >
    > inp = raw_input('Enter a string: ')
    > punctuation = '%$!*.,-:? ;()\'\"\\'
    > identity = "".join([chr(i) for i in range(256)])
    >
    > t = inp.translate(identity, punctuation).lower()
    > if t != t[::-1]:
    > ...
    >
    > Yours is definitely easiest to understand so best for
    > the OP.
    >
    > Cheers,
    > Andrew
    >
    >
    >



    Thanks Andrew,

    there might be a million ways to solve the palindrome problem. I think
    that another good way would be the use of regular expressions. I´m a
    software developer by profession but quite new to Python. So I tried to
    find an easy way that fits my limited knowledge of the Python syntax.

    My first impression of Python is that it is a well - designed and
    interesting language. I also like this newsgroup. People here seem to be
    more helpful than in some other groups I know...

    Hopefully taking part in discussions here will improve my English as
    well as my Python :)

    --
    -- Ulli
    www.u-schramme.de
    Ulrich Schramme, Nov 13, 2003
    #8
  9. Runic911

    Georgy Pruss Guest

    "Ulrich Schramme" <> wrote in message news:bov86k$9hj$...
    | Georgy Pruss wrote:
    | > Knowing what your program should do, could also help.
    | > G-:
    | >
    |
    | As far as I know is a palindrome a word that you can read from both
    | sides. Sorry, but English is not my native language. So I don´t have an
    | English example handy. But the German name 'OTTO' is a palindrome.

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


    |
    |
    | --
    | -- Ulli
    | www.u-schramme.de
    |
    Georgy Pruss, Nov 13, 2003
    #9
  10. Georgy Pruss wrote:

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


    Sorry, it seems that I misunderstood your previous posting.

    --
    -- Ulli
    www.u-schramme.de
    Ulrich Schramme, Nov 13, 2003
    #10
  11. 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
    Ulrich Schramme, Nov 13, 2003
    #11
  12. Runic911

    Alan Kennedy Guest

    [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",
    "If I Had a Hi-Fi",
    "So Many Dynamos",
    "Madam I'm Alan",
    "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
    -----------------------------------------------------
    check http headers here: http://xhaus.com/headers
    email alan: http://xhaus.com/mailto/alan
    Alan Kennedy, Nov 13, 2003
    #12
  13. Runic911

    Gerrit Holl Guest

    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/
    Gerrit Holl, Nov 13, 2003
    #13
  14. Runic911

    Andrew Dalke Guest

    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
    Andrew Dalke, Nov 13, 2003
    #14
  15. Runic911

    Andrew Dalke Guest

    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
    Andrew Dalke, Nov 13, 2003
    #15
  16. Runic911

    Ben Finney Guest

    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",
    "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/>
    Ben Finney, Nov 13, 2003
    #16
  17. Runic911

    Peter Otten Guest

    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
    Peter Otten, Nov 14, 2003
    #17
  18. 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.

    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
    Skip Montanaro, Nov 14, 2003
    #18
  19. Runic911

    Alan Kennedy Guest

    [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 :-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/

    > 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
    -----------------------------------------------------
    check http headers here: http://xhaus.com/headers
    email alan: http://xhaus.com/mailto/alan
    Alan Kennedy, Nov 14, 2003
    #19
  20. Runic911

    Ron Adam Guest

    On Thu, 13 Nov 2003 17:32:06 +0000, Alan Kennedy <>
    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. :)

    _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, Nov 14, 2003
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Lorin Leone

    Palindrome (HELP)

    Lorin Leone, Nov 12, 2003, in forum: C++
    Replies:
    4
    Views:
    995
    Chris Theis
    Nov 13, 2003
  2. Tim Churches

    Re: Re: Palindrome

    Tim Churches, Nov 13, 2003, in forum: Python
    Replies:
    2
    Views:
    724
    yousafzai
    Jun 5, 2011
  3. Pierre Quentel

    Re: Palindrome

    Pierre Quentel, Nov 13, 2003, in forum: Python
    Replies:
    2
    Views:
    499
    Francis Avila
    Nov 13, 2003
  4. cat_dog_ass

    Palindrome using StringBuffer

    cat_dog_ass, Jan 23, 2007, in forum: Java
    Replies:
    4
    Views:
    2,893
    abhi2varma
    Jan 5, 2013
  5. Tung Chau
    Replies:
    1
    Views:
    460
    SM Ryan
    Aug 6, 2004
Loading...

Share This Page