CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 12 of 12
  1. #1
    Join Date
    Apr 2019
    Posts
    2

    Palindromes in Python

    How can I Implement palindromes in Python?

  2. #2
    Join Date
    Apr 2019
    Posts
    2

    Re: Palindromes in Python

    A palindrome is a phrase, a word, or a sequence that reads the same forward and backward. One such example will be pip! An example of such a phrase will be ‘nurses run’. Let’s implement it, shall we?

    >>>
    Code:
    def isPalindrome(string):
          left,right=0,len(string)-1
          while right>=left:
                  if not string[left]==string[right]:
                           return False
                  left+=1;right-=1
                  return True
    >>> isPalindrome('redrum murder')
    True

    >>> isPalindrome('CC.')
    False

    Well, there are other ways to do this too. Let’s try using an iterator.

    >>>
    Code:
    def isPalindrome(string):
          left,right=iter(string),iter(string[::-1])
          i=0
          while i<len(string)/2:
                 if next(left)!=next(right):
                          return False
                 i+=1
                 return True
    >>> isPalindrome('redrum murder')
    True

    >>> isPalindrome('CC.')
    False

    >>> isPalindrome('CCC.')
    False

    >>> isPalindrome('CCC')
    True
    Last edited by 2kaud; May 8th, 2019 at 05:42 AM. Reason: Added code tags

  3. #3
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

    Re: Palindromes in Python

    It really doesn't have to be that complex:
    Code:
    def isPalindrome(text):
        return text == ''.join(reversed(text))
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  4. #4
    Join Date
    Feb 2017
    Posts
    677

    Re: Palindromes in Python

    Quote Originally Posted by laserlight View Post
    It really doesn't have to be that complex:
    Your solution may have a lower complexity in some elegance sense but the algorithmic complexity is higher than necessary because the string is always reversed (as far as I can tell without knowing any Python). This results in an O(N) complexity whereas aakashdata's solution will be O(1) amortized because it stops when the first unequality is found.

    Say the characters of a string appear at random with probability 1/28. Then the probability that the first and last characters are equal is (1/28)^2 which is roughly 1/1000. It would mean that in 999 cases out of 1000 aakashdata's solution will stop already when the first pair of characters are compared.

    Introducing an initial equality test of only the first and last character at the beginning of your solution would reduce its elegance somewhat but it would also reduce the complexity from O(N) to O(1) amortized. A small blemish on a perfect skin may make you even more attractive.
    Last edited by wolle; May 19th, 2019 at 02:57 AM.

  5. #5
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

    Re: Palindromes in Python

    Quote Originally Posted by wolle
    Your solution may have a lower complexity in some elegance sense but the algorithmic complexity is higher than necessary because the string is always reversed (as far as I can tell without knowing any Python). This results in an O(N) complexity whereas aakashdata's solution will be O(1) amortized because it stops when the first unequality is found.
    Sure, but by and large for the kind of strings that people want to check if they are palindromes, this doesn't matter: they are so short that O(N) complexity is meaningless versus amortised O(1) complexity, and you would have O(N) complexity anyway from doing preprocessing work to get them into a form suitable to test with simple comparisons for equality (e.g., removing punctuation and changing all alphabetic characters to the same case).
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  6. #6
    Join Date
    Feb 2017
    Posts
    677

    Re: Palindromes in Python

    Quote Originally Posted by laserlight View Post
    Sure, but by and large for the kind of strings that people want to check if they are palindromes, this doesn't matter:
    My point is that seemingly simple code can have hidden complexities to be aware of. Your suggestion in #3 is an example of that. It may be that it doesn't matter in this case (who's ever written a palindrome checker other than as an exercise anyway?) but in the general case it does matter I think. But maybe Python programmers aren't supposed to be concerned with efficiency. It's not even mentioned in the core guidelines,

    https://www.python.org/dev/peps/pep-0020/

    Note that if the "cleansing" of the string takes place in conjunction with the core palindrome checking the algorithm can still be made O(1) amortized.
    Last edited by wolle; May 19th, 2019 at 05:36 AM.

  7. #7
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

    Re: Palindromes in Python

    Quote Originally Posted by wolle
    My point is that seemingly simple code can have hidden complexities to be aware of. Your suggestion in #3 is an example of that. It may be that it doesn't matter in this case (...) but in the general case it does matter I think.
    Yes, I agree. My point is that it's also possible to over-engineer to handle things that don't matter, and in general we should be aware of that too.

    Quote Originally Posted by wolle
    But maybe Python programmers aren't supposed to be concerned with efficiency. It's not even mentioned in the core guidelines
    I initially took this as a snide remark, which seems rather rude coming from a fellow member who has been here for awhile and should know that I don't just program in Python, but okay, in retrospect it is better to err on the side of assuming that people mean well and so you are genuinely curious.

    So, my answer to this is that I find it to be a mix. At the language level, yes, it does look like that "Zen of Python" doesn't mention efficiency, but we could possibly infer it from "Although practicality beats purity.", and aphorisms aside, in reality it is true that some of the backwards incompatible redesigns of Python going from 2 to 3 have to do with efficiency. Yet, at programmer level, it's clear from increasing popularity that there are people with no computer science background who can't care in the first place about efficiency using Python, and then it's also true that programmers pretty much don't choose Python because they need something time critical, for reasons including the global interpreter lock on the most common Python implementation. On the other hand, some of the Python idioms developed by programmers arguably have to do with efficiency (e.g., preferences for certain structures over others).
    Last edited by laserlight; May 19th, 2019 at 06:44 AM.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  8. #8
    Join Date
    Feb 2017
    Posts
    677

    Re: Palindromes in Python

    Quote Originally Posted by laserlight View Post
    Oh please, what a snide remark. Surely you know that I don't just program in Python.
    It wasn't meant like that. I know you program in C++ but since you replied here I presume you have Python experience too which I don't have.

    In C++ there's a heavy focus on efficiency (a little too much in my view). I wonder if Python is different, if there's a more relaxed attitude. At least that Zen document indicates that. I asked you because you're in a position to have an opinion, nothing else.

  9. #9
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

    Re: Palindromes in Python

    Quote Originally Posted by wolle
    It wasn't meant like that. I know you program in C++ but since you replied here I presume you have Python experience too which I don't have.
    Yes, I read your statement again and decided it was unfair to attribute rudeness to you when it can be explained otherwise. My apologies as it means that it is I who became rude.

    For what's it's worth, if you would like an example of how isPalindrome could be written in more "Pythonic" fashion than aakashdata's examples while maintaining the same time complexity and even number of comparisons, I would suggest:
    Code:
    import itertools
    
    def isPalindrome(text):
        for forward, backward in zip(itertools.islice(text, len(text) / 2),
                                     reversed(text)):
            if forward != backward:
                return False
        return True
    It's the same idea of using iterators as aakashdata's second example, except that it directly halves the forward iterator range by creating an iterator with a middle end point and makes the iterating in reverse for the backward iterator more explicit. Some Python programmers -- and I admit that I have counted myself one of them at times -- are allergic to "unnecessary" for loops and might rewrite this with a generator expression:
    Code:
    def isPalindrome(text):
        return next((False for forward, backward
                     in zip(itertools.islice(text, len(text) / 2), reversed(text))
                     if forward != backward),
                    True)
    But maybe you'll take another look at your favourite "Zen and Python" and ask whether this flat structure really is flat or does it actually violate "Sparse is better than dense".
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  10. #10
    Join Date
    Feb 2017
    Posts
    677

    Re: Palindromes in Python

    Quote Originally Posted by laserlight View Post
    For what's it's worth, if you would like an example of how isPalindrome could be written in more "Pythonic" fashion than aakashdata's examples while maintaining the same time complexity and even number of comparisons, I would suggest:
    Your "pythonic" versions are quite similar to what a C++ version in the functional style could look like, for example

    Code:
    inline bool is_palindrome(const std::string& s) {
        return std::equal(s.begin(), s.begin() + s.size()/2, s.rbegin());
    }
    Complexity is O(1) amortized.

    I know Python is increasingly popular even rivaling C++. My problem is that I cannot find anything in particular with Python that makes it so special in comparison with other modern multiparadigm languages. Is it maybe that programmers feel special when they get to follow the Zen of Python programming rules to write "pythonic" code? To me it seems like "beautiful Python code" simply translates to "follows the functional programming paradigm". Nothing wrong with that but what's so special about writing functional code in a functional language? I can't get rid of the feeling that there's at least some amount of hype in effect here.

    Again, I'm not blaming you for anything. I'm just asking because I know you are familiar with both C++ and Python.
    Last edited by wolle; May 20th, 2019 at 04:37 AM.

  11. #11
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

    Re: Palindromes in Python

    Quote Originally Posted by wolle
    Your "pythonic" versions are quite similar to what a C++ version in the functional style could look like, for example
    Yes, but C++ has a richer library of generic algorithms, and in this case the next function is more akin to the overly generic std::for_each than to a more descriptive generic algorithm. If you look at my second Python example, you still need to look closely into the generator to find out almost the entirety of what the function is doing, whereas with your C++ example, the very name std::equal sets the tone for what's going to happen. It might be possible to mitigate this by naming the generator though, e.g.,
    Code:
    def is_palindrome(text):
        mismatches = (
            False for forward, backward
            in zip(itertools.islice(text, len(text) / 2), reversed(text))
            if forward != backward
        )
        return next(mismatches, True)
    Quote Originally Posted by wolle
    I know Python is increasingly popular even rivaling C++.
    I wouldn't put much stock into general popularity contests; in the end different languages will have their niches which may rise and fall from time to time, so it's more important to look at popularity within niches, and surely you'll find that in some niches, C++ is still dominant, whereas in others, C++ is pretty much never used compared to Python.

    Quote Originally Posted by wolle
    My problem is that I cannot find anything in particular with Python that makes it so special in comparison with other modern multiparadigm languages.
    It's probably mainly traction from the data science crowd as an alternative to R thanks to:
    • numpy and pandas libraries
    • Not too complicated syntax when these folks that might not have a computer science/software engineering background are just starting out
    • Python being a mainstream general purpose programming language to begin with, so data science teams can get help from their software engineering teams when they need advanced help in Python; this may then have a "virtuous cycle" effect of companies trying to do "big data" hiring more Python programmers even if Python isn't necessarily any better than other programming languages for the other programming tasks they need done


    Quote Originally Posted by wolle
    Is it maybe that programmers feel special when they get to follow the Zen of Python programming rules to write "pythonic" code?
    I think you grossly overestimate how much even Python programmers from a CS background think about that PEP when they write Python code.

    Quote Originally Posted by wolle
    To me it seems like "beautiful Python code" simply translates to "follows the functional programming paradigm".
    Not true: like any other multiparadigm programming language, Python has idioms that go beyond any particular programming paradigm.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  12. #12
    Join Date
    Feb 2017
    Posts
    677

    Re: Palindromes in Python

    Quote Originally Posted by laserlight View Post
    I wouldn't put much stock into general popularity contests;
    At least the TIOBE index is based on objective data and not just what people think,

    https://www.tiobe.com/tiobe-index/

    Here Python has been in a positive trend for quite some time.

    It's probably mainly traction from the data science crowd as an alternative to R thanks to:
    Yes it seems Python has quite a large body of high quality packages provided by the community.

    https://pypi.org/

    This never happened with Java for example. Everybody just waited for Sun and now Oracle to extend the standard library to include ever more packages.

    I think you grossly overestimate how much even Python programmers from a CS background think about that PEP when they write Python code.
    Maybe it works at a subconscious level. The Zen of Python rules apply to any language really but it was Python that brought them. People want to do the right thing and these 19 "commandments" provide that.

    -----

    Thanks for you reply. I'll keep an eye on Python for new projects.
    Last edited by wolle; May 23rd, 2019 at 04:19 AM.

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured