An observant mate of ours flashed this snap on a train from Cambridge to London - well done! The copy reads:

“Questions on any number of different lines.

Where in London can I learn to line dance?

What percentage of UK bank notes contain traces of cocaine?

Who played Johnny Cash in Walk the Line?”

Remember, we also answer train-related questions…

Astute readers may have noticed our new name, which underscores just how important our Texperts are to us. So we’re sharing them with the world! We’ve uploaded more Texpert profiles to our site so you can get to know the fab people behind the answers - the talent behind the texts!

Martin has answered over 35,000 questions and is into Capoeira. Sam has a PhD in something called intracellular signalling. And Ran is sometimes wakened by duck bills tapping on the windows of her riverboat in the dead of night while she dreams of the mysteries of the ancient world.

They’re an exceptional and friendly bunch this lot, which we’re always reminded of when we get together in Cambridge for our biannual office parties. The most recent one was great and I had a lovely time catching up over punting, bbq, and a few crafty ones in the Granta. A sunny day with familiar faces and new folks alike enjoying a good laugh and some good tunes - fantastic!

We plan to feature as many of our Texperts on our website as we can in the weeks and months ahead, so keep an eye out…

Here is the photo evidence from the Texperts office party! Shot on my trusty mobile (how “on-brand” is that??) here are some highlights of the great event.

Punting on the Cam - a perennial crowd-pleaser!

Then it was off to the fabulous Granta for a tasty BBQ. Giles looks well chuffed and Henry can’t wait to tuck in.

Bridget, Gary, and Chris enjoy erudite conversation and refreshing bevvies…

Clare, John, and Fred are clearly suspicious…

Deborah, Tim, and Sandy havin’ a ball…

Our print campaign has rolled out, and here are the results. City A.M. carries our front page ad copy, which grabbed the eyes of City Pro’s last week. Any thoughts on the new look? Let us know.

“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
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 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!

The complete source code can be downloaded here.

Update (2007-09-11)

There’s an interesting discussion about this problem on the ruby-talk mailing list.