palindrome iteration

B

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
 
P

Peter Otten

Baba said:
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
 
B

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]
 
R

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
 
M

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
 
D

Dave Angel

Bruno said:
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
 
B

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

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

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]
 
M

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

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
 
M

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

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

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

Jussi Piitulainen

Ian said:
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?
 
D

Dave Angel

Jussi said:
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

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

Jussi Piitulainen

Dave said:
Jussi said:
Ian said:
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.
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,901
Latest member
Noble71S45

Latest Threads

Top