[atraub]

I must admit, Dogstopper's Java Function Challenge inspired me. It's time for the Python Function challenge, Project Palindrome!

Is everyone here familiar with palindromes? If not, check em out on wikipedia. One of my favorite palindromes is, "Madam, I'm Adam." Madam I'm Adam, when looking at only the characters, is a palindrome. It is the same set of chars forward and backwards when we ignore punctuation and formatting (madamimadam).

So here's my challenge. Write a program than can correctly recognize wordwise and characterwise palindromes and be able to correctly report what we're looking at. I will not reveal which specific palindromes I'll be using for the test until all entries have been submitted. Your program should return a tuple with 2 values. The first value will be whether it's a characterwise palindrome, and the second will be if it's a wordwise palindrome. For example:

isPalindrome("i HAS A kitty!") should return (False, False)

isPalindrome("Madam, I'm Adam") should return (True,False)

isPalindrome("Fall leaves after leaves fall") should return (False, True)

isPalindrome("Level, madam, level!") should return (True, True)


The deadline is January 10th. To keep the test fair, all submissions must be Python3 compliant... which shouldn't be a problem. They can be in any version of Python, I'll translate them to 3 as needed. Please be sure to name your function isPalindrome for ease of testing.

I'll update soon to show you the specific function I'll use for testing! Good luck!

Please post your code in your post.


Update:
I'm sure you'll want an easy way to test your functions. Here's a sample function you can use to test your palindrome function. To keep things fair, this will NOT be the one I use for the final test. It's just something you can use to test yours.

import time
import palindrome #your palindrome.py file.

def main(palFunction, sampleSize=10000):
	def testPalindrome():
		sampleData = [["Madam, I'm Adam.", (True,False)],
			["level madam, level!", (True, True)],                  
			["i HAS A kitty :)/>", (False,False)],
			["Fall leaves after leaves fall",(False,True)]]
		for eachEntry in sampleData:
			results = palFunction(eachEntry[0])
			if not results==eachEntry[1]:
				return (eachEntry[0],eachEntry[1],results)
		return None
		
	results = testPalindrome()
	if results:
		print("This entry failed to correctly identify:\n\"%s\" as: %s" % (results[0],results[1]))
		print("Function returns: %s" % (results[2],))
	else:
		start = time.time()
		for i in range(sampleSize):
			testPalindrome()
		elapsed = time.time() - start
		print("Elapsed time: %f\nAverage time: %f\n" % (elapsed, elapsed/sampleSize))

        
if __name__=="__main__":
    main(palindrome.isPalindrome)

EDIT 2:
Don't worry about linewise palindromes, like:

Quote

As I was passing near the jail
I met a man, but hurried by.
His face was ghastly, grimly pale.
He had a gun. I wondered why.
He had, A gun? I wondered... why,
His face was ghastly! grimly pale,
I met a man but hurried by,
As I was passing near the jail.

This post has been edited by atraub: 23 December 2010 - 10:26 PM
Reason for edit:: code cleanup

[Sergio Tapia]

You made it py3 just to spite us didn't you?

[atraub]

Well, there are speed differences between 2 and 3. I do want to promote 3, so it seems like the fair way to test it while simultaneously pushing my own agenda I only worry that time.time() might not be a small enough unit of measure for this test.

This post has been edited by atraub: 23 December 2010 - 09:40 AM

[Steven Smith]

Can you specify what sort of entry validation and filtering might be required? Your example shows commas, apostrophes, exclamations, smilies that must be filtered. Could there be misformatting like double spacing?

I would typically add all this by default, but if the goal is 100% speed related...

[atraub]

For palindromic purposes (HAH!), only concern yourself with alphanumeric values.

"I am       (^___^) +_+       MAI!!!!!!!"

would be considered a characterwise palindrome despite all the extra junk. 0-9 a-z are all that matter.

This post has been edited by atraub: 23 December 2010 - 10:33 AM

[Seta00]

I would do it, but I'm too lazy to download Python 3 and learn the differences

[Sergio Tapia]

Ditto.

[soldner]

Well I'm learning with 2.7 and I think 3.1's code also can be run in 2.7, so I'm giving it a whirl.

[Dogstopper]

atraub, on 23 December 2010 - 10:26 AM, said:

Well, there are speed differences between 2 and 3. I do want to promote 3, so it seems like the fair way to test it while simultaneously pushing my own agenda I only worry that time.time() might not be a small enough unit of measure for this test.

I can't use Python 3 yet! It'll break my Wireless Internet in my OS. I can hack it to make it work, but it's not worth the effort. I'll be doing it in 2.7 and converting later.

[KYA]

How is that even possible?

[Curtis Rutland]

Alright, here's my try:

Spoiler

def cleanString(instring):
    instring = instring.lower()
    spaces = ''.join(ch for ch in instring if ch.isalnum() or ch == ' ')
    nospaces = ''.join(ch for ch in spaces if ch != ' ')
    return (spaces, nospaces)

def isCharwise(instring):
    return instring == instring[::-1]

def isWordwise(instring):
    words = instring.split(' ')
    return words == words[::-1]

def isPalindrome(instring):
    (spaces, nospaces) = cleanString(instring)    
    return (isCharwise(nospaces), isWordwise(spaces))

