#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2013
    Posts
    15
    Rep Power
    0

    Interlocking Words


    I am doing a problem where I have to find all the words in a list that make a word from alternating letters of two other words. It is from a book/e-bbok called Think Python. This is the full problem:

    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.

    First, is there an easier, more efficient way of doing this? This way takes forever.

    Second, I was looking for answers to this online and found this, which I don't really get. http://stackoverflow.com/questions/5523058/how-to-optimize-this-python-code-from-thinkpython-exercise-10-10.
    One of the answers says something about alternating even and odd letters in a word to make another word. That's not really the problem but other people seem to agree with it. Am I missing something, can anyone shed a little light on this problem?

    Any help is much appreciated...Thanks

    This is what I have

    Code:
    words = open('words.txt')
    words_list = []
    for word in words:
        x = word.strip()
        words_list.append(x)
        
        
    def find_word(joined, words_list):
        if joined in words_list:
            return True
        else:
            return False
        
    def interlock_words(word, werd, words_list, joined_words, z):
        interlocked = []
        i = 0
        j = 0
        listword = list(word)
        listwerd = list(werd)
        print('word is', word)
        print('werd is', werd)
        for letter in range(len(word) * 2):
            if i == 0:
                interlocked.append(word[j])
                i = 1
            else:
                interlocked.append(werd[j])
                i = 0
                j +=1
        q = ''.join(interlocked)
        print('q is', q)
        print()
        check = find_word(q, words_list)
        if z == 0:
            if check == True:
                joined_words.append(q)
                print('word is', word)
                print('werd is', werd)
                print('joind words is', joined_words)
                z = 1
                check = interlock_words(werd, word, words_list, joined_words, z)
            else:
                z = 1
                check = interlock_words(werd, word, words_list, joined_words, z)
        else:
            if check == True:
                joined_words.append(q)
                print('word is', werd)
                print('werd is', word)
                print('joined_words is', joined_words)
            else:
                pass
                
        print('joined is', joined_words)
        
    
    
    def interlock(words_list):
        z = 0
        joined_words = []
        for word in words_list:
            i = words_list.index(word)
            words_copy = words_list[i:]
            for werd in words_copy:
                if werd == word:
                    continue
                elif len(word) == len(werd):
                    check = interlock_words(word, werd, words_copy, joined_words, z)
                else:
                    continue
     
                
    interlock(words_list)
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2013
    Posts
    138
    Rep Power
    2
    1. Could you provide a sample of 'words.txt'?

    2. You have a bug here, you're printing out the wrong variable:

    Code:
                print('word is', werd)
                print('werd is', word)
    3. In the stackoverflow link someone is using a clever string manipulation that you could also use:

    Code:
    >>> alphabet = 'abcdefghijklmnopqrstuvwxyz'
    >>> alphabet[::2]  # Starting at zero, get all values with even index
    'acegikmoqsuwy'
    >>> alphabet[1::2]  # Starting at one, get all values with odd index
    'bdfhjlnprtvxz'
    4. For your own sake, use proper variable names. I suggest you only use 'i' and 'j' for counters, and make all other variable names as descriptive as possible.
  4. #3
  5. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,856
    Rep Power
    481
    Code:
    >>> ''.join(''.join(t) for t in zip('shoe','cold'))
    'schooled'
    >>> ''.join(''.join(t) for t in zip('cold','shoe'))
    'csohlode'
    >>>
    if the words to interlock have differing lengths (The problem is not defined if the lengths differ by more than 1) use itertools.zip_longest and only test with the long word first.

    If I were motivated I'd get some data to test the performance of my code written in full and your code. Instead, I'm going to eat the bulb of roast garlic and see if I recover by Sunday. Really!

    [edit]A weak garlic. I'm fine. If there are only two words to interleave it's simpler like this
    >>> ''.join(a+b for (a,b,) in zip('shoe','cold'))
    'schooled'
    [/edit]
    Last edited by b49P23TIvg; April 9th, 2013 at 10:44 AM.
    [code]Code tags[/code] are essential for python code and Makefiles!
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2013
    Posts
    15
    Rep Power
    0
    Originally Posted by partoj
    1. Could you provide a sample of 'words.txt'?

    2. You have a bug here, you're printing out the wrong variable:

    Code:
                print('word is', werd)
                print('werd is', word)
    3. In the stackoverflow link someone is using a clever string manipulation that you could also use:

    Code:
    >>> alphabet = 'abcdefghijklmnopqrstuvwxyz'
    >>> alphabet[::2]  # Starting at zero, get all values with even index
    'acegikmoqsuwy'
    >>> alphabet[1::2]  # Starting at one, get all values with odd index
    'bdfhjlnprtvxz'
    4. For your own sake, use proper variable names. I suggest you only use 'i' and 'j' for counters, and make all other variable names as descriptive as possible.
    Thanks for your reply...

    That's not really a bug as opposed to just bad wording. In that section of the code I am flip flopping the 2 words am trying to interlock so when I get to that 2nd word in the list I don't have to reiterate all over again. It makes the code faster, but still takes a very long time with a big list.

    As for the second comment in your reply, why do you just check for just the value with the even and odd index? It is a pair of words that we are putting together to form another. That's the part I am not really getting.

    Thanks for the help
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2012
    Posts
    25
    Rep Power
    0
    Well in the case of 'schooled':
    Code:
    >>> 'schooled'[::2]
    'shoe'
    >>> 'schooled'[1::2]
    'cold'
    You can easily check if they interlock based on that info.

    Comments on this post

    • CastorTroy agrees
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2013
    Posts
    138
    Rep Power
    2
    I'm currently trying to write a program with this file as input: http://www-01.sil.org/linguistics/wordlists/english/wordlist/wordsEn.txt

    Every word takes forever to check, so my algorithm must really suck.
    Last edited by partoj; April 10th, 2013 at 04:33 AM.
  12. #7
  13. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,856
    Rep Power
    481
    triennially
    fleetness
    truancies
    ballooned
    calliopes
    weirdness
    plainness
    sheerness
    ...
    Code:
    number of words in group
           length of each word in group
      1 11
      9  9
     28  8
     81  7
    173  6
    341  5
    445  4
     41  3
    Runs in a blink. Use sets. Use hints by others in the thread. Spoiler below.







    x





    |






    V







    Code:
    with open('a') as inf:
        words = set(inf.read().split())
    
    keep = set()
    for word in words:
        if 1 < len(word):
            a = word[::2]
            b = word[1::2]
            if (a in words) and (b in words):
                keep.add(word)
    
    print(keep)

    Comments on this post

    • partoj agrees : Nice! This code will process the wordsEn.txt in 0.142 secs.
    [code]Code tags[/code] are essential for python code and Makefiles!
  14. #8
  15. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2013
    Posts
    15
    Rep Power
    0
    Originally Posted by Lucantrop
    Well in the case of 'schooled':
    Code:
    >>> 'schooled'[::2]
    'shoe'
    >>> 'schooled'[1::2]
    'cold'
    You can easily check if they interlock based on that info.
    Ohhhhhh! Got it. Thanks for the help

IMN logo majestic logo threadwatch logo seochat tools logo