Humbled ...

Discussion in 'Mac Programming' started by mysterytramp, Jun 24, 2009.

  1. macrumors 65816

    mysterytramp

    Joined:
    Jul 17, 2008
    Location:
    Maryland
    #1
    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:

    Code:
    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:

    Code:
    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
     
  2. macrumors 68030

    Catfish_Man

    Joined:
    Sep 13, 2001
    Location:
    Portland, OR
    #2
    How about this?

    Code:
    def isAnagram(word1,word2):
        return sorted(word1) == sorted(word2)
    
     
  3. thread starter macrumors 65816

    mysterytramp

    Joined:
    Jul 17, 2008
    Location:
    Maryland
    #3
    Lesson learned ... twice.

    mt
     
  4. macrumors 68030

    Catfish_Man

    Joined:
    Sep 13, 2001
    Location:
    Portland, OR
    #4
    Clever solution though :) I hadn't thought of sorting the strings to compare for anagrams until I read your post.
     
  5. macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #5
    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
     

Share This Page