Escape from Zurg

“Escape from Zurg” is a puzzle (featuring characters from the movie “Toy Story”) which has been used to teach students Logic Programming (in, for example, Prolog). Recently I came across a very interesting paper which presents an elegant Haskell solution to the riddle. This got me wondering about whether I could come up with a similarly satisfying solution in Ruby.

After a few false starts (mainly a result of me trying to transliterate the Prolog or Haskell solutions rather than come up with something which worked well in Ruby) I’ve come up with something that I’m pretty happy with. Not only is it (I think) concise and clear, but it’s also efficient. Given that Ruby doesn’t have built-in searching (like Prolog) and and doesn’t support lazy evaluation or list comprehension (like Haskell), the fact that the Ruby implementation is as straightforward as it turns out to be is, I think, a testament to the power of the language.

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 (this is not a typo: sixty). The toys need different times to cross the bridge (in either direction):

Buzz: 5 minutes 10 minutes 20 minutes 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 now is: In which order can the four toys cross the bridge in time (that is, in 60 minutes) to be saved from Zurg?

Like the Haskell solution, the Ruby solution depends on a `SearchProblem` class which looks after the task of generating candidate solutions:

```SearchProblem = Struct.new(:initial) do
def each_candidate(&proc)
step [], initial, &proc
end

def step(history, state, &proc)
if state.terminal?
yield history
else
state.each_successor do |move, state|
step history + [move], state, &proc
end
end
end
end```

`SearchProblem` takes an initial `State` which provides two methods; `terminal?` returns true if the state is terminal (i.e. in our case, all the toys are on the right hand side of the bridge) and `each_successor` calls a block with each valid move from that state, together with the new state after that move.

`SearchProblem` provides an `each_candidate` method which calls the provided block with each candidate solution in turn. Crucially, candidate solutions are generated as needed, so we don’t have to hold the entire search tree in memory (not a big deal for a problem of this size, but definitely an issue for a “real world” problem!). The Haskell solution achieves a similar effect through lazy evaluation (contrast with this Erlang solution which does have to generate the entire search tree).

To define the particular problem at hand, we first define our `Toys`:

```Toy = Struct.new(:name, :time)
Toys = [
Toy.new(:buzz, 5),
Toy.new(:woody, 10),
Toy.new(:rex, 20),
Toy.new(:hamm, 25)]```

Next, we define `Move` which we will use to represent transitions between states. In this case, a move consists of a direction (right or left) and a group of toys (two toys for a move to the right, one toy for a move to the left):

```Move = Struct.new(:direction, :who) do
def cost
who.collect(&:time).max
end
end```

`Move` provides one method, `cost` which returns the time taken to complete the move (the implementation of which makes use of the `Symbol#to_proc` trick).

Most of the heavy lifting is performed by the `State` class:

```State = Struct.new(:pos, :group) do
def terminal?
group.empty?
end

def each_successor
case pos
when :left
group.each_pair do |pair|
yield Move.new(:right, pair), State.new(:right, group - pair)
end
when :right
(Toys - group).each do |toy|
yield Move.new(:left, [toy]), State.new(:left, group + [toy])
end
end
end
end```

A `State` comprises two attributes, `pos` which represents the current flashlight position and `group` which represents the toys remaining on the left-hand side of the bridge (so the toys on the right-hand side will be `Toys - group`).

The implementation of `State#terminal?` is obvious — if `group` is empty (i.e. if there are no toys on the left-hand side) then we’re done.

`State#each_successor` has to deal with two cases, depending on the position of the flashlight. The implementation utilises a small utility method on `Array` which allows all unique pairs of elements of the array to be generated:

```class Array
def each_pair
each_with_index do |x, i|
self[i + 1 ... length].each {|y| yield [x, y]}
end
end
end```

Finally, we create an instance of `SearchProblem` with our initial state and print out the first candidate solution we find in which the time taken is no more than 60 minutes:

```problem = SearchProblem.new State.new(:left, Toys)
puts problem.each_candidate {|history|
break history if history.inject(0) {|acc, move| acc + move.cost} <= 60
}```

As it happens (by sheer fluke) with the `Toys` array initialized in the natural order, the very first solution generated turns out to be the correct one, so the amount of work performed is the bare minimum. Clearly we can’t always rely on being so lucky in general, however!

To my mind, this solution is at least as easy to understand (and as flexible) as the Haskell equivalent (and both are a significant improvement on the Prolog). I would very much welcome comments and suggestions, however!

Update (2007-09-11)

8 Responses to “Escape from Zurg”

1. September 16, 2007 at 9:54 am

I recently bought “Rails for Java Developers” and “Haskell: The Craft of Functional Programming” for my holiday bookshelf. I’ve been in the Java monoculture for too long!

However, I’ve yet to see a more elegant solution in Ruby than in Java… might have a bash at doing this in Java to see if Ruby has some tricks that I missed.

2. September 16, 2007 at 10:24 am

Do let us know how you get on if you do, Sam. I did think about trying to come up with a Java (or C++) solution and decided that I didn’t want to do that kind of violence to my brain 🙂

Frankly, I’d be amazed if you can come up with anything even close to the succinctness and clarity of the Haskell or Ruby solutions in Java. But I’d love to be proven wrong!

3. September 20, 2007 at 4:30 pm

Hello! I’ve typed this and I’m getting a compile error when defining the “Move” struct, specifically on the line “who.collect(&:time).max”. It *does* look incorrect. If I change it to “who.collect{ |toy| toy.time }.max”, it works fine.

If it helps, I’m using Cygwin ruby 1.8.6. Maybe the syntax above is for some more recent version?

For those, like me, who are looking at this and can’t seem to figure it out by inspection, the correct series of moves is:

Woody and Buzz go right
Buzz goes left
Rex and Hamm go right
Woody goes left
Woody and Buzz go right

4. September 20, 2007 at 4:38 pm

Hey Noah,

The code is correct – you need to define Symbol#to_proc. The source code (and explaination of how it works) is available here. Or you can download the source of my solution (which includes the Symbol#to_proc trick) here.

5. September 20, 2007 at 10:23 pm

Ah! Sorry, I missed that bit. Makes sense.

6. October 13, 2007 at 9:27 pm

I’ve written up a Java implementation on the javablog. I tried to be as general as possible. Naturally it does work out to be somewhat more verbose than the Ruby or Haskell versions. I actually really like Haskell, although I’ve not quite got the hang of Monads yet.

1. 1 lojic.com » Blog Archive » Escape from Zurg Trackback on September 10, 2007 at 8:39 pm
2. 2 Javablog » Escape from Zurg Trackback on October 13, 2007 at 9:24 pm