[Curtis Rutland]

Seta00, on 23 December 2010 - 01:07 PM, said:

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

I'm not quite sure how to take that lol

I really don't know much about python. I bought the O'Reilly Learning Python book but I haven't had much of a chance to read through it. This literally was my first python program, for better or worse.

FWIW, I'm coming from a C# background.

This post has been edited by insertAlias: 23 December 2010 - 01:18 PM

[Seta00]

insertAlias, on 23 December 2010 - 04:16 PM, said:

I'm not quite sure how to take that lol

Look at my solution, it's like C/C++ code translated to Python, yours achieves the same result with less code using slicing

[Dogstopper]

, your original was far more pythonic than my original.

BTW, my time on the last one was:

Your function works!  Average time: 0.000222838282585

My first one was:

Your function works!  Average time: 0.000252705430984

If it didn't use classes, I assume that my time would be much faster.

This post has been edited by atraub: 28 December 2010 - 11:38 AM
Reason for edit:: fixed member tag

[Curtis Rutland]

I see. Well, glad I'm learning right

But a real valid question is, which takes more time? Is it more efficient to use basic control structures or built in methods? Obviously it's more efficient in "programmer time" but in execution time, I wonder?

[baavgai]

I honestly don't understand the palFunction.__call__(eachEntry[0]) thing. I thought it might be a Python 3 ism, but it isn't. This works just fine: palFunction(eachEntry[0]). Python uses those __ for a reason.

Also, I'm not sure that a speed test is entirely valid. If I wanted speed I could do it in C. I could probably make some fugly stuff in Python that would be fast, but not very maintainable. Simple, clean, short, and sweet are what I like to see.

Here's my stab:

Spoiler

def isPalindrome(line):
	def sanitize(ch):
		allowed = 'abcdefghijklmnopqrstuvwxyz'
		if ch in allowed: return ch
		return ' '
	def isTokenPal(a):
		(head, tail) = (0, len(a)-1)
		while head<tail:
			if not a[head]==a[tail]: return False
			(head, tail) = (head+1, tail-1)
		return True
	s = ''.join([sanitize(c) for c in line.lower()])
	return (isTokenPal([ c for c in s if not c==' ' ]), isTokenPal(s.split()))

Now, if you really want to run your fitness test to choose a winner, here's a slight modification to that code:

Spoiler

class cached():
	def __init__(self, func):
		self.func = func
		self.cache = dict()
		
	def __call__(self, arg):
		if arg not in self.cache:
			self.cache[arg] = self.func(arg)
		return self.cache[arg]

@cached
def isPalindrome(line):
	def sanitize(ch):
		allowed = 'abcdefghijklmnopqrstuvwxyz'
		if ch in allowed: return ch
		return ' '
	def isTokenPal(a):
		(head, tail) = (0, len(a)-1)
		while head<tail:
			if not a[head]==a[tail]: return False
			(head, tail) = (head+1, tail-1)
		return True
	s = ''.join([sanitize(c) for c in line.lower()])
	# print(s)
	return (isTokenPal([ c for c in s if not c==' ' ]), isTokenPal(s.split()))

The above runs an order of magnatude faster in the test, though the modfication is rather absurd.

I believe you'll get better test result if you just time the whole mess. Timing many very little increments is far more variable due to how computers time things and ticks.

e.g.

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

[atraub]

I like your changes. I still don't like using that form of string formatting (% operator) because it's deprecated in Python. But, I think I'll use yours to replace mine.

[atraub]

BIG NEWS:

I'm allowing earlier versions of Python, I'll just convert them to 3 myself on an as needed basis. So, 2.x guys, join the fray!

[baavgai]

atraub, on 23 December 2010 - 11:20 PM, said:

don't like using that form of string formatting (% operator) because it's deprecated in Python.

OMG, no! Wut? This is what I get for not really caring about Python 3, along with most of the planet.