Be gentle, it's my first non-"hello world" python program. I had to google for how to clean the string, but other than that, the rest I figured out from my python book.

EDIT: Figured I'd post my average time from your program: 7.5e-05. I got that +/- 1e-05 about 10 tries.

Also, I think I'm going to use this challenge in the C# forum, if you don't mind.

This post has been edited by insertAlias: 23 December 2010 - 12:50 PM

[Steven Smith]

My first go at it before I start refactoring and finding better functions to keep from typecasting like mad... think this works though.

Spoiler

def isPalindrome(testString):
    charList = list(filter(str.isalpha, list(testString.lower())))
    isChar = charList == list(reversed(charList))

    wordList = list(filter(lambda x: x.isalpha() or x.isspace(), list(testString.lower())))
    wordList = ''.join(wordList).split()
    isWord = wordList == list(reversed(wordList))

    return (isChar, isWord)

Edit: @Dogstopper, sorry, the OP did not request it so I didn't see it necessary.
Time on my laptop: Your function works! Average time: 0.000102999997139
Edited by Dogstopper: Can you please post in [spoiler] tags?

This post has been edited by Steven Smith: 23 December 2010 - 01:00 PM

[Dogstopper]

KYA, on 23 December 2010 - 01:39 PM, said:

How is that even possible?

The python package got conveniently renamed to python from its original pyhton3. I don't wanna mess with it.

BUT, I found an Eclipse plugin that does the execution internally. Here's my code (now with classes):

Spoiler

'''
Created on Dec 23, 2010

@author: Stephen Schwahn
'''

class Palindrome(object):
    '''
    This class defines a palindrome and several methods 
    to establish what kind of palindrome it is.
    '''


    def __init__(self, pal):
        '''
        Constructor
        '''
        self.origPal = pal
    
    def removePuncCap(self):
        # Lowercase it first
        self.origPal = self.origPal.lower();
        
        # Set an array of acceptable characters.
        string = ""
        for letter in self.origPal:
            if letter.isalpha() or letter == ' ':
                string += letter
        
        self.origPal = string
    
    def removeSpaces(self):
        string = ""
        for letter in self.origPal:
            if letter.isalpha():
                string += letter
        
        self.origPal = string
    
    def isWordPal(self):
        '''
        Make sure to call this before isLetterPal or else
        all the spaces will be gone.
        '''
        words = self.origPal.split(" "); 
        left = 0
        right = len(words) - 1
        
        if not len(words) > 1:
            return False
        
        while (left < right):
            if words[left] != words[right]:
                return False
            left +=1
            right -= 1
        return True
        
    def isLetterPal(self):
        self.removeSpaces()
        left = 0
        right = len(self.origPal) - 1
        
        while (left < right):
            if self.origPal[left] != self.origPal[right]:
                return False
            left+=1
            right-=1
        return True 

def isPalindrome(pal):
    p = Palindrome(pal)
    p.removePuncCap();
    isWord = p.isWordPal()
    isLetter = p.isLetterPal()
    return (isLetter, isWord)

[Seta00]

Haha, by looking at the other solutions insertAlias' solution I can see how much influenced I am by C/C++:

Spoiler

def isalnum_or_space(item):
    return str.isalnum(item) or item == ' '

def isPalindrome(the_string):
    result = [False, False]

    the_string = the_string.lower()

    # characterwise palindrome
    string = filter(str.isalnum, the_string)

    sz = len(string)
    count = 0

    for i in range(sz):
        if string[i] == string[sz-i-1]:
            count += 1

    if count == sz:
        result[0] = True

    # word wise palindrome
    string2 = filter(isalnum_or_space, the_string)
    words = string2.split(' ')

    sz = len(words)
    count = 0

    for i in range(0, sz):
        if words[i].strip() == words[sz-i-1].strip():
            count += 1

    if count >= sz-1:
        result[1] = True

    return (result[0],result[1])

Guess I need to get more pythonic

This post has been edited by Seta00: 23 December 2010 - 01:10 PM

[Dogstopper]

Here is a far more pythonic version of my last program. It uses list comprehensions to remove the non-letters and it uses string/list slicing (to reverse them):

Spoiler

'''
Created on Dec 23, 2010

@author: Stephen Schwahn
'''

class Palindrome(object):
    '''
    This class defines a palindrome and several methods 
    to establish what kind of palindrome it is.
    '''

    def __init__(self, pal):

        self.origPal = pal
    
    def removePuncCap(self):
        self.origPal = ''.join([letter for letter in self.origPal.lower() if letter == ' ' or letter.isalpha()])

    
    def removeSpaces(self):
        self.origPal = ''.join([letter for letter in self.origPal.lower() if letter.isalpha()])
    
    def isWordPal(self):
        '''
        Make sure to call this before isLetterPal or else
        all the spaces will be gone.
        '''
        words = self.origPal.split()
        return words == words[::-1]
        
    def isLetterPal(self):
        self.removeSpaces()
        return self.origPal == self.origPal[::-1]

def isPalindrome(pal):
    p = Palindrome(pal)
    p.removePuncCap();
    isWord = p.isWordPal()
    isLetter = p.isLetterPal()
    return (isLetter, isWord)

This post has been edited by Dogstopper: 23 December 2010 - 01:15 PM