Exercise 8.9.A word ladder is a sequence of words of the same length in which each word differs from the last in exactly one letter. For example, the sequence ROCK, SOCK, SICK, SILK, SILD, SOLD, GOLD is a word ladder that connects the words ROCK and GOLD.
To be able to construct word ladders algorithmically, we need access to a dictionary from which we can choose the individual words. We will use the “The UK Advanced Cryptics Dictionary” (UKACD), a list of words compiled by Ross Beresford specifically for crossword puzzles and other word games. The
word list can be found in the data/UKACD17 folder at
a) Write a function that reads all \(n\)-letter words from the UKACD and returns a list of Strings. Dictionary entries that consist of multiple words or contain non-alphabetic and foreign characters should be filtered out.
For a given set of words \(W\), we can construct a graph by interpreting each word as a node and connecting two words with an edge if they differ in exactly one letter. We call the result the word-ladder graph for \(W\); for obvious reasons, every path in this graph is a word ladder. The main problem when working with word-ladder graphs is computing the neighbors of a given node \(n\). The naive solution is to it iterate
over all words in \(W\) and select those that differ from \(n\) in a single letter, but having to do this repeatedly while traversing the graph is painfully slow.
A better alternative is to construct an auxiliary data structure that helps us find words that are similar to each other. To see how this can be done, let’s consider a simplified example first. We know that all neighbors of ROCK differ in exactly one letter so they must have the form *OCK, R*CK, RO*K, or ROC*.
We can therefore prepare four “buckets” labeled OCK, RCK, ROK, and ROC and place all four-letter words that contain those three letters in the same order into the corresponding bucket:
.
bucket
words
OCK
ROCK, SOCK, LOCK, OCKY, MOCK, …
RCK
ROCK, RACK, RICK, …
ROK
ROCK, GROK, ROOK, …
ROC
ROCK, CROC, …
Each bucket contains potential neighbors, and the four buckets together are guaranteed to contain every neighbor of ROCK. Finding all neighbors of ROCK is a simple matter of iterating over the words in those four buckets and collecting those that that differ from ROCK in exactly one letter.
b) Which buckets do you have to check to find all neighbors of HAPPY and HARPY?
Now consider the outline of a class for finding similar words shown in Listing 8.22. The field buckets maps keys of type String to sets of words. Each entry of
buckets represent a bucket as described above. The constructor takes a list of words and adds them to the data structure. To complete this class, we need to implement two methods. The first method addWord() takes a single word and adds it
to all buckets it belongs to. The second method findSimilarWords() takes a word and returns all entries in the data structure that differ from word in a single letter.
Listing 8.22ch8 / words
public class SimilarWords {
private final Map<String, Set<String>> buckets = new HashMap<>();
public SimilarWords(Collection<String> words) {
for (String w : words)
addWord(w);
}
public void addWord(String word) {
// ...
}
public List<String> findSimilarWords(String word) {
// ...
}
}
c) Implement addWord() and findSimilarWords().
d) Write a class for representing word-ladder graphs. The nodes of the graph are strings of a certain length, and two nodes are mututal neighbors if their strings differ in exactly one character.
e) What is the shortest word ladder that transforms ROCK into GOLD? Are there any four-letter words that cannot be transformed into GOLD? Which word is hardest to transform into GOLD?
f) What is the longest word ladder between a pair of four-letter words? What seven-letter words can be transformed into their reverse?
Lasers and Mirrrors
Exercise 8.10.A popular type of puzzle that can be found in many computer games asks the player to manipulate one or more light rays, either by blocking them with obstacles or by
redirecting them with mirrors. In this exercise, we will simulate the propagation of light rays on a board consisting of \(w\times h\) squares. A square on the board is either empty or it contains an object that emits a beam of light or interacts with incoming light. There are four kinds of objects, and each
interacts differently with incoming light:
•Obstacles () block all incoming light.
•Emitters () block incoming light but emit light in a fixed direction.
•Opaque mirrors () reflect or block incoming light, depending on the mirror’s orientation relative to the light ray.
•Semi-transparent mirrors () reflect, block, or transmit incoming light, depending on the mirror’s orientation relative to the light ray.
Mirrors can have four different orientations. The following diagram shows how diagonal and horizontal mirrors reflect light:
In the diagonal orientation, the mirror reflects incoming light at a 90 degree angle, and in the horizontal orientation, it reflects only light that hits the mirror itself but not its side. Semi-transparent mirrors behave similarly but also transmit the incoming light:
Diagrams for the remaining two orientations can be obtained by rotating the pictures by 90 degrees.
Figure 8.9 shows a simple scene that consists of a single emitter pointing downwards, four mirrors in different orientations, and one obstacle that blocks all incoming light. All squares outside the scene are considered obstacles, so only
the propagation of light inside the rectangle must be considered. Starting at the emitter in the upper-left corner, the beam first moves downward until it hits the semi-transparent mirror, where it is refracted into two beams: one beam that continues downward until it is stopped by the outer wall of the
scene, and one that advances to the right, where it is reflected upward.
Figure 8.9 A scene consisting of lasers and mirrors. The laser beam is emitted by the triangle and propagates through a scene consisting of different objects that transmit, reflect, or block light.
a) Sketch the final distribution of light for the scene in Fig. 8.9.
b) Design classes for modeling individual objects and their behavior, most importantly the way they emit and reflect light.
c) Write a program that simulates the propagation of light rays through the scene.
Path Finding
Exercise 8.11.Finding the shortest path between two locations is a common problem in many computer games. In this exercise, we will consider the
problem of planning the movement of units in strategy games such as Civilization.
Figure 8.10 illustrates the kind of map that is used in such games. Units can traverse the board by moving between adjacent tiles, but the cost of movement depends on the underlying terrain. For instance, it is easier (and cheaper) to traverse
grasslands than woods, mountains are impassable, and there is a special penalty for entering water tiles. More specifically, we model the cost of movement using the following rules:
• Mountain tiles are impassable.
• Entering forest tiles costs 2 movement points.
• Entering grassland tiles costs 1 movement point.
• Entering water tiles from land costs 3 movement points.
• Moving between water tiles costs 1 movement point.
The goal is to find the path between two tiles with the lowest overall cost.
Figure 8.10 A strategy game board. Units can move horizontally and vertically, and the cost of movement depends on the underlying terrain.
a) Explain how to construct a weighted graph that can be used to model and solve this problem.
b) Use Dijkstra’s algorithm to compute the length of the shortest path from G2 to every position on the board in Fig. 8.10. What is the shortest route to M7?
) block all incoming light.
) block incoming light but emit light in a fixed direction.
) reflect or block incoming light, depending on the mirror’s orientation relative to the light ray.
) reflect, block, or transmit incoming light, depending on the mirror’s orientation relative to the light ray.