Seems the accepted method would be str.format. Looks very .NET, actually. I can do that:

	if results:
		print("This entry failed to correctly identify:\n\"{0}\" as: {1}".format(results[0],results[1]))
		print("Function returns: {0}".format(results[2]))
	else:
		start = time.time()
		for i in range(sampleSize):
			testPalindrome()
		elapsed = time.time() - start
		print("Elapsed time: {0}\nAverage time: {1}\n".format(elapsed, elapsed/sampleSize))

[soldner]

Pretty nice, Dogstopper!

I needed to use reg expressions at work (I'm a SAP ABAP programmer) so ended up using re for my function, and here it is:
-Well, I don't see how to load the code so it looks like the others. Would someone tell me?

import re
def isPalindrome(txt):
    '''Returns tuple showing phrase meets two palindrome requirements.

        1. Character palindrome where the characters(alphas only) reversed are same,
        2. Word palindrome where the words, reversed, are the same.
        Return Tuple shows True/False for each type (character, word)
    '''  
    # Character matching
    txt1 = re.sub('\W+', '', txt).lower()
    if txt1 == txt1[::-1]:
        char = True
    else:
        char = False

    # Word matching
    txt2 = re.sub('\W+', ':', txt).lower() 
    txt3 = txt2.split(':')
    for item in txt3[:]:
        if item == '': txt3.remove(item)

    if txt3 == txt3[::-1]:
        word = True
    else:
        word = False       

    return (char, word)

This post has been edited by atraub: 28 December 2010 - 08:45 AM
Reason for edit:: Added code tags

[atraub]

Just for giggles, I made a recursive palindrome function. Yes, it is should be VERY SLOW so it's not a serious contender. I just liked how clean the recursive style looked.

#Checks for character-wise and word-wise palindromes

def stringPrep(inputStr):
    charWise = ""
    wordWise = ""
    for letters in inputStr.lower():
        if letters.isalnum() or letters == " ":
                wordWise += letters
                if letters != " ":
                    charWise += letters
    return charWise, wordWise.split(" ")
    

def isPalindrome(inputStr):
    def isPalindromeX(inputStr):
        if len(inputStr) <=1:
            return True        
        elif inputStr[0] == inputStr[-1]:
            return isPalindromeX(inputStr[1:-1])
        else:
            return False
        
    charWise,wordWise = stringPrep(inputStr)
    
    return (isPalindromeX(charWise),isPalindromeX(wordWise))

This post has been edited by atraub: 28 December 2010 - 04:49 PM
Reason for edit:: Cleaning

[atraub]

Here are the preliminary results using the test functions that baavgai wrote:
(Seta00, yours isn't working. This may be a python 2 to 3 issue, but filter() returns an object not a string)

Atraubrecursion
Elapsed time: 1.03600001335
Average time: 0.000103600001335

Stevensmith
Elapsed time: 1.65299987793
Average time: 0.000165299987793

Baavgai
Elapsed time: 1.07399988174
Average time: 0.000107399988174

Insertalias
Elapsed time: 1.117000103
Average time: 0.0001117000103

Dogstopper
Elapsed time: 1.19000005722
Average time: 0.000119000005722

Baavgaicached
Elapsed time: 0.0500001907349
Average time: 5.00001907349e-06

While I can't explain it, the recursive function is actually winning in terms of average time, but I'm sure that would change if we used some longer strings. You all still have time to revise your functions! Good Luck!!

UPDATE:
Added Baavgai's cached approach. It's amazing how fast the elapsed time is versus how slow the average is.

This post has been edited by atraub: 28 December 2010 - 11:44 AM

[soldner]

Really Cool! I wasn't going for speed as much as accuracy, but seeing how fast and looking at the code is a tremedous help!

I'm looking forward to the next one. Thanks Adam!

[atraub]

If you want to revise it, we still have almost 2 weeks until the deadline; but there definitely is no shame in losing to or baavgai.

Also, as far as speed testing. Things like clever or clean code are somewhat subjective. Speed is the only sure-fire, non-subjective way I know of for testing code.

This post has been edited by atraub: 28 December 2010 - 04:50 PM

[atraub]

I upgraded the testing a little. Here's some more detailed results... very interesting stuff:


Small Strings
insertAlias
Elapsed time: 0.533268928528
Average time: 5.33268928528e-05

Dogstopper Dogstopper
Elapsed time: 0.53926897049
Average time: 5.3926897049e-05

baavgai baavgai
Elapsed time: 0.509850025177
Average time: 5.09850025177e-05

baavgai baavgaiCached
Elapsed time: 0.0319018363953
Average time: 3.19018363953e-06

atraub AtraubRecursion
Elapsed time: 0.491166114807
Average time: 4.91166114807e-05

StevenSmith StevenSmith
Elapsed time: 0.77411699295
Average time: 7.7411699295e-05






Lots of Bad Characters
atraub AtraubRecursion
Elapsed time: 0.437238931656
Average time: 4.37238931656e-05

baavgai baavgai
Elapsed time: 0.617779970169
Average time: 6.17779970169e-05

Dogstopper Dogstopper
Elapsed time: 0.460546016693
Average time: 4.60546016693e-05

StevenSmith StevenSmith
Elapsed time: 0.974539041519
Average time: 9.74539041519e-05

baavgai baavgaiCached
Elapsed time: 0.0210049152374
Average time: 2.10049152374e-06

insertAlias
Elapsed time: 0.503103017807
Average time: 5.03103017807e-05






Big Strings
baavgai baavgai
Elapsed time: 2.16325092316
Average time: 0.000216325092316

StevenSmith StevenSmith
Elapsed time: 2.56431889534
Average time: 0.000256431889534

Dogstopper Dogstopper
Elapsed time: 1.88621520996
Average time: 0.000188621520996

atraub AtraubRecursion
Elapsed time: 2.69212698936
Average time: 0.000269212698936

baavgai baavgaiCached
Elapsed time: 0.0213510990143
Average time: 2.13510990143e-06

insertAlias
Elapsed time: 1.90147399902
Average time: 0.000190147399902






Random Strings
atraub AtraubRecursion
Elapsed time: 3.48411202431
Average time: 0.000348411202431

StevenSmith StevenSmith
Elapsed time: 5.86155796051
Average time: 0.000586155796051

baavgai baavgai
This entry failed to correctly identify:
"VWoV^q^ZdJCuseNjtQanxz" as: (False, True)
Function returns: (False, False)

baavgai baavgaiCached
This entry failed to correctly identify:
"VWoV^q^ZdJCuseNjtQanxz" as: (False, True)
Function returns: (False, False)

Dogstopper Dogstopper
Elapsed time: 4.41251921654
Average time: 0.000441251921654

insertAlias
Elapsed time: 4.1979072094
Average time: 0.00041979072094




Unique Strings
StevenSmith StevenSmith
Elapsed time: 0.161891937256
Average time: 9.21096593399e-06

baavgai baavgaiCached
Elapsed time: 0.0967390537262
Average time: 5.50404265625e-06

Dogstopper Dogstopper
Elapsed time: 0.117145061493
Average time: 6.66505811862e-06

baavgai baavgai
Elapsed time: 0.0819129943848
Average time: 4.6605026391e-06

atraub AtraubRecursion
Elapsed time: 0.063915014267
Average time: 3.63649375665e-06

insertAlias
Elapsed time: 0.138894081116
Average time: 7.90248527058e-06



UPDATE: I edited the print statement to use the member Tag

This post has been edited by atraub: 29 December 2010 - 07:14 AM
Reason for edit:: includes more tests

[Dogstopper]

baavgai, every time I look at your code, I learn something new. I love the decorators taking on the role of a cache. Great idea and very efficient!