Java Collections Framework - Building Java Programs: A Back to Basics Approach - page 713

18. Write a method called reverse that accepts a map from strings to strings as a parameter and returns a new map that
is the reverse of the original. The reverse of a map is a new map that uses the values from the original as its keys and
the keys from the original as its values. Since a map's values need not be unique but its keys must be, you should
have each value map to a set of keys. In other words, if the original map maps keys of type K to values of type V, the
new map should map keys of type V to values that are Set s containing elements of type K. For example, the map
{42=Marty, 81=Sue, 17=Ed, 31=Dave, 56=Ed, 3=Marty, 29=Ed} has a reverse of {Marty=[42, 3],
Sue=[81], Ed=[17, 56, 29], Dave=[31]} . (The order of the keys and values does not matter.)
19. Write a method called rarest that accepts a map whose keys are strings and whose values are integers as a parameter
and returns the integer value that occurs the fewest times in the map. If there is a tie, return the smaller integer value. If
the map is empty, throw an exception.
20. Write a modified version of the Vocabulary program developed in Chapter 10 that uses sets rather than
ArrayList s to store its words. (The program will be noticeably shorter and will run faster!)
Programming Projects
1. Write a program that computes the edit distance (also called the Levenshtein distance, for its creator Vladimir
Levenshtein) between two words. The edit distance between two strings is the minimum number of operations that
are needed to transform one string into the other. For this program, an operation is a substitution of a single charac-
ter, such as from “brisk” to “brick”. The edit distance between the words “dog” and “cat” is 3, following the chain of
“dot”, “cot”, and “cat” to transform “dog” into “cat”. When you compute the edit distance between two words, each
intermediate word must be an actual valid word. Edit distances are useful in applications that need to determine how
similar two strings are, such as spelling checkers.
Read your input from a dictionary text file. From this file, compute a map from every word to its immediate neigh-
bors, that is, the words that have an edit distance of 1 from it. Once this map is built, you can walk it to find paths
from one word to another.
A good way to process paths to walk the neighbor map is to use a linked list of words to visit, starting with the
beginning word, such as “dog”. Your algorithm should repeatedly remove the front word of the list and add all of its
neighbors to the end of the list, until the ending word (such as “cat”) is found or until the list becomes empty, which
indicates that no path exists between the two words.
2. Write a program that solves the classic “stable marriage” problem. This problem deals with a group of men and a
group of women. The program tries to pair them up so as to generate as many stable marriages as possible. A set of
marriages is unstable if you can find a man and a woman who would rather be married to each other than to their
current spouses (in which case the two would be inclined to divorce their spouses and marry each other).
The input file for the program will list all of the men, one per line, followed by a blank line, followed by all of the
women, one per line. The men and women are numbered according to their positions in the input file (the first man is
#1, the second man is #2, and so on; the first woman is #1, the second woman is #2, and so on). Each input line
(except for the blank line separating men from women) lists the person's name, followed by a colon, followed by a
list of integers. These integers are the marriage partner preferences of this particular person. For example, see the
following input line in the men's section:
Joe: 10 8 35 9 20 22 33 6 29 7 32 16 18 25