PDA

View Full Version : Humbled ...




mysterytramp
Jun 24, 2009, 06:17 PM
An exercise in the Python version of “How to Think Like a Computer Scientist” at first struck me as dumb, then in a flash I had the answer. Come up with a function that would determine if one word was an anagram of the other.

Immediately, I saw what would be an easy mistake: going letter by letter through the first word looking to see if the letter appeared in the second word. It would be easy to write a routine that would see P E E L E D as an anagram of P E D D L E, since they’re both made up of P, E, L and D.

My solution would turn each word into lists, search for a letter in wordList1 into wordList2, and when it was found, replace the letter with a nonalphabetic character, “*”. If the loops reach the end, the words are anagrams.

Here:

def isAnagram(word1,word2):
wordList1, wordList2 = list(word1), list(word2)
if len(wordList1) <> len(wordList2):
return False
where = -1
for ch1 in wordList1:
for counter in range (0, len(wordList2)):
if ch1 == wordList2[counter]:
where = counter
break
if where == -1:
return False
else:
wordList2[counter] = '*'
where = -1
print str(wordList2) # this print statement isn't needed
# but I think it's cool to watch the iterations
return True


firstWord, secondWord = raw_input('Please enter first word: '), raw_input('Please enter second word: ')

print isAnagram(firstWord,secondWord)

I was sufficiently proud of myself and decided to call it a night. As I’m brushing my teeth, I realize just how stupid I was. If the two lists were sorted, they would be equal if the words were anagrams.

Like this:

def isAnagram(word1,word2):
x,y = list(word1), list(word2)
x.sort(), y.sort()
# print str(x), str(y)
return (x == y)

firstWord, secondWord = raw_input('Please enter first word: '), raw_input('Please enter second word: ')

print isAnagram(firstWord,secondWord)

Sure enough, No. 2 works like a charm. I clung to the hope that checking the equality of two lists is so inefficient that somehow my original routine was faster. Not a chance. I mocked up some brute force timing (essentially wrapping each “isAnagram” statement with a 100,000 iteration for loop) and the second version takes half the time of the first.

So there’s an important lesson here: Never be too impressed with your coding because there’s almost always a faster way to get something done.

mt



Catfish_Man
Jun 24, 2009, 06:50 PM
How about this?


def isAnagram(word1,word2):
return sorted(word1) == sorted(word2)

mysterytramp
Jun 24, 2009, 08:32 PM
How about this?


def isAnagram(word1,word2):
return sorted(word1) == sorted(word2)


Lesson learned ... twice.

mt

Catfish_Man
Jun 24, 2009, 10:22 PM
Clever solution though :) I hadn't thought of sorting the strings to compare for anagrams until I read your post.

lee1210
Jun 24, 2009, 11:52 PM
A corollary to this is that the solution to a lot of programming problems (which are often issues of algorithms or problem solve, not the actual implementation) don't come from staring at the code. Almost every difficult problem i've solved myself or with others have been solved away from the keyboard.

You stated that your alternate solution came to you in the shower. That's a popular candidate, but I find that almost anything where your mind can be clear helps things snap into focus. I've been trying to exercise more lately, and the routine is physically demanding (for me), but mentally I'm on autopilot. A lot of things come to me then, because my mind literally has nothing else to do.

Sometimes you just have to bang out a solution, but for the hard stuff time away is the best way to work towards a solution.

-Lee