palindrome iteration

[Baba]

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

 

[Peter Otten]

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

 

[Bruno Desthuilliers]

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]

 

[Richard Arts]

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

 

[Matteo Landi]

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

 

[Dave Angel]

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

 

[Bruno Desthuilliers]

Richard Arts a écrit :

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]

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 ?

 

[D'Arcy J.M. Cain]

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]

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

Oops. Simple and wrong.

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

 

[Mark Lawrence]

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.

 

[Ian]

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

 

[MRAB]

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!

 

[Mark Lawrence]

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.

 

[Terry Reedy]

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.

 

[MRAB]

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.

 

[Jussi Piitulainen]

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?

 

[Dave Angel]

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

 

[D'Arcy J.M. Cain]

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

 

[Jussi Piitulainen]

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.