Ruby Forum Ruby > Solving the Zurg puzzle in Ruby

I recently got distracted by the Escape from Zurg puzzle - a problem
which has been used to teach students logic programming. I started
wondering whether I could come up with a nice solution in Ruby.

The solution that I've come up with is (I think - you may think
otherwise :-) very nice indeed, and is a good demonstration of the power
and flexibility of Ruby.

Anyway - I've blogged about it here:

http://www.texperts.com/2007/09/09/escape-from-zurg/

I'd be very interested to hear your comments!

Paul

Paul Butcher wrote:
> I recently got distracted by the Escape from Zurg puzzle - a problem
> which has been used to teach students logic programming. I started
> wondering whether I could come up with a nice solution in Ruby.
> 
> The solution that I've come up with is (I think - you may think
> otherwise :-) very nice indeed, and is a good demonstration of the power
> and flexibility of Ruby.

yeah,
that's pretty nice Paul.

I do like passing a block to Struct.new,
never thought about that before, but it makes sense.

State = Struct.new(:pos, :group) do
  *blah*
end

http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/267494

Matthew Rudy wrote:
> yeah,
> that's pretty nice Paul.

Thanks Matthew :-) The thing that impressed me was that what felt like a 
very "natural" Ruby implementation (not using anything tricky or 
obscure) ended up being (in my opinion) just as concise and efficient as 
the Haskell solution which intimately relies on lazy evaluation to 
achieve its efficiency.

> I do like passing a block to Struct.new,
> never thought about that before, but it makes sense.

Something that I discovered as I was thinking about this problem, in 
fact!

Cheers!

Paul.

On Sep 10, 10:57 am, Paul Butcher <p...@82ask.com> wrote:
> > I do like passing a block to Struct.new,
> > never thought about that before, but it makes sense.
>
> Something that I discovered as I was thinking about this problem, in
> fact!
>
> Cheers!
>
> Paul.
> --
> Posted viahttp://www.ruby-forum.com/.

I agree, a very nice solution.  The one aspect you missed out on is
the possibility to truncate your search based on cumulative cost.  For
example,

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

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

# ...

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

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

# ...

problem = SearchProblem.new(State.new(:left, Toys, 0), 60)
problem.each_candidate {|history, cost|
  p history, cost
}


Like you said, since your first solution generated is valid, it's not
terribly important in this specific case, but in general, it's good to
truncate early.
Your original code generates all 108 ( 4c2 * 2c1 * 3c2 * 3c1 * 2c2 = 6
* 2 * 3 * 3 * 1 = 108) candidates, but many of those candidates can be
ruled out
before examining the full history.

For example:
if Rex & Ham go over (25 minutes)
and Ham comes back (25 minutes)
then Ham & Buzz go over (25 minutes)
we've already exceeded our max cost, and we don't need to examine any
of the solution tree that starts with that pattern.
In this case, it cuts out 3 possibilities.  In a more general case, it
may cut out more.

Altering the code as above yields only the 2 allowable cost solutions,
on which you can do whatever checking you wished.

For more elaborate problems, you could also introduce a partial
solution check criterion (possibly passed in a block) rather than the
simple cost comparison.

Cool problem.  Nice solution.

Noah Easterly wrote:
>  The one aspect you missed out on is
> the possibility to truncate your search based on cumulative cost. 

Ah - of course! That makes perfect sense. Thanks Noah.

Paul.

On Sep 9, 4:08 am, Paul Butcher <p...@82ask.com> wrote:
> I recently got distracted by the Escape from Zurg puzzle

Yeah, thanks for distracting me too :) I'm too much of a sucker for
these things.

> Anyway - I've blogged about it here:
>
> http://www.texperts.com/2007/09/09/escape-from-zurg/

Nice solution. I gained some knowledge about Structs; I don't use them
often.

I've been looking into Lisp recently, so I thought I'd try a simpler
solution w/o Structs/Classes for fun. I learned something about the
advantages of functions over methods in some instances. If I had made
the combinations function a method of Array (I still love how Ruby
makes that easy), the generate_states function would've been more
awkward IMO. As a function, it's easier to compute the array argument
more dynamically.

require 'pp'
TOYS = { :buzz => 5, :woody => 10, :rex => 20, :hamm => 25 }

def combinations array, n
  result = []
  if n > 0
    (0 .. array.length - n).each do |i|
      combs = [[]] if (combs = combinations(array[i + 1 .. -1], n -
1)).empty?
      combs.collect {|comb| [array[i]] + comb}.each {|x| result << x}
    end
  end
  return result
end

def generate_states state
  forward = state[:position] == :forward
  args = forward ? [state[:source], 2] : [state[:destination], 1]
  combinations(*args).inject([]) do |states, movers|
    states << {
      :minutes => state[:minutes] - TOYS[movers.max {|a,b| TOYS[a] <=>
TOYS[b] }],
      :source => forward ? state[:source] - movers : state[:source] +
movers,
      :destination => forward ? state[:destination] + movers :
state[:destination] - movers,
      :position => forward ? :backward : :forward,
      :history => state[:history] + [[ state[:position], movers ]] }
    states
  end
end

def play_game state
  if state[:source].empty?
    pp(state[:history]) unless state[:minutes] < 0
  else
    generate_states(state).each {|new_state| play_game new_state }
  end
end

play_game({
  :minutes => 60,
  :source => [ :buzz, :woody, :rex, :hamm ],
  :destination => [],
  :position => :forward,
  :history => [] })

