Paul Butcher from the Texperts recently wrote a great blog post with a Ruby implementation of Escape from Zurg. I had been meaning to learn both Ruby and Haskell for a long time and recently invested in some reading material. But it wasn’t long before I got the craving to write a Java version. The idea is not to solve this specific problem, but to use it to show how more general searches may be solved in these languages.
Buzz, Woody, Rex, and Hamm have to escape from Zurg. They must cross one last bridge before they are free. However, the bridge is fragile and can hold at most two of them at the same time. Moreover, to cross the bridge a flashlight is needed to avoid traps and broken parts. The problem is that our friends have only one flashlight with one battery that lasts for only 60 minutes. The toys need different times to cross the bridge (in either direction):
- Buzz: 5 minutes
- Woody: 10 minutes
- Rex: 20 minutes
- Hamm: 25 minutes
The problem is: In which order should the four toys cross the bridge?
The problem may be solved by a brute-force search in a finite state-space (due to the “hard” limit of 60 minutes). Any valid solution (i.e. not necessarily optimal) will do, so the search is complete when the first valid solution is found. This is not really a generic search problem as search spaces may be infinite, have “soft” limits and optimal solutions may be required. However, it does make for a good programming exercise.
Search problems of this variety can be visualised as a tree graph with the vertices representing the state at a specific point in time, and the edges indicating a change of state. The hard limit in this example kills off any cycles that may arise. The algorithm employed by the original Haskell implementation is a forwards depth-first search, which is memory efficient as it does not store the entire state space in memory. We will do the same here but we’ll find all the solutions, not just the first one.
In true Java style, we’ll try to be as general as possible to begin with and come up with a dumb depth-first algorithm to print out all the valid solutions to search problems with a hard limit. We then realise that our most important object types are interfaces for State and Move, which we define as
// implementations should override equals()
public interface State {
public State move(Move move);
public Set<Move> moves();
}
public interface Move {
public int cost();
}and then the depth-first solution is implemented as
public class SearchProblem {
private final State end;
private final State initial;
private final int limit;
public SearchProblem(State initial, State end, int limit) {
this.initial = initial;
this.end = end;
this.limit = limit;
}
public void solve() {
solve(initial, 0);
}
private void solve(State state, int existingCost) {
for (Move move : state.moves()) {
int cost = existingCost + move.cost();
if (cost > limit)
continue;
State newState = state.move(move);
if (newState.equals(end)) {
System.out.println("Solution discovered at " + newState);
continue;
}
solve(newState, cost);
}
}
}We now still need to code up the specific problem… let’s define the Toys as enums with a set time and the sides of the bridge as an enum
public enum Toy {
Buzz(5), Hamm(25), Rex(20), Woody(10);
private final int time;
Toy(int time) {
this.time = time;
}
public int getTime() {
return time;
}
}
public enum Direction { Left, Right }and implement Move
class ToyStoryMove implements Move {
private final Direction direction;
private final List<Toy> toys;
public ToyStoryMove(List<Toy> toys, Direction direction) {
this.toys = toys;
this.direction = direction;
}
@Override
public int cost() {
if (toys.size() == 1)
return toys.get(0).getTime();
return Math.max(toys.get(0).getTime(), toys.get(1).getTime());
}
}The generation of the moves is implemented in State (Note: updated, see comments for original)
@Override
public Set<Move> moves() {
Set<Move> moves = new HashSet<Move>();
if (torch == Direction.Left) {
for (List<Toy> moving : combinations(leftBank)) {
moves.add(new ToyStoryMove(moving, Direction.Right));
}
} else {
Set<Toy> toys = exclusive(Arrays.asList(Toy.values()), leftBank);
for (Toy toy : toys) {
moves.add(new ToyStoryMove(Arrays.asList(toy), Direction.Left));
}
}
return moves;
}everything else is pretty much Eclipse-generated boilerplate. Running the code gives the two solutions
- Buzz and Woody go right
- Buzz goes left
- Hamm and Rex go right
- Woody goes left
- Woody and Buzz go right
and
- Buzz and Woody go right
- Woody goes left
- Hamm and Rex go right
- Buzz goes left
- Woody and Buzz go right
Full code available as a zip download. Admittedly, it is somewhat more verbose than the Ruby or Haskell code… but at least 1/5 of the code is in documentation and everything you don’t see above was either auto-generated by Eclipse or is a debugging assertion. The search space is exhausted within 40 milliseconds on my MacBook, but it’s a really small space so that doesn’t say much.
PS: I really like Haskell after reading this introduction.
Paul Butcher wrote:
October 13th, 2007 at 11:36 pm