Velocity Reviews > palindrome iteration

# palindrome iteration

Baba
Guest
Posts: n/a

 08-27-2010
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
Guest
Posts: n/a

 08-27-2010
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

Bruno Desthuilliers
Guest
Posts: n/a

 08-27-2010
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
Guest
Posts: n/a

 08-27-2010
> 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
Guest
Posts: n/a

 08-27-2010
> 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[i] == 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[i] != 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/

Dave Angel
Guest
Posts: n/a

 08-27-2010

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

Bruno Desthuilliers
Guest
Posts: n/a

 08-27-2010
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
Guest
Posts: n/a

 08-27-2010
(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
Guest
Posts: n/a

 08-27-2010
On Fri, 27 Aug 2010 16:43:16 +0200
Bruno Desthuilliers <(E-Mail Removed)> 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 <(E-Mail Removed)> | 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
Guest
Posts: n/a

 08-27-2010
On Fri, 27 Aug 2010 11:49:42 -0400
"D'Arcy J.M. Cain" <(E-Mail Removed)> 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 <(E-Mail Removed)> | 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.