C Answers to Exercises
Chapter 8
Solution to Exercise 8.1
For simplicity, we assume that levels are stored as arrays of Strings, for example as follows:
public static String[] sokoban1 = {
" #####",
" # #",
" #$ #",
" ### $##",
" # $ $ #",
"### # ## # ######",
"# # ## ##### ..#",
"# $ $ ..#",
"##### ### #@## ..#",
" # #########",
" #######"
};
The parse() method in Listing C.62 constructs an instance of Level from such an array of strings. The function first determines the level’s width and height by counting the number of columns and rows in the textual description and then iterates over the rows a second time to place the individual objects.
Listing C.62ch8 / Level
public static Level parse(String[] rows) {
int width = 0;
for (String row : rows)
width = Math.max(width, row.length());
int height = rows.length;
var level = new Level(width, height);
for (int y = 0; y < height; y++) {
for (int x = 0; x < rows[y].length(); x++) {
level.setCode(x, y, rows[y].charAt(x));
}
}
return level;
}
Solution to Exercise 8.2
Like the other methods defined in GameState, the toString() method shown in Listing C.63 takes an additional argument of type Level. It iterates over the the rows and columns of the level and computes the correct character code for each square.
Listing C.63ch8 / GameState
// Return the ASCII representation of this game state.
public String toString(Level level) {
var sb = new StringBuilder();
for (int y = 0; y < level.height(); y++) {
for (int x = 0; x < level.width(); x++) {
char charCode;
int index = level.index(x, y);
if (level.walls().contains(index)) {
charCode = '#';
} else if (index == workerPos) {
charCode = level.goals().contains(index) ? '+' : '@';
} else if (crates.contains(index)) {
charCode = level.goals().contains(index) ? '*' : '$';
} else {
charCode = level.goals().contains(index) ? '.' : ' ';
}
sb.append(charCode);
}
sb.append('\n');
}
return sb.toString();
}
Solution to Exercise 8.3
A level is closed if no positions on the boundary of the level can be reached from the worker’s starting position. The solution in Listing C.64 first constructs the move graph of the level with all crates removed and then uses breadth-first search to check whether it is possible to reach any position on the boundary.
Listing C.64ch8 / LevelClosed
public static boolean isLevelClosed(Level level) {
var moveGraph = new MoveGraph(level, new BitSet());
Integer posOutside = moveGraph.scan(
level.workerStart(),
pos -> level.getX(pos) == 0 || level.getY(pos) == 0
|| level.getX(pos) == level.width() - 1
|| level.getY(pos) == level.height() - 1);
return posOutside == null;
}
Solution to Exercise 8.4
We first compute the interior of the level using breadth-first search. For each interior position that is not occupied by a crate and not already in a known component, we then use breadth-first search again to find all the nodes it is connected to, which gives us the next component. For an implementation, see Listing C.65.
Listing C.65ch8 / Components
static List<BitSet> findComponents(Level level, BitSet crates) {
var interior = new BitSet();
new MoveGraph(level, new BitSet())
.visitNodes(level.workerStart(), interior::add);
var inComponent = new BitSet();
var components = new ArrayList<BitSet>();
for (int pos : interior) {
if (!crates.contains(pos) && !inComponent.contains(pos)) {
var component = new BitSet();
new MoveGraph(level, crates)
.visitNodes(pos, component::add);
components.add(component);
inComponent.addAll(component);
}
}
return components;
}
JDK: ArrayList, List
•BitSet: add(), BitSet(), contains()
•Graph: visitNodes()
•Level: workerStart()
•MoveGraph: MoveGraph()
Solution to Exercise 8.5
A function compressMoves() that compresses a string of movement commands is shown in Listing C.66. The compressed solution of Level 1 is:
u3l3uLUllDDuuruurDldldll3dr12RurD 14lulld15R 13l3urrdD3uruul4Dull3dr11RurD 13l3urrdDuull3dr11R 7l3ulLul3D4urrDlldll3dr10RdrUluRR lld6l3uLLul3Duull3dr10RdrUluR
Listing C.66ch8 / SokobanSolver
// Replace runs of identical letters with an integer followed
// by a single letter
static String compressMoves(String moves) {
var sb = new StringBuilder();
for (int i = 0; i < moves.length(); i++) {
char move = moves.charAt(i);
int count = 1;
while (i < moves.length() - 1 && moves.charAt(i + 1) == move) {
i++;
count++;
}
if (count > 2)
sb.append(count);
else if (count == 2)
sb.append(move);
sb.append(move);
}
return sb.toString();
}
JDK: String, StringBuilder
Solution to Exercise 8.6
Changing the order of neighbors doesn’t affect the length of the shortest path through the push graph, but it does cause breadth-first search to discover a different solution first. With the standard order, the solver favors nearby crates, which leads to a solution in which the total distance traveled by the worker is fairly small (but not minimal, as we will discuss in Section 8.5). Reversing the list of neighbors, on the other hand, favors far-away crates, which produces a solution in which the worker constantly alternates between different crates. In the case of Level 1, the resulting solution requires 926 steps and starts as follows:
u3l3uLUluurDldlDll3drRll3urrDull3drr4R6l3urrdDuull3drRdd4ruu
This solution also requires the minimum 97 pushes.
Solution to Exercise 8.7
Node E has a total of eight neighbors that correspond to moving the left or the right crate in each of four directions. Moving the left crate up brings us back to the starting node S. The remaining options are moving the left crate down (E1), right (E2), left (E3), and moving the right crate up (E4), down (E5), left (E6), or right (E7).
Solution to Exercise 8.8
a)Figure C.14 marks all dead squares in the level using an X.
b)One way to show that a position \(p\) is dead is to place a single crate at \(p\) and show that, regardless of the worker’s position, the resulting level cannot be solved. (The only positions of the worker that must be checked are the four squares next to \(p\).) If we repeat this for all positions \(p\) inside the level, we obtain the list of all dead squares.
We can solve the problem more efficiently by considering the reverse problem: Which positions in a level are reachable by pulling a crate that starts at one of the goal squares? Similar to the push graph, we can define a pull graph in which two positions are adjacent if the worker can pull a crate from one position to the other. To compute the list of dead squares, we first determine all reachable positions in the level and then successively remove positions that are reachable by repeatedly pulling a crate from each of the goals. The positions that remain are the level’s dead squares. An implementation is shown in Listing C.67.
Listing C.67ch8 / DeadSquares
public static BitSet computeDeadSquares(Level level) {
// An edge x -> y in the following graph indicates that a
// crate can be pulled from position x to position y.
var pullGraph = new Graph<Integer>() {
public List<Integer> neighbors(Integer pos) {
var neighbors = new ArrayList<Integer>();
for (var direction : Board.ALL_DIRECTIONS) {
int neighbor = level.moveIndex(pos, direction);
if (neighbor == -1)
continue;
int worker = level.moveIndex(neighbor, direction);
if (worker == -1)
continue;
if (!level.walls().contains(neighbor) &&
!level.walls().contains(worker)) {
neighbors.add(neighbor);
}
}
return neighbors;
}
};
// Start with the interior of the level, then remove squares that
// can be reached by pulling a crate from any of the goal squares.
var deadSquares = new BitSet();
new MoveGraph(level, new BitSet())
.visitNodes(level.workerStart(), deadSquares::add);
for (int goal : level.goals())
pullGraph.visitNodes(goal, deadSquares::remove);
return deadSquares;
}
JDK: ArrayList, List
•BitSet: BitSet()
•Board: ALL_DIRECTIONS, moveIndex()
•Graph: visitNodes()
•Level: goals(), walls(), workerStart()
•MoveGraph: MoveGraph()
Solution to Exercise 8.9
a)The UKACD is stored as a text file that contains one entry per line. The readWords() method in Listing C.68 reads the entire file and creates a list of entries that contain only alphabetic characters and have the correct length wordLength. As a special case, the functions returns all words if the wordLength parameter is negative.
Listing C.68ch8 / words / WordList
// Read all words of the given length from the file at 'path'.
// Each line is assumed to contain a single word.
public static Collection<String> readWords(
String path, int wordLength) throws IOException {
var words = new ArrayList<String>();
var reader = new BufferedReader(new FileReader(path));
while (reader.ready()) {
String entry = reader.readLine().toLowerCase();
if (entry.matches("[a-zA-Z]*") &&
(entry.length() == wordLength || wordLength < 0)) {
words.add(entry);
}
}
return words;
}
JDK: ArrayList, BufferedReader, Collection, IOException, String
b)The neighbors of HAPPY are contained in four buckets: APPY, HPPY, HAPY, and HAPP. (The bucket HAPY corresponds to deleting either occurrence of the letter P.) HARPY belongs to five buckets: ARPY, HRPY, HAPY, HARY, and HARP.
c)A word \(w\) of length \(n\) must be added to \(n\) buckets, and the key of the \(k\)th bucket is obtained by deleting the \(k\)th letter of \(w\); see Listing C.69. Likewise, to find the neighbors of a word \(w\), we inspect all matching buckets and pick those entries that differ from \(w\) in exactly one letter.
Listing C.69ch8 / words / SimilarWords
private void addWord(String word) {
for (int i = 0; i < word.length(); i++) {
String key = deleteLetter(word, i);
buckets.computeIfAbsent(key, k -> new HashSet<>()).add(word);
}
}
public Collection<String> findSimilarWords(String word) {
var result = new ArrayList<String>();
for (int i = 0; i < word.length(); i++) {
for (String n : buckets.get(deleteLetter(word, i))) {
int distance = 0; // number of letters that differ
for (int j = 0; j < n.length() && distance <= 1; j++) {
if (n.charAt(j) != word.charAt(j))
distance++;
}
if (distance == 1)
result.add(n);
}
}
return result;
}
private static String deleteLetter(String word, int index) {
var sb = new StringBuilder(word);
sb.deleteCharAt(index);
return sb.toString();
}
JDK: ArrayList, Collection, HashSet, String, StringBuilder
•SimilarWords
d)The WordLadderGraph class shown in Listing C.70 computes the word ladder graph for an arbitrary set of words. The nodes of this graph are stored in the words field, and its edges are computed on the fly.
Listing C.70ch8 / words / WordLadderGraph
public class WordLadderGraph implements Graph<String> {
private final Set<String> words;
private final SimilarWords similar;
public WordLadderGraph(Collection<String> words) {
this.words = new HashSet<>(words);
similar = new SimilarWords(words);
}
@Override
public Collection<String> nodes() {return words;}
@Override
public Collection<String> neighbors(String word) {
if (!words.contains(word))
return Collections.emptyList();
return similar.findSimilarWords(word);
}
}
JDK: Collection, HashSet, Set, String
•Graph
•SimilarWords: findSimilarWords(), SimilarWords()
e)Four steps are necessary to transform ROCK into GOLD:
\[ \text {ROCK}\to {}\text {ROOK}\to {}\text {GOOK}\to {}\text {GOOD}\to {}\text {GOLD}. \]
To compute the list of words that cannot be transformed into GOLD, traverse the graph starting at GOLD and afterward report all nodes that weren’t reached; there are 90 such words. The words ETNA and ODIN have the largest distance 11 from GOLD.
f)The longest word ladder is the one between ISLA and ZEBU:
\(\seteqnumber{0}{C.}{7}\)\begin{gather*} \text {ISLA}\to {}\text {ISLE}\to {}\text {IDLE}\to {}\text {IDLY}\to {}\text {ILLY}\to {}\text {ALLY}\to {}\text {ALAY}\to {}\text {FLAY}\to {}\text {FLEY}\to {}\\ \text {GLEY}\to {}\text {GOEY}\to {}\text {GOBY}\to {}\text {GOBO}\to {}\text {ZOBO}\to {}\text {ZOBU}\to {}\text {ZEBU} \end{gather*} There are four pairs of words that can be transformed into their reverse: REVILER/RELIVER, REVILED/DELIVER, DEIFIER/REIFIED, STENNED/DENNETS.
Solution to Exercise 8.10
a)The distribution of light is shown in Fig. C.15.
b)Every object either emits light by itself or reflects incoming light. To model this behavior, we use the interface LaserPiece defined in Listing C.71, which defines two methods: emit() returns the directions in which incoming light is emitted and reflect() the directions in which light is reflected. We use the Direction class defined in Listing 8.3 to represent the four directions up, down, left, and right. The listing also defines two simple pieces: the empty square (EMPTY), which transmits incoming light unchanged, and the solid block (BLOCKER), which absorbs all incoming light. EMPTY is implemented as a function that returns a list that contains just the direction of the incoming light ray, and BLOCKER as a function that returns an empty list regardless of the incoming light.
Listing C.71ch8 / lasers / LaserPiece
public interface LaserPiece {
default List<Board.Direction> emit() {
return List.of();
}
List<Board.Direction> reflect(Board.Direction incoming);
LaserPiece EMPTY = List::of;
LaserPiece BLOCKER = incoming -> List.of();
}
A laser is another simple LaserPiece: it emits light in a single fixed direction but doesn’t reflect any incoming light (Listing C.72).
Listing C.72ch8 / lasers / Emitter
record Emitter(Board.Direction direction) implements LaserPiece {
@Override
public List<Board.Direction> reflect(Board.Direction incoming) {
return List.of();
}
@Override
public List<Board.Direction> emit() {
return List.of(direction);
}
}
JDK: List
•Board: Direction
•LaserPiece
A more complex object is the transparent mirror because the direction of the outgoing rays depends both on the direction of the incoming ray and the orientation of the mirror. To implement reflect(), we create a table that maps all possible combinations of mirror orientations and incoming rays to the resulting outgoing directions (Listing C.73). For instance, the first key “|l” represents a vertical mirror and an incoming ray that moves towards the left, and the associated value is a list of two directions that indicates that the ray splits into two and continues to the left and to the right. The other orientations of the mirror are encoded as “\”, “-”, and “/”. The reflect() method returns the list of directions in which an incoming light ray is split; this is either one of the values stored in map or the empty list when the light ray is blocked.
Listing C.73ch8 / lasers / TransparentMirror
record TransparentMirror(String orientation) implements LaserPiece {
static Map<String, List<Board.Direction>> map = Map.ofEntries(
Map.entry("|l", List.of(LEFT, RIGHT)),
Map.entry("|r", List.of(LEFT, RIGHT)),
Map.entry("-u", List.of(UP, DOWN)),
Map.entry("-d", List.of(UP, DOWN)),
Map.entry("/r", List.of(UP, RIGHT)),
Map.entry("/u", List.of(UP, RIGHT)),
Map.entry("/l", List.of(LEFT, DOWN)),
Map.entry("/d", List.of(LEFT, DOWN)),
Map.entry("\\u", List.of(UP, LEFT)),
Map.entry("\\l", List.of(UP, LEFT)),
Map.entry("\\r", List.of(RIGHT, DOWN)),
Map.entry("\\d", List.of(RIGHT, DOWN)));
@Override
public List<Board.Direction> reflect(Board.Direction incoming) {
return map.getOrDefault(orientation + incoming.charCode(),
List.of());
}
}
JDK: List, Map
•Board: Direction, DOWN, LEFT, RIGHT, UP
•Board.Direction: charCode()
•LaserPiece
c)The key idea is to model the problem as a graph in which each square on the board is represented by four nodes, one for each of its four sides. We can label the nodes using tuples of the form \((p,d)\), where \(p\) is the position of the square and \(d\) a direction (up, down, left, or right). The node \((p,d)\) represents a ray of light that leaves the square \(p\) in direction \(d\).
An implementation of this idea is shown in Listing C.74. The LaserBoard class extends the Board class we developed for representing Sokoban levels, which
simplifies the task of computing with positions on the board and directions. It also implements the Graph
Listing C.74ch8 / lasers / LaserBoard
// A graph for simulating the propagation of light on a rectangular board.
public class LaserBoard extends Board
implements Graph<LaserBoard.Ray> {
public record Pos(int x, int y) {}
public record Ray(Pos pos, Direction direction) {}
private Map<Pos, LaserPiece> pieces = new HashMap<>();
public LaserBoard(int width, int height) {
super(width, height);
}
public void setPiece(int x, int y, LaserPiece piece) {
pieces.put(new Pos(x, y), piece);
}
// ...
}
•Board
•Graph
•LaserPiece
To compute the neighbors of a node ray in this graph, we first look up the object the ray hits next and then reflect it depending on the object’s type and the ray’s current direction (Listing C.75).
Listing C.75ch8 / lasers / LaserBoard
// Each ray is connected to the rays it spawns in neighboring squares.
@Override
public List<Ray> neighbors(Ray ray) {
Pos neighbor = new Pos(ray.pos.x + ray.direction.xOff(),
ray.pos.y + ray.direction.yOff());
if (!isInside(neighbor.x(), neighbor.y()))
return List.of();
var newRays = new ArrayList<Ray>();
LaserPiece piece =
pieces.getOrDefault(neighbor, LaserPiece.EMPTY);
for (var direction : piece.reflect(ray.direction))
newRays.add(new Ray(neighbor, direction));
return newRays;
}
JDK: ArrayList, List
•Board: Direction
•Board.Direction: xOff(), yOff()
•Graph
•LaserBoard: Pos, Ray
•LaserPiece: EMPTY, reflect()
We can now simulate the propagation of light as shown in Listing C.76. For every LaserPiece on the board, we first call emit() to determine the outgoing rays of light, and then follow each such ray by traversing the graph using breadth-first search. Every Ray discovered by visitNodes() is stored in a set rays that represents the final distribution of light on the board. For example, the resulting set of rays for the board in Fig. 8.9 can be visualized as follows:
.... .d.. .... .... .d.. .... .... udl. ..l. ..l. udlr ...r .... ud.. .... .... ud.. .... ..l. udlr ..lr ..lr u.l. ....
Listing C.76ch8 / lasers / LaserBoard
// Simulate the propagation of light by following the rays emitted
// by each piece on the board.
public Set<Ray> simulateLight() {
var rays = new HashSet<Ray>();
for (Pos p : pieces.keySet()) {
var piece = pieces.get(p);
for (var direction : piece.emit()) {
var ray = new Ray(p, direction);
visitNodes(ray, rays::add);
}
}
return rays;
}
JDK: HashSet, Set
•Graph: visitNodes()
•LaserBoard: Pos, Ray
•LaserPiece: EMPTY
Solution to Exercise 8.11
a)We can model the board as a weighted graph in which each node corresponds to a position on the board. Using the Board and WeightedGraph types developed in this chapter, we define a graph CivBoard that models the movement on the board (Listing C.77). The terrain field holds the type of terrain for every square on the board: We use “␣” for grasslands, “f” for forests, “w” for water, and “m” for mountains.
Listing C.77ch8 / civ
public class CivBoard extends Board
implements WeightedGraph<CivBoard.Pos> {
public record Pos(int x, int y) {}
private final List<Character> terrain;
public CivBoard(int width, int height) {
super(width, height);
terrain = new ArrayList<>(
Collections.nCopies(width * height, ' '));
}
char getTerrain(Pos p) {
return terrain.get(index(p.x(), p.y()));
}
// ...
}
JDK: ArrayList, Character, Collections, List
•Board
•WeightedGraph
For a given position on the board, the outgoing edges point to neighboring positions that are reachable, and the weight of each edge reflects the cost of moving to that position (Listing C.78).
Listing C.78ch8 / civ / CivBoard
public List<Edge<Pos>> edges(Pos pos) {
var edges = new ArrayList<Edge<Pos>>();
for (var dir : ALL_DIRECTIONS) {
Pos neighbor = new Pos(pos.x + dir.xOff(), pos.y + dir.yOff());
if (!isInside(neighbor.x(), neighbor.y()))
continue;
int weight = switch (getTerrain(neighbor)) {
case ' ' -> 1;
case 'f' -> 2;
case 'w' -> getTerrain(pos) == 'w' ? 1 : 3;
case 'm' -> Integer.MAX_VALUE;
default -> throw new RuntimeException("Invalid terrain");
};
if (weight != Integer.MAX_VALUE) {
edges.add(new Edge<>(neighbor, weight));
}
}
return edges;
}
JDK: ArrayList, Integer, List, RuntimeException
•Board: ALL_DIRECTIONS, Direction
•CivBoard: Pos
•WeightedGraph: Edge
b)Figure C.16 shows the distance of every square from G2.
| A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | |
| 0 | 11 | 9 | 7 | 5 | 4 | 3 | 4 | 5 | 7 | 9 | 11 | 10 | 11 | 12 | 13 | 14 |
| 1 | 10 | 8 | 6 | 4 | 3 | 2 | 1 | 4 | 6 | 8 | 9 | 9 | 10 | 11 | 12 | 14 |
| 2 | 10 | 9 | 7 | 5 | 3 | 1 | 0 | 3 | 4 | 6 | 7 | 8 | 9 | 11 | 13 | 15 |
| 3 | 10 | 9 | 8 | 6 | 4 | 2 | 3 | 4 | 5 | 6 | 7 | – | 11 | 12 | 13 | 14 |
| 4 | 11 | 10 | – | 6 | 4 | 3 | 4 | 5 | 6 | 7 | 9 | – | – | 13 | 14 | 15 |
| 5 | – | – | 10 | 7 | 5 | 4 | 5 | 7 | – | 8 | 9 | – | – | 14 | 15 | 16 |
| 6 | 13 | 12 | 11 | 9 | 8 | 6 | 7 | 9 | 11 | – | 10 | 11 | 12 | 13 | 15 | 16 |
| 7 | 13 | 12 | 11 | 10 | 10 | 8 | 9 | 11 | 13 | 14 | 12 | 12 | 13 | 15 | 18 | 17 |
| 8 | 14 | 13 | 12 | 11 | 11 | 10 | 11 | 13 | 15 | 16 | 14 | 13 | 14 | 15 | 17 | 18 |
| 9 | 15 | 14 | 13 | 13 | 13 | 12 | 13 | 15 | 16 | 17 | 15 | 14 | 15 | 17 | 18 | 20 |
| 10 | 16 | 15 | 15 | 15 | 15 | 13 | 14 | 15 | 16 | 17 | 16 | 15 | 16 | 17 | 19 | 21 |
There several similar shortest paths of length 13 from G2 to M7. One is
\[ \text {G2}\to {}\text {H2}\to {}\text {H3}\to {}\text {H4}\to {}\text {I4}\to {}\text {J4}\to {}\text {J5}\to {}\text {K5}\to {}\text {K6}\to {}\text {L6}\to {}\text {L7}\to {}\text {M7}. \]