In [5]:
def anagrams(phrase, shortest=2):
"""Return a set of phrases with words from WORDS that form anagram
of phrase. Spaces can be anywhere in phrase or anagram. All words
have length >= shortest. Phrases in answer must have words in
lexicographic order (not all permutations)."""
results = []
phrase = phrase.replace(' ', '')
words = find_words(phrase)
def _check(w, p):
return len(w) + len(removed(p, w)) == len(p)
def _helper(parents, _words, _phrase):
if _phrase == '':
results.append(' '.join(sorted(parents)))
elif _words:
word = _words.pop()
if len(word) >= shortest and _check(word, _phrase):
_helper(parents+[word], set(_words), removed(_phrase, word))
_helper(parents, _words, _phrase)
_helper([], words, phrase)
return set(results)
# ------------
# Helpful functions
#
# You may find the following functions useful. These functions
# are identical to those we defined in lecture.
def removed(letters, remove):
"Return a str of letters, but with each letter in remove removed once."
for L in remove:
letters = letters.replace(L, '', 1)
return letters
def find_words(letters):
return extend_prefix('', letters, set())
def extend_prefix(pre, letters, results):
if pre in WORDS: results.add(pre)
if pre in PREFIXES:
for L in letters:
extend_prefix(pre+L, letters.replace(L, '', 1), results)
return results
def prefixes(word):
"A list of the initial sequences of a word, not including the complete word."
return [word[:i] for i in range(len(word))]
def readwordlist(filename):
"Return a pair of sets: all the words in a file, and all the prefixes. (Uppercased.)"
wordset = set(open(filename).read().upper().split())
prefixset = set(p for word in wordset for p in prefixes(word))
return wordset, prefixset
WORDS, PREFIXES = readwordlist('words4k.txt')
# ------------
# Testing
#
# Run the function test() to see if your function behaves as expected.
def test():
assert 'DOCTOR WHO' in anagrams('TORCHWOOD')
assert 'BOOK SEC TRY' in anagrams('OCTOBER SKY')
assert 'SEE THEY' in anagrams('THE EYES')
assert 'LIVES' in anagrams('ELVIS')
assert anagrams('PYTHONIC') == set([
'NTH PIC YO', 'NTH OY PIC', 'ON PIC THY', 'NO PIC THY', 'COY IN PHT',
'ICY NO PHT', 'ICY ON PHT', 'ICY NTH OP', 'COP IN THY', 'HYP ON TIC',
'CON PI THY', 'HYP NO TIC', 'COY NTH PI', 'CON HYP IT', 'COT HYP IN',
'CON HYP TI'])
return 'tests pass'
print test()
In [16]:
'c' > 'ba'
Out[16]:
In [1]:
# In this problem, you will define a function, boggle_words(),
# that takes a board as input and returns a set of words that
# can be made from the board according to the rules of Boggle.
def boggle_words(board, minlength=3):
"Find all the words on this Boggle board; return as a set of words."
result = set()
N = int(len(board)**0.5)
def _dfs(word, _i, index):
for n in neighbors(_i, N):
if n not in index and board[n] != '|':
_word = word+board[n]
if _word in WORDS and len(_word) >= minlength:
result.add(_word)
if _word in PREFIXES:
_dfs(_word, n, index | set([n]))
for (i, c) in enumerate(board):
if c != '|':
_dfs(c, i, set([i]))
return result
def test():
b = Board('XXXX TEST XXXX XXXX')
assert b == '|||||||XXXX||TEST||XXXX||XXXX|||||||'
assert display(b) == """
||||||
|XXXX|
|TEST|
|XXXX|
|XXXX|
||||||""".strip()
assert boggle_words(b) == set(['SET', 'SEX', 'TEST'])
assert neighbors(20, 6) == (13, 14, 15, 19, 21, 25, 26, 27)
assert len(boggle_words(Board('TPLER ORAIS METND DASEU NOWRB'))) == 317
assert boggle_words(Board('PLAY THIS WORD GAME')) == set([
'LID', 'SIR', 'OAR', 'LIS', 'RAG', 'SAL', 'RAM', 'RAW', 'SAY', 'RID',
'RIA', 'THO', 'HAY', 'MAR', 'HAS', 'AYS', 'PHI', 'OIL', 'MAW', 'THIS',
'LAY', 'RHO', 'PHT', 'PLAYS', 'ASIDE', 'ROM', 'RIDE', 'ROT', 'ROW', 'MAG',
'THIRD', 'WOT', 'MORE', 'WOG', 'WORE', 'SAID', 'MOR', 'SAIL', 'MOW', 'MOT',
'LAID', 'MOA', 'LAS', 'MOG', 'AGO', 'IDS', 'HAIR', 'GAME', 'REM', 'HOME',
'RED', 'WORD', 'WHA', 'WHO', 'WHOM', 'YID', 'DRAW', 'WAG', 'SRI', 'TOW',
'DRAG', 'YAH', 'WAR', 'MED', 'HIRE', 'TOWARDS', 'ORS', 'ALT', 'ORE', 'SIDE',
'ALP', 'ORA', 'TWA', 'ERS', 'TOR', 'TWO', 'AIS', 'AIR', 'AIL', 'ERA', 'TOM',
'AID', 'TOG', 'DIS', 'HIS', 'GAR', 'GAM', 'HID', 'HOG', 'PLAY', 'GOA', 'HOW',
'HOT', 'WARM', 'GOT', 'IRE', 'GOR', 'ARS', 'ARM', 'ARE', 'TOWARD', 'THROW'])
return 'tests pass'
def Board(text):
"""Input is a string of space-separated rows of N letters each;
result is a string of size (N+2)**2 with borders all around."""
rows = text.split()
N = len(rows)
rows = [BORDER*N] + rows + [BORDER*N]
return ''.join(BORDER + row + BORDER for row in rows)
def size(board): return int(len(board)**0.5)
def neighbors(i, N):
return (i-N-1, i-N, i-N+1, i-1, i+1, i+N-1, i+N, i+N+1)
BORDER = '|'
def display(board):
"Return a string representation of board, suitable for printing."
N = size(board)
return '\n'.join(board[i:i+N] for i in range(0, N**2, N))
# ------------
# Helpful functions
#
# You may find the following functions useful. These functions
# are identical to those we defined in lecture.
def prefixes(word):
"A list of the initial sequences of a word, not including the complete word."
return [word[:i] for i in range(len(word))]
def readwordlist(filename):
"Return a pair of sets: all the words in a file, and all the prefixes. (Uppercased.)"
wordset = set(open(filename).read().upper().split())
prefixset = set(p for word in wordset for p in prefixes(word))
return wordset, prefixset
WORDS, PREFIXES = readwordlist('words4k.txt')
print test()
Out[1]:
In [ ]: