Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
April 8th, 2013, 11:56 PM
 CastorTroy
Registered User

Join Date: Feb 2013
Posts: 15
Time spent in forums: 3 h 7 m 9 sec
Reputation 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
April 9th, 2013, 01:55 AM
 partoj
Contributing User

Join Date: Feb 2013
Posts: 138
Time spent in forums: 1 Day 12 h 26 m 47 sec
Reputation Power: 1
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
April 9th, 2013, 10:27 AM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,218
Time spent in forums: 1 Month 3 Weeks 2 Days 18 h 51 m 46 sec
Reputation Power: 455
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]
__________________
[code]Code tags[/code] are essential for python code!

Last edited by b49P23TIvg : April 9th, 2013 at 11:44 AM.

#4
April 9th, 2013, 10:43 AM
 CastorTroy
Registered User

Join Date: Feb 2013
Posts: 15
Time spent in forums: 3 h 7 m 9 sec
Reputation Power: 0
Quote:
 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
April 9th, 2013, 12:16 PM
 Lucantrop
Registered User

Join Date: Dec 2012
Posts: 25
Time spent in forums: 23 h 8 m 29 sec
Reputation 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.
CastorTroy agrees!

#6
April 10th, 2013, 05:30 AM
 partoj
Contributing User

Join Date: Feb 2013
Posts: 138
Time spent in forums: 1 Day 12 h 26 m 47 sec
Reputation Power: 1
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 05:33 AM.

#7
April 10th, 2013, 12:26 PM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,218
Time spent in forums: 1 Month 3 Weeks 2 Days 18 h 51 m 46 sec
Reputation Power: 455
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
April 10th, 2013, 10:34 PM
 CastorTroy
Registered User

Join Date: Feb 2013
Posts: 15
Time spent in forums: 3 h 7 m 9 sec
Reputation Power: 0
Quote:
 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

 Viewing: Dev Shed Forums > Programming Languages > Python Programming > Interlocking Words