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. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2013
Posts
138
Rep Power
6
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.
3. 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!

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.
4. 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.

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
5. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Dec 2012
Posts
34
Rep Power
6
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.

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

Join Date
Feb 2013
Posts
138
Rep Power
6
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.
7. 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:

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

print(keep)```

• partoj agrees : Nice! This code will process the wordsEn.txt in 0.142 secs.
8. 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