I reviewed Paul's solution again, and I like his use of blocks. My
first solution didn't compute the whole tree in advance, but it did
compute an array of states at each level of recursion. I redesigned it
to use blocks in a few places which should make it more efficient. I
also added a block to play_game instead of hardcoding the output
printing which makes it more flexible.

Ruby blocks are awesome :)

require 'pp'
TOYS = { :buzz => 5, :woody => 10, :rex => 20, :hamm => 25 }

def combinations array, n
  result = []
  if n > 0
    (0 .. array.length - n).each do |i|
      combs = [[]] if (combs = combinations(array[i + 1 .. -1], n -
1)).empty?
      combs.collect {|comb| [array[i]] + comb}.each {|x| result << x}
    end
  end
  result
end

def execute_move state, forward, movers
  { :minutes => state[:minutes] - TOYS[movers.max {|a,b| TOYS[a] <=>
TOYS[b] }],
    :source => forward ? state[:source] - movers : state[:source] +
movers,
    :destination => forward ? state[:destination] + movers :
state[:destination] - movers,
    :position => forward ? :backward : :forward,
    :history => state[:history] + [[ state[:position], movers ]] }
end

def each_state state
  forward = state[:position] == :forward
  args = forward ? [state[:source], 2] : [state[:destination], 1]
  combinations(*args).each {|movers| yield execute_move(state,
forward, movers) }
end

def play_game state, &b
  if state[:source].empty?
    yield(state[:history]) unless state[:minutes] < 0
  else
    each_state(state) {|new_state| play_game new_state, &b }
  end
end

play_game({
  :minutes => 60,
  :source => [ :buzz, :woody, :rex, :hamm ],
  :destination => [],
  :position => :forward,
  :history => [] }) {|history| pp history }

I was curious about efficiencies, so to stress the program a bit more,
I added two more 'toys':

:foo => 30, :bar => 35

With the additional toys, my original program took 32.2s, adding the
blocks/yields to avoid too much precomputation only brought it down to
31.9s. I tested Paul's original program and it took 116s.

None of the programs find a solution since I left the time at 60, and
none are pruning, so they compute the whole candidate space. I
wouldn't expect a ~4x difference between the solutions. If anyone has
insight from the code or profile output below, I would appreciate it.

Here's my profile output (top 10):

  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 16.94     6.27      6.27    11015     0.57     2.02  Range#each
 16.32    12.31      6.04    10230     0.59     1.12
Object#execute_move
 12.75    17.03      4.72    21245     0.22     1.33
Object#combinations
 11.05    21.12      4.09    31477     0.13     6.94  Array#each
  7.92    24.05      2.93    98813     0.03     0.03  Hash#[]
  6.73    26.54      2.49    10231     0.24    23.35  Object#play_game
  5.81    28.69      2.15    15334     0.14     0.19  Array#collect
  4.22    30.25      1.56     5911     0.26    39.85
Object#each_state
  2.86    31.31      1.06    36579     0.03     0.03  Fixnum#-
  2.59    32.27      0.96    36220     0.03     0.03  Array#+

Here's Paul's profile output (top 10):

  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 20.65    14.90     14.90    50276     0.30    15.62  Array#each
 11.99    23.55      8.65    30240     0.29     1.08  Move#cost
  8.08    29.38      5.83    30870     0.19     0.30  Struct#hash
  7.89    35.07      5.69    30240     0.19     0.38  Array#collect
  5.68    39.17      4.10    47520     0.09     0.12  Kernel.send
  4.88    42.69      3.52    30240     0.12     0.17  Symbol#to_proc
  4.60    46.01      3.32    92610     0.04     0.04  Kernel.hash
  4.34    49.14      3.13    30240     0.10     0.21  Enumerable.max
  3.85    51.92      2.78    10231     0.27    51.66
SearchProblem#step
  3.27    54.28      2.36     5911     0.40    81.93
State#each_successor

Brian,

I feel that I should apologise to you - I've clearly got you "hooked" 
and I'm sure that you have other things that you should be doing :-)

Brian Adkins wrote:
> I was curious about efficiencies ...
> 
> ... I
> wouldn't expect a ~4x difference between the solutions. If anyone has
> insight from the code or profile output below, I would appreciate it.

That's a very surprising result! I, too, would be interested in any 
light that anyone can cast on it.

Thanks Brian,

Paul.

Paul Butcher wrote:

> That's a very surprising result! I, too, would be interested in any 
> light that anyone can cast on it.
> 

Replacing

 def cost
   who.collect(&:time).max
 end

 with

 who.inject(0) { |current_max, toy| toy.time > current_max ? toy.time : 
current_max }

makes paul's solution run 5.5 times faster on my machine (in around 29 
seconds). Still slower than Brian's (which takes 24 seconds), but a 
difference of 20% or so is less surprising that multiples.

Cost is obviously called a lot, the intial version iterates over who 
once, creates a new array then iterates over it again to get the max. 
I'm guessing the creation of lots of garbage & the second iteration are 
the big factors.

Fred

Frederick Cheung wrote:
> Replacing
> 
>  def cost
>    who.collect(&:time).max
>  end
> 
>  with
> 
>  who.inject(0) { |current_max, toy| toy.time > current_max ? toy.time : 
> current_max }
> 
> makes paul's solution run 5.5 times faster on my machine (in around 29 
> seconds). Still slower than Brian's (which takes 24 seconds), but

And replacing it with:

who.max {|a, b| a.time <=> b.time}.time

(which is actually the way that I wrote it initially - but I thought 
that the solution using collect was clearer!) gets my solution and 
Brian's running in vitually identical times.

Paul