palindrome iteration

Discussion in 'Python' started by Baba, Aug 27, 2010.

  1. Baba

    Baba Guest

    level: beginner

    the following code looks ok to me but it doesn't work. I would like
    some hints as to where my reasoning / thought goes wrong

    def i_palindrome(pal):
    while len(pal)>1:
    if pal[0] == pal[-1]:
    pal=pal[1:-1]
    return True

    print i_palindrome('annab')


    my reasoning:
    - i check the length of the string: if > 1 continue
    - i check first and last char: if they are equal continue
    - create a new, shorter string starting at index 1 and ending at
    second last index (up to but not including index-1
    -restart the while loop as long as length of string is > 1
    - exiting this loop means all compared chars were identical hence it
    is a palindrome and i return True

    tnx
    Baba
     
    Baba, Aug 27, 2010
    #1
    1. Advertising

  2. Baba

    Peter Otten Guest

    Baba wrote:

    > level: beginner
    >
    > the following code looks ok to me but it doesn't work. I would like
    > some hints as to where my reasoning / thought goes wrong
    >
    > def i_palindrome(pal):
    > while len(pal)>1:
    > if pal[0] == pal[-1]:
    > pal=pal[1:-1]
    > return True


    Do yourself a favour and use 4-space indent. That makes the structure of
    your code more obvious.

    > print i_palindrome('annab')
    >
    >
    > my reasoning:
    > - i check the length of the string: if > 1 continue
    > - i check first and last char: if they are equal continue
    > - create a new, shorter string starting at index 1 and ending at
    > second last index (up to but not including index-1
    > -restart the while loop as long as length of string is > 1
    > - exiting this loop means all compared chars were identical hence it
    > is a palindrome and i return True


    If the test pal[0] == pal[-1] fails, i. e. the two compared characters
    differ, what happens?

    More generally, if pal is not a palindrome, can your function ever return
    False? If not, at what point should it?

    Peter
     
    Peter Otten, Aug 27, 2010
    #2
    1. Advertising

  3. Baba a écrit :
    > level: beginner
    >
    > the following code looks ok to me but it doesn't work.


    "doesn't work" is about the most useless description of a problem.
    Please specify what you expected and what actually happens.

    > I would like
    > some hints as to where my reasoning / thought goes wrong
    >
    > def i_palindrome(pal):
    > while len(pal)>1:
    > if pal[0] == pal[-1]:
    > pal=pal[1:-1]


    Can you explain what happens if pal[0] != pal[-1] ? (answer below)

    > return True


    > print i_palindrome('annab')


    And then you go in an infinite loop !-)

    >
    > my reasoning:
    > - i check the length of the string: if > 1 continue
    > - i check first and last char: if they are equal continue
    > - create a new, shorter string starting at index 1 and ending at
    > second last index (up to but not including index-1
    > -restart the while loop as long as length of string is > 1
    > - exiting this loop means all compared chars were identical hence it
    > is a palindrome and i return True


    Your problem is that when first and last char are not equal, you don't
    exit the while loop. You need a "return False" somewhere here, ie:

    def is_palindrom(pal):
    while len(pal)>1:
    # NB : inverted the test here to make exit more obvious
    if pal[0] != pal[-1]:
    return False
    pal=pal[1:-1]
    return True


    Now there is another solution. A palindrom is made of two symetric
    halves, with (odd len) or without (even len) a single char between the
    symetric halves, ie :

    * odd : ABCBA ('AB' + 'C' + 'BA')
    * even : ABCCBA ('ABC' + 'CBA')

    So you just have to extract the symetric halves, reverse one, and
    compare both (case insensitive compare while we're at it). Here's a
    possible (and a bit tricky) Python 2.x implementation:

    def is_palindrom(s):
    s = s.lower()
    slen = len(s)
    until = slen / 2 # Python 2x integer division
    offset = int(not(slen % 2))
    runtil = until - offset
    return s[0:until] == s[-1:runtil:-1]
     
    Bruno Desthuilliers, Aug 27, 2010
    #3
  4. Baba

    Richard Arts Guest

    > Now there is another solution. A palindrom is made of two symetric halves,
    > with (odd len) or without (even len) a single char between the symetric
    > halves, ie :
    >
    > * odd : ABCBA ('AB' + 'C' + 'BA')
    > * even : ABCCBA ('ABC' + 'CBA')
    >
    > So you just have to extract the symetric halves, reverse one, and compare
    > both (case insensitive compare while we're at it).


    Yes, this is a correct observation, but it is not necessary to compare
    the halves; Simply compare the complete string with its reverse. If
    they match, it is a palindrome.

    > Here's a possible (and a
    > bit tricky) Python 2.x implementation:
    >
    > def is_palindrom(s):
    >    s = s.lower()
    >    slen = len(s)
    >    until = slen / 2 # Python 2x integer division
    >    offset = int(not(slen % 2))
    >    runtil = until - offset
    >    return s[0:until] == s[-1:runtil:-1]
    >
    >


    At first glance this seems to be correct, but it is tricky indeed.
    Particularly the assignment of the offset variable, casting a bool to
    an integer of a negated expression. Given that Baba notes that this is
    a beginners level query, it wouldn't have hurt to be a little bit more
    verbose there.

    Richard
     
    Richard Arts, Aug 27, 2010
    #4
  5. Baba

    Matteo Landi Guest

    > Yes, this is a correct observation, but it is not necessary to compare
    > the halves; Simply compare the complete string with its reverse. If
    > they match, it is a palindrome.


    I've always used to implement the is_palindrome function as you
    suggest, i.e. comparing the original string with the reverse one, but
    while reading, I tought about a imho nicer version which prevent from
    creating another string.

    Here are both the recursive/iterative versions of the function:

    def palindrome(str, i=0, j=-1):
    try:
    if str == str[j]:
    return palindrome(str, i + 1, j - 1)
    return False
    except IndexError:
    return True

    def palindrome(str, i=0, j=-1):
    try:
    while True:
    if str != str[j]:
    return False
    i, j = i + 1, j - 1
    return True
    except IndexError:
    return True

    Regards,
    Matteo

    >
    >> Here's a possible (and a
    >> bit tricky) Python 2.x implementation:
    >>
    >> def is_palindrom(s):
    >>    s = s.lower()
    >>    slen = len(s)
    >>    until = slen / 2 # Python 2x integer division
    >>    offset = int(not(slen % 2))
    >>    runtil = until - offset
    >>    return s[0:until] == s[-1:runtil:-1]
    >>
    >>

    >
    > At first glance this seems to be correct, but it is tricky indeed.
    > Particularly the assignment of the offset variable, casting a bool to
    > an integer of a negated expression. Given that Baba notes that this is
    > a beginners level query, it wouldn't have hurt to be a little bit more
    > verbose there.
    >
    > Richard
    > --
    > http://mail.python.org/mailman/listinfo/python-list
    >




    --
    Matteo Landi
    http://www.matteolandi.net/
     
    Matteo Landi, Aug 27, 2010
    #5
  6. Baba

    Dave Angel Guest

    Bruno Desthuilliers wrote:
    > <div class="moz-text-flowed" style="font-family: -moz-fixed">Baba a
    > écrit :
    >> level: beginner
    >>
    >> the following code looks ok to me but it doesn't work.

    >
    > "doesn't work" is about the most useless description of a problem.
    > Please specify what you expected and what actually happens.
    >
    >> I would like
    >> some hints as to where my reasoning / thought goes wrong
    >>
    >> def i_palindrome(pal):
    >> while len(pal)>1:
    >> if pal[0] == pal[-1]:
    >> pal=pal[1:-1]

    >
    > Can you explain what happens if pal[0] != pal[-1] ? (answer below)
    >
    >> return True

    >
    >> print i_palindrome('annab')

    >
    > And then you go in an infinite loop !-)
    >
    >>
    >> my reasoning:
    >> - i check the length of the string: if > 1 continue
    >> - i check first and last char: if they are equal continue
    >> - create a new, shorter string starting at index 1 and ending at
    >> second last index (up to but not including index-1
    >> -restart the while loop as long as length of string is > 1
    >> - exiting this loop means all compared chars were identical hence it
    >> is a palindrome and i return True

    >
    > Your problem is that when first and last char are not equal, you don't
    > exit the while loop. You need a "return False" somewhere here, ie:
    >
    > def is_palindrom(pal):
    > while len(pal)>1:
    > # NB : inverted the test here to make exit more obvious
    > if pal[0] != pal[-1]:
    > return False
    > pal=pal[1:-1]
    > return True
    >
    >
    > Now there is another solution. A palindrom is made of two symetric
    > halves, with (odd len) or without (even len) a single char between the
    > symetric halves, ie :
    >
    > * odd : ABCBA ('AB' + 'C' + 'BA')
    > * even : ABCCBA ('ABC' + 'CBA')
    >
    > So you just have to extract the symetric halves, reverse one, and
    > compare both (case insensitive compare while we're at it). Here's a
    > possible (and a bit tricky) Python 2.x implementation:
    >
    > def is_palindrom(s):
    > s = s.lower()
    > slen = len(s)
    > until = slen / 2 # Python 2x integer division
    > offset = int(not(slen % 2))
    > runtil = until - offset
    > return s[0:until] == s[-1:runtil:-1]
    >
    >

    or (untested)
    def is_palindrom(s):
    s = s.lower()
    return s == s[::-1]

    DaveA
     
    Dave Angel, Aug 27, 2010
    #6
  7. Richard Arts a écrit :
    >> Now there is another solution. A palindrom is made of two symetric halves,
    >> with (odd len) or without (even len) a single char between the symetric
    >> halves, ie :
    >>
    >> * odd : ABCBA ('AB' + 'C' + 'BA')
    >> * even : ABCCBA ('ABC' + 'CBA')
    >>
    >> So you just have to extract the symetric halves, reverse one, and compare
    >> both (case insensitive compare while we're at it).

    >
    > Yes, this is a correct observation, but it is not necessary to compare
    > the halves; Simply compare the complete string with its reverse. If
    > they match, it is a palindrome.


    Duh :(

    I kinda feel stupid right now, thanks Richard :-/
     
    Bruno Desthuilliers, Aug 27, 2010
    #7
  8. Dave Angel a écrit :
    (snip)

    > or (untested)
    > def is_palindrom(s):
    > s = s.lower()
    > return s == s[::-1]
    >



    Right, go on, make me feel a bit more stupid :-/
    Who's next ?
     
    Bruno Desthuilliers, Aug 27, 2010
    #8
  9. On Fri, 27 Aug 2010 16:43:16 +0200
    Bruno Desthuilliers <> wrote:
    > Dave Angel a écrit :
    > > def is_palindrom(s):
    > > s = s.lower()
    > > return s == s[::-1]

    >
    >
    > Right, go on, make me feel a bit more stupid :-/
    > Who's next ?


    How about a one-liner?

    is_palindrome = lambda x: len(x)> 0 and x == x.lower()[::-1]

    Note that the above assumes that single characters are palindromes but
    empty strings are not. I'm not 100% sure that that last is true. If
    not then this can be simplified.

    is_palindrome = lambda x: x == x.lower()[::-1]

    --
    D'Arcy J.M. Cain <> | Democracy is three wolves
    http://www.druid.net/darcy/ | and a sheep voting on
    +1 416 425 1212 (DoD#0082) (eNTP) | what's for dinner.
     
    D'Arcy J.M. Cain, Aug 27, 2010
    #9
  10. On Fri, 27 Aug 2010 11:49:42 -0400
    "D'Arcy J.M. Cain" <> wrote:
    > is_palindrome = lambda x: x == x.lower()[::-1]


    Oops. Simple and wrong.

    is_palindrome = lambda x: x.lower() == x.lower()[::-1]

    --
    D'Arcy J.M. Cain <> | Democracy is three wolves
    http://www.druid.net/darcy/ | and a sheep voting on
    +1 416 425 1212 (DoD#0082) (eNTP) | what's for dinner.
     
    D'Arcy J.M. Cain, Aug 27, 2010
    #10
  11. On 27/08/2010 15:43, Bruno Desthuilliers wrote:
    > Dave Angel a écrit :
    > (snip)
    >
    >> or (untested)
    >> def is_palindrom(s):
    >> s = s.lower()
    >> return s == s[::-1]
    >>

    >
    >
    > Right, go on, make me feel a bit more stupid :-/
    > Who's next ?


    It could be worse, try responding to issue 9702. :)

    Cheers.

    Mark Lawrence.
     
    Mark Lawrence, Aug 27, 2010
    #11
  12. Baba

    Ian Guest

    On 27/08/2010 09:53, Baba wrote:
    > level: beginner
    >
    > the following code looks ok to me but it doesn't work. I would like
    > some hints as to where my reasoning / thought goes wrong
    >
    > def i_palindrome(pal):
    > while len(pal)>1:
    > if pal[0] == pal[-1]:
    > pal=pal[1:-1]
    > return True
    >
    > print i_palindrome('annab')
    >

    If you want to or must do it recursively.
    (Shown in pseudo code to make the logic clearer)

    def isPalindrome(pal)
    ''' test pal (a list) is a palindrome '''
    if length of pal = 1
    return True # all one letter strings are palindromes.
    if first equals last
    # pal could be a palindrome
    # so test inner part
    p = pal with first and last removed
    return isPalendrome(p) # and true - implied
    else
    return False # it can't be

    Of course, the simpler way is to use the definition of a Palindrome as
    the same backwards and forwards.

    def isPalindrome(pal)
    return pal == pal.reverse
     
    Ian, Aug 27, 2010
    #12
  13. Baba

    MRAB Guest

    On 27/08/2010 17:20, Mark Lawrence wrote:
    > On 27/08/2010 15:43, Bruno Desthuilliers wrote:
    >> Dave Angel a écrit :
    >> (snip)
    >>
    >>> or (untested)
    >>> def is_palindrom(s):
    >>> s = s.lower()
    >>> return s == s[::-1]
    >>>

    >>
    >>
    >> Right, go on, make me feel a bit more stupid :-/
    >> Who's next ?

    >
    > It could be worse, try responding to issue 9702. :)
    >

    As a wise man once said: Ay caramba! :)
     
    MRAB, Aug 27, 2010
    #13
  14. On 27/08/2010 17:53, MRAB wrote:
    > On 27/08/2010 17:20, Mark Lawrence wrote:
    >> On 27/08/2010 15:43, Bruno Desthuilliers wrote:
    >>> Dave Angel a écrit :
    >>> (snip)
    >>>
    >>>> or (untested)
    >>>> def is_palindrom(s):
    >>>> s = s.lower()
    >>>> return s == s[::-1]
    >>>>
    >>>
    >>>
    >>> Right, go on, make me feel a bit more stupid :-/
    >>> Who's next ?

    >>
    >> It could be worse, try responding to issue 9702. :)
    >>

    > As a wise man once said: Ay caramba! :)


    Isn't that a syntax error? Shouldn't it be ¡Ay caramba! :)

    Cheers.

    Mark Lawrence.
     
    Mark Lawrence, Aug 27, 2010
    #14
  15. Baba

    Terry Reedy Guest

    On 8/27/2010 4:53 AM, Baba wrote:
    > level: beginner
    >
    > the following code looks ok to me but it doesn't work. I would like
    > some hints as to where my reasoning / thought goes wrong
    >
    > def i_palindrome(pal):
    > while len(pal)>1:
    > if pal[0] == pal[-1]:
    > pal=pal[1:-1]
    > return True
    >
    > print i_palindrome('annab')


    General practical debugging procedurewhen logic inspection fails: insert
    print statements at key points.

    In the case above, put "print pal" before the if statement and you
    should see the problem. And/or "print 'equal'" after the if.

    --
    Terry Jan Reedy
     
    Terry Reedy, Aug 27, 2010
    #15
  16. Baba

    MRAB Guest

    On 27/08/2010 18:28, Mark Lawrence wrote:
    > On 27/08/2010 17:53, MRAB wrote:
    >> On 27/08/2010 17:20, Mark Lawrence wrote:
    >>> On 27/08/2010 15:43, Bruno Desthuilliers wrote:
    >>>> Dave Angel a écrit :
    >>>> (snip)
    >>>>
    >>>>> or (untested)
    >>>>> def is_palindrom(s):
    >>>>> s = s.lower()
    >>>>> return s == s[::-1]
    >>>>>
    >>>>
    >>>>
    >>>> Right, go on, make me feel a bit more stupid :-/
    >>>> Who's next ?
    >>>
    >>> It could be worse, try responding to issue 9702. :)
    >>>

    >> As a wise man once said: Ay caramba! :)

    >
    > Isn't that a syntax error? Shouldn't it be ¡Ay caramba! :)
    >

    I stand (OK, sit) corrected.
     
    MRAB, Aug 27, 2010
    #16
  17. Ian writes:

    > If you want to or must do it recursively.
    > (Shown in pseudo code to make the logic clearer)
    >
    > def isPalindrome(pal)
    > ''' test pal (a list) is a palindrome '''
    > if length of pal = 1
    > return True # all one letter strings are palindromes.
    > if first equals last
    > # pal could be a palindrome
    > # so test inner part
    > p = pal with first and last removed
    > return isPalendrome(p) # and true - implied
    > else
    > return False # it can't be


    def palindromep(s):
    return ( s == "" or
    ( s[0] == s[-1] and
    palindromep(s[1:-1]) ) )

    > Of course, the simpler way is to use the definition of a Palindrome
    > as the same backwards and forwards.
    >
    > def isPalindrome(pal)
    > return pal == pal.reverse


    Agreed. But is there any nicer way to spell .reverse than [::-1] in
    Python? There is .swapcase() but no .reverse(), right?
     
    Jussi Piitulainen, Aug 27, 2010
    #17
  18. Baba

    Dave Angel Guest

    Jussi Piitulainen wrote:
    > Ian writes:
    >
    >
    >> If you want to or must do it recursively.
    >> (Shown in pseudo code to make the logic clearer)
    >>
    >> def isPalindrome(pal)
    >> ''' test pal (a list) is a palindrome '''
    >> if length of pal = 1
    >> return True # all one letter strings are palindromes.
    >> if first equals last
    >> # pal could be a palindrome
    >> # so test inner part
    >> p = pal with first and last removed
    >> return isPalendrome(p) # and true - implied
    >> else
    >> return False # it can't be
    >>

    >
    > def palindromep(s):
    > return ( s == "" or
    > ( s[0] == s[-1] and
    > palindromep(s[1:-1]) ) )
    >
    >
    >> Of course, the simpler way is to use the definition of a Palindrome
    >> as the same backwards and forwards.
    >>
    >> def isPalindrome(pal)
    >> return pal == pal.reverse
    >>

    >
    > Agreed. But is there any nicer way to spell .reverse than [::-1] in
    > Python? There is .swapcase() but no .reverse(), right?
    >
    >

    There can't be a .reverse() method on string, because it's immutable.
    You could use

    "".join(reversed(pal))

    but I'd prefer pal[::-1] as I said earlier.

    DaveA
     
    Dave Angel, Aug 27, 2010
    #18
  19. On Fri, 27 Aug 2010 12:02:39 -0400
    "D'Arcy J.M. Cain" <> wrote:
    > On Fri, 27 Aug 2010 11:49:42 -0400
    > "D'Arcy J.M. Cain" <> wrote:
    > > is_palindrome = lambda x: x == x.lower()[::-1]

    >
    > Oops. Simple and wrong.
    >
    > is_palindrome = lambda x: x.lower() == x.lower()[::-1]


    slightly more efficient I think.

    is_palindrome = lambda y: (lambda x: x == x[::-1])(y.lower())

    --
    D'Arcy J.M. Cain <> | Democracy is three wolves
    http://www.druid.net/darcy/ | and a sheep voting on
    +1 416 425 1212 (DoD#0082) (eNTP) | what's for dinner.
     
    D'Arcy J.M. Cain, Aug 27, 2010
    #19
  20. Dave Angel writes:

    > Jussi Piitulainen wrote:
    >> Ian writes:
    >>> Of course, the simpler way is to use the definition of a
    >>> Palindrome as the same backwards and forwards.
    >>>
    >>> def isPalindrome(pal)
    >>> return pal == pal.reverse

    >>
    >> Agreed. But is there any nicer way to spell .reverse than [::-1] in
    >> Python? There is .swapcase() but no .reverse(), right?
    >>

    > There can't be a .reverse() method on string, because it's
    > immutable. You could use
    >
    > "".join(reversed(pal))
    >
    > but I'd prefer pal[::-1] as I said earlier.


    There could easily be a .reverse() method on strings. It would return
    the reversed string, like .swapcase() returns the swapcased string.
     
    Jussi Piitulainen, Aug 27, 2010
    #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:
    1,042
    Chris Theis
    Nov 13, 2003
  2. Runic911

    Palindrome

    Runic911, Nov 13, 2003, in forum: Python
    Replies:
    24
    Views:
    1,625
    Andrew Dalke
    Nov 15, 2003
  3. Tim Churches

    Re: Re: Palindrome

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

    Re: Palindrome

    Pierre Quentel, Nov 13, 2003, in forum: Python
    Replies:
    2
    Views:
    528
    Francis Avila
    Nov 13, 2003
  5. Rudi
    Replies:
    5
    Views:
    5,240
Loading...

Share This Page