# palindrome iteration

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

1. ### BabaGuest

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

2. ### Peter OttenGuest

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

> 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

3. ### Bruno DesthuilliersGuest

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
4. ### Richard ArtsGuest

> 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
5. ### Matteo LandiGuest

> 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
6. ### Dave AngelGuest

Bruno Desthuilliers wrote:
> <div class="moz-text-flowed" style="font-family: -moz-fixed">Baba a
>> 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
7. ### Bruno DesthuilliersGuest

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
8. ### Bruno DesthuilliersGuest

(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
9. ### D'Arcy J.M. CainGuest

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 ?

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
10. ### D'Arcy J.M. CainGuest

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
11. ### Mark LawrenceGuest

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
12. ### IanGuest

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
13. ### MRABGuest

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
14. ### Mark LawrenceGuest

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
15. ### Terry ReedyGuest

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
16. ### MRABGuest

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
17. ### Jussi PiitulainenGuest

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
18. ### Dave AngelGuest

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
19. ### D'Arcy J.M. CainGuest

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
20. ### Jussi PiitulainenGuest

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