title: How to optimize this Python code (from ThinkPython, Exercise 10.10)
body: <p>I'm working through Allen Downey's <em>How To Think Like A Computer Scientist</em>, and I've written what I believe to be a functionally correct solution to Exercise 10.10.  But it took just over 10 hours (!) to run, so I'm wondering if I'm missing some really obvious and helpful optimization.</p>
  
  <p>Here's the Exercise:</p>
  
  <p>"Two words 'interlock' if taking alternating letters from each forms a new word.  For example, 'shoe' and 'cold' interlock to form 'schooled'.  Write a program that finds all pairs of words that interlock.  Hint: Don't enumerate all pairs!"</p>
  
  <p>(For these word-list problems, Downey has supplied a file with 113809 words.  We may assume that these words are in a list, one word per item in the list.)</p>
  
  <p>Here's my solution:</p>
  
  <pre><code>from bisect import bisect_left
  
  def index(lst, target):
      """If target is in list, returns the index of target; otherwise returns None"""
      i = bisect_left(lst, target)
      if i != len(lst) and lst[i] == target:
          return i
      else:
          return None
  
  def interlock(str1, str2):
      "Takes two strings of equal length and 'interlocks' them."
      if len(str1) == len(str2):
          lst1 = list(str1)
          lst2 = list(str2)
          result = []
          for i in range(len(lst1)):
              result.append(lst1[i])
              result.append(lst2[i])
          return ''.join(result)
      else:
          return None
  
  def interlockings(word_lst):
      """Checks each pair of equal-length words to see if their interlocking is a word; prints each successful pair and the total number of successful pairs."""
      total = 0
      for i in range(1, 12):  # 12 because max word length is 22
          # to shorten the loops, get a sublist of words of equal length
          sub_lst = filter(lambda(x): len(x) == i, word_lst)
          for word1 in sub_lst[:-1]:
              for word2 in sub_lst[sub_lst.index(word1)+1:]: # pair word1 only with words that come after word1
                  word1word2 = interlock(word1, word2) # interlock word1 with word2
                  word2word1 = interlock(word2, word1) # interlock word2 with word1
                  if index(lst, word1word2): # check to see if word1word2 is actually a word
                      total += 1
                      print "Word 1: %s, Word 2: %s, Interlock: %s" % (word1, word2, word1word2)
                  if index(lst, word2word1): # check to see if word2word1 is actually a word
                      total += 1
                      print "Word 2, %s, Word 1: %s, Interlock: %s" % (word2, word1, word2word1)
      print "Total interlockings: ", total
  </code></pre>
  
  <p>The print statements are not the problem; my program found only 652 such pairs.  The problem is the nested loops, right?  I mean, even though I'm looping over lists that contain only words of the same length, there are (for example) 21727 words of length 7, which means my program has to check over 400 million "interlockings" to see if they're actual words---and that's just for the length-7 words.</p>
  
  <p>So again, this code took 10 hours to run (and found no pairs involving words of length 5 or greater, in case you were curious).  Is there a better way to solve this problem?</p>
  
  <p>Thanks in advance for any and all insight.  I'm aware that "premature optimization is the root of all evil"---and perhaps I've fallen into that trap already---but in general, while I can usually write code that runs correctly, I often struggle with writing code that runs well.</p>