Escape from Zurg
A long time ago, I got fascinated with the Zurg riddle. Aka Escape from Zurg, the Zurg riddle is a puzzle (featuring characters from the movie Toy Story) which has been used to teach students Logic Programming. Recently, Sam Halliday from the Javablog wrote a blog post with a Java implementation, and Paul Butcher from the Texperts wrote another blog post with a Ruby implementation of Escape from Zurg. Others implementations can to be find here. However it wasn’t long before I got the craving to write a Scala version. The idea is not to solve this specific problem, but to use it to show some Scala features.
Here’s the puzzle:
Buzz, Woody, Rex, and Hamm have to escape from Zurg. They merely have to 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
Since there can be only two toys on the bridge at the same time, they cannot cross the bridge all at once. Since they need the flashlight to cross the bridge, whenever two have crossed the bridge, somebody has to go back and bring the flashlight to those toys on the other side that still have to cross the bridge.
The problem is: In which order can the four toys cross the bridge in time (that is, in 60 minutes) to be saved from Zurg?
Let’s start defining the Toys as a case class with name and time fields.
case class Toy(name: String, time: Int)
Like as the Toys, the sides of the bridge are case classes, in truth, case objects.
abstract class Direction
case object Left extends Direction
case object Right extends Direction
What are case classes/objects?
Case classes and case objects are defined like a normal classes or objects, except that the definition is prefixed with the modifier case. The case modifier in front of a class or object definition has the following effects:
- Case classes implicitly come with a constructor function, with the same name as the class.
- Case classes and case objects implicitly come with implementations of methods
toString,equalsandhashCode. - Case classes implicitly come with nullary accessor methods which retrieve the constructor arguments.
- Case classes allow the constructions of patterns which refer to the case class constructor (Pattern Matching).
For more details about case classes/objects see here or in Scala Documentation.
Next, we define Move which we will use to represent transitions between states. Each move consists of a direction (right or left) and a group of toys. Move provides two methods, the cost method which returns the time taken to complete the move and the overrided toString method which provides a better print version from the move.
class Move(direction: Direction, toys: List[Toy]) {
def cost = Iterable.max(toys.map{_.time})
override def toString = "Move: " + direction + " " + toys.map{_.name}.mkString("[", ",", "]")
}
A State comprises two fields, direction which represents the current flashlight position and group which represents the toys remaining on the left-hand side of the bridge.
class State(direction: Direction, group: List[Toy]) {
def done = group.isEmpty
def next(f: (Move, State) => Unit) = direction match {
case Left => for { tuple <- group.zipWithIndex
toy <- group drop (tuple._2 + 1)
toys = List(toy, tuple._1) }
f(new Move(Right, toys), new State(Right, group diff toys))
case Right => for(toy <- (ToyStory.toys diff group))
f(new Move(Left, List(toy)), new State(Left, toy :: group))
}
}
What are the Scala features in State class?
- First-Class Functions
- Pattern Matching
- For-Comprehensions
First-Class Functions
In Scala each function is a “first-class value”. Like any other value, it may be passed as a parameter or returned as a result. Functions which take other functions as parameters or return them as results are called higher-order functions. The next method takes a function from the type (Move, State) => Unit as parameter named f.
For more details about functions see here or in Scala Documentation.
Pattern Matching
Scala has a built-in general pattern matching mechanism. Pattern matching is a generalization of C or Java’s switch statement to class hierarchies. Instead of a switch statement, there is a standard method match, which is defined in Scala’s root class Any, and therefore is available for all objects. The match method takes as argument a number of cases. Scala’s pattern matching statement is most useful for matching on algebraic types expressed via case classes. Scala also allows the definition of patterns independently of case classes, using unapply methods in extractor objects. The next method starts with the statement: direction match..., a pattern matching expression with two options: Left and Right.
For more details about pattern matching and extractor objects see here or in Scala Documentation.
For-Comprehensions
Scala offers special syntax to express combinations of certain higher-order functions more naturally. For comprehensions are a generalization of list comprehensions found in languages like Haskell and Python. They are mapped to combinations involving methods foreach and filter. For instance, the for loop for (path <- problem) ... in ToyStory object is mapped to problem foreach (path => ...) defined in SearchProblem class.
class SearchProblem(initial: State) {
def foreach(f: List[Move] => Unit) {
def solve(path: List[Move], state: State) {
if (state.done) {
f(path)
} else {
state next { (move, state) => solve(move :: path, state) }
}
}
solve(Nil, initial)
}
}
object ToyStory extends Application {
val toys = Toy("Buzz", 5) :: Toy("Woody", 10) :: Toy("Rex", 20) :: Toy("Hamm", 25) :: Nil
val problem = new SearchProblem(new State(Left, toys))
for (path <- problem)
if ((0 /: path) {(cost, move) => cost + move.cost} <= 60)
println("Solution: " + path)
}