Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > palindrome iteration

Reply
Thread Tools

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
 
Reply With Quote
 
 
 
 
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
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
 
Reply With Quote
 
 
 
 
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]


 
Reply With Quote
 
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
 
Reply With Quote
 
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/
 
Reply With Quote
 
Dave Angel
Guest
Posts: n/a
 
      08-27-2010


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
 
Reply With Quote
 
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 :-/


 
Reply With Quote
 
Bruno Desthuilliers
Guest
Posts: n/a
 
      08-27-2010
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 ?
 
Reply With Quote
 
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 ?


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 <(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.
 
Reply With Quote
 
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.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: Re: Palindrome Tim Churches Python 2 06-05-2011 03:24 AM
Struts - Problem with nested iteration or double iteration Rudi Java 5 10-01-2008 03:30 AM
Palindrome Runic911 Python 24 11-15-2003 12:08 AM
Re: Palindrome Pierre Quentel Python 2 11-13-2003 06:11 PM
Palindrome (HELP) Lorin Leone C++ 4 11-13-2003 08:11 AM



Advertisments