Solving the Zurg puzzle in Ruby

[Paul Butcher]

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
--
Posted via http://www.ruby-forum.com/.

[Matthew Rudy]

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

[Paul Butcher]

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.

[Noah Easterly]

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.

[Paul Butcher]

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.

[Brian Adkins]

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 => [] })

[Brian Adkins]

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 }

[Brian Adkins]

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

[Paul Butcher]

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.

[Frederick Cheung]

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

[Paul Butcher]

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