# Unit 6: Fun with Words
"""
A portmanteau word is a blend of two or more words, like 'mathelete',
which comes from 'math' and 'athelete'. You will write a function to
find the 'best' portmanteau word from a list of dictionary words.
Because 'portmanteau' is so easy to misspell, we will call our
function 'natalie' instead:
natalie(['word', ...]) == 'portmanteauword'
In this exercise the rules are: a portmanteau must be composed of
three non-empty pieces, start+mid+end, where both start+mid and
mid+end are among the list of words passed in. For example,
'adolescented' comes from 'adolescent' and 'scented', with
start+mid+end='adole'+'scent'+'ed'. A portmanteau must be composed
of two different words (not the same word twice).
That defines an allowable combination, but which is best? Intuitively,
a longer word is better, and a word is well-balanced if the mid is
about half the total length while start and end are about 1/4 each.
To make that specific, the score for a word w is the number of letters
in w minus the difference between the actual and ideal lengths of
start, mid, and end. (For the example word w='adole'+'scent'+'ed', the
start,mid,end lengths are 5,5,2 and the total length is 12. The ideal
start,mid,end lengths are 12/4,12/2,12/4 = 3,6,3. So the final score
is
12 - abs(5-3) - abs(5-6) - abs(2-3) = 8.
yielding a score of 12 - abs(5-(12/4)) - abs(5-(12/2)) -
abs(2-(12/4)) = 8.
The output of natalie(words) should be the best portmanteau, or None
if there is none.
Note (1): I got the idea for this question from
Darius Bacon. Note (2): In real life, many portmanteaux omit letters,
for example 'smoke' + 'fog' = 'smog'; we aren't considering those.
Note (3): The word 'portmanteau' is itself a portmanteau; it comes
from the French "porter" (to carry) + "manteau" (cloak), and in
English meant "suitcase" in 1871 when Lewis Carroll used it in
'Through the Looking Glass' to mean two words packed into one. Note
(4): the rules for 'best' are certainly subjective, and certainly
should depend on more things than just letter length. In addition to
programming the solution described here, you are welcome to explore
your own definition of best, and use your own word lists to come up
with interesting new results. Post your best ones in the discussion
forum. Note (5) The test examples will involve no more than a dozen or so
input words. But you could implement a method that is efficient with a
larger list of words.
"""
def natalie(words):
"Find the best Portmanteau word formed from any two of the list of words."
def test_natalie():
"Some test cases for natalie"
assert natalie(['adolescent', 'scented', 'centennial', 'always', 'ado']) == 'adolescented'
assert natalie(['eskimo', 'escort', 'kimchee', 'kimono', 'cheese']) == 'eskimono'
assert natalie(['kimono', 'kimchee', 'cheese', 'serious', 'us', 'usage']) == 'kimcheese'
assert natalie(['circus', 'elephant', 'lion', 'opera', 'phantom']) == 'elephantom'
assert natalie(['programmer', 'coder', 'partying', 'merrymaking']) == 'programmerrymaking'
assert natalie(['int', 'intimate', 'hinter', 'hint', 'winter']) == 'hintimate'
assert natalie(['morass', 'moral', 'assassination']) == 'morassassination'
assert natalie(['entrepreneur', 'academic', 'doctor', 'neuropsychologist', 'neurotoxin', 'scientist', 'gist']) == 'entrepreneuropsychologist'
assert natalie(['perspicacity', 'cityslicker', 'capability', 'capable']) == 'perspicacityslicker'
assert natalie(['backfire', 'fireproof', 'backflow', 'flowchart', 'background', 'groundhog']) == 'backgroundhog'
assert natalie(['streaker', 'nudist', 'hippie', 'protestor', 'disturbance', 'cops']) == 'nudisturbance'
assert natalie(['night', 'day']) == None
assert natalie(['dog', 'dogs']) == None
assert natalie(['test']) == None
assert natalie(['']) == None
assert natalie(['ABC', '123']) == None
assert natalie([]) == None
return 'tests pass'
print test_natalie()
My solution:
# Unit 6: Fun with Words
"""
A portmanteau word is a blend of two or more words, like 'mathelete',
which comes from 'math' and 'athelete'. You will write a function to
find the 'best' portmanteau word from a list of dictionary words.
Because 'portmanteau' is so easy to misspell, we will call our
function 'natalie' instead:
natalie(['word', ...]) == 'portmanteauword'
In this exercise the rules are: a portmanteau must be composed of
three non-empty pieces, start+mid+end, where both start+mid and
mid+end are among the list of words passed in. For example,
'adolescented' comes from 'adolescent' and 'scented', with
start+mid+end='adole'+'scent'+'ed'. A portmanteau must be composed
of two different words (not the same word twice).
That defines an allowable combination, but which is best? Intuitively,
a longer word is better, and a word is well-balanced if the mid is
about half the total length while start and end are about 1/4 each.
To make that specific, the score for a word w is the number of letters
in w minus the difference between the actual and ideal lengths of
start, mid, and end. (For the example word w='adole'+'scent'+'ed', the
start,mid,end lengths are 5,5,2 and the total length is 12. The ideal
start,mid,end lengths are 12/4,12/2,12/4 = 3,6,3. So the final score
is
12 - abs(5-3) - abs(5-6) - abs(2-3) = 8.
yielding a score of 12 - abs(5-(12/4)) - abs(5-(12/2)) -
abs(2-(12/4)) = 8.
The output of natalie(words) should be the best portmanteau, or None
if there is none.
Note (1): I got the idea for this question from
Darius Bacon. Note (2): In real life, many portmanteaux omit letters,
for example 'smoke' + 'fog' = 'smog'; we aren't considering those.
Note (3): The word 'portmanteau' is itself a portmanteau; it comes
from the French "porter" (to carry) + "manteau" (cloak), and in
English meant "suitcase" in 1871 when Lewis Carroll used it in
'Through the Looking Glass' to mean two words packed into one. Note
(4): the rules for 'best' are certainly subjective, and certainly
should depend on more things than just letter length. In addition to
programming the solution described here, you are welcome to explore
your own definition of best, and use your own word lists to come up
with interesting new results. Post your best ones in the discussion
forum. Note (5) The test examples will involve no more than a dozen or so
input words. But you could implement a method that is efficient with a
larger list of words.
"""
def natalie(words):
"Find the best Portmanteau word formed from any two of the list of words."
#we will represent a natalie with a tuple (word, score)
natalies = []
for (word1, word2) in getWordPairs(words):
mid = ''
endpos = 1
while word1.find(word2[0:endpos]) != -1 and endpos <= len(word2):
mid = word2[0:endpos]
endpos +=1
start = substringBefore(word1, mid)
end = substringAfter(word2, mid)
if mid == '' or len(start) == 0 or len(end) == 0:
#we didn't find a natalie
continue
word = start + mid + end
score = len(word) - abs(len(start)-(len(word)/4.0)) - abs(len(mid)-(len(word)/2.0)) - abs(len(end)-(len(word)/4.0))
natalies.append((word, score))
if len(natalies) == 0:
return None
max_score = max([natalie[1] for natalie in natalies])
#remark: I only return the first hit among several best matches
return [ele[0] for ele in natalies if ele[1] == max_score][0]
def substringAfter(text, substring):
start = text.find(substring)
if start == -1:
return ''
return text[start + len(substring):]
def substringBefore(text, substring):
start = text.find(substring)
if start == -1:
return ''
return text[:start]
def getWordPairs(words):
from itertools import permutations
perms = list(permutations(words, 2))
return perms
def test_natalie():
"Some test cases for natalie"
assert natalie(['adolescent', 'scented', 'centennial', 'always', 'ado']) == 'adolescented'
assert natalie(['eskimo', 'escort', 'kimchee', 'kimono', 'cheese']) == 'eskimono'
assert natalie(['kimono', 'kimchee', 'cheese', 'serious', 'us', 'usage']) == 'kimcheese'
assert natalie(['circus', 'elephant', 'lion', 'opera', 'phantom']) == 'elephantom'
assert natalie(['programmer', 'coder', 'partying', 'merrymaking']) == 'programmerrymaking'
assert natalie(['int', 'intimate', 'hinter', 'hint', 'winter']) == 'hintimate'
assert natalie(['morass', 'moral', 'assassination']) == 'morassassination'
assert natalie(['entrepreneur', 'academic', 'doctor', 'neuropsychologist', 'neurotoxin', 'scientist', 'gist']) == 'entrepreneuropsychologist'
assert natalie(['perspicacity', 'cityslicker', 'capability', 'capable']) == 'perspicacityslicker'
assert natalie(['backfire', 'fireproof', 'backflow', 'flowchart', 'background', 'groundhog']) == 'backgroundhog'
assert natalie(['streaker', 'nudist', 'hippie', 'protestor', 'disturbance', 'cops']) == 'nudisturbance'
assert natalie(['night', 'day']) == None
assert natalie(['dog', 'dogs']) == None
assert natalie(['test']) == None
assert natalie(['']) == None
assert natalie(['ABC', '123']) == None
assert natalie([]) == None
return 'tests pass'
No comments:
Post a Comment