## Dictionaries and Tuples

Another application of tuples is to use them as keys in dictionaries. Follow and practice the examples presented in this section in order to understand how tuples can be used with dictionaries.

### Tuples

#### Solution

from __future__ import print_function, division

def make_word_dict():
"""Reads a word list and returns a dictionary."""
d = dict()
fin = open('words.txt')
for line in fin:
word = line.strip().lower()
d[word] = None

# have to add single letter words to the word list;
# also, the empty string is considered a word.
for letter in ['a', 'i', '']:
d[letter] = letter
return d

"""memo is a dictionary that maps from each word that is known
to be reducible to a list of its reducible children.  It starts
with the empty string."""

memo = {}
memo[''] = ['']

def is_reducible(word, word_dict):
"""If word is reducible, returns a list of its reducible children.
Also adds an entry to the memo dictionary.
A string is reducible if it has at least one child that is
reducible.  The empty string is also reducible.
word: string
word_dict: dictionary with words as keys
"""
if word in memo:
return memo[word]

# check each of the children and make a list of the reducible ones
res = []
for child in children(word, word_dict):
if is_reducible(child, word_dict):
res.append(child)

# memoize and return the result
memo[word] = res
return res

def children(word, word_dict):
"""Returns a list of all words that can be formed by removing one letter.
word: string
Returns: list of strings
"""
res = []
for i in range(len(word)):
child = word[:i] + word[i+1:]
if child in word_dict:
res.append(child)
return res

def all_reducible(word_dict):
"""Checks all words in the word_dict; returns a list reducible ones.
word_dict: dictionary with words as keys
"""
res = []
for word in word_dict:
t = is_reducible(word, word_dict)
if t != []:
res.append(word)
return res

def print_trail(word):
"""Prints the sequence of words that reduces this word to the empty string.
If there is more than one choice, it chooses the first.
word: string
"""
if len(word) == 0:
return
print(word, end=' ')
t = is_reducible(word, word_dict)
print_trail(t[0])

def print_longest_words(word_dict):
"""Finds the longest reducible words and prints them.
word_dict: dictionary of valid words
"""
words = all_reducible(word_dict)

# use DSU to sort by word length
t = []
for word in words:
t.append((len(word), word))
t.sort(reverse=True)

# print the longest 5 words
for _, word in t[0:5]:
print_trail(word)
print('\n')

if __name__ == '__main__':
word_dict = make_word_dict()
print_longest_words(word_dict)