Solving the Zurg puzzle in Ruby

Discussion in 'Ruby' started by Paul Butcher, Sep 9, 2007.

  1. Paul Butcher

    Paul Butcher Guest

    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/.
     
    Paul Butcher, Sep 9, 2007
    #1
    1. Advertising

  2. Paul Butcher

    Matthew Rudy Guest

    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

    --
    Posted via http://www.ruby-forum.com/.
     
    Matthew Rudy, Sep 9, 2007
    #2
    1. Advertising

  3. Paul Butcher

    Paul Butcher Guest

    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.
    --
    Posted via http://www.ruby-forum.com/.
     
    Paul Butcher, Sep 10, 2007
    #3
  4. On Sep 10, 10:57 am, Paul Butcher <> wrote:
    > 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.
    > --
    > 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, Sep 10, 2007
    #4
  5. Paul Butcher

    Paul Butcher Guest

    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.
    --
    Posted via http://www.ruby-forum.com/.
     
    Paul Butcher, Sep 10, 2007
    #5
  6. Paul Butcher

    Brian Adkins Guest

    On Sep 9, 4:08 am, Paul Butcher <> 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] + 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 }],
    :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, Sep 10, 2007
    #6
  7. Paul Butcher

    Brian Adkins Guest

    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] + 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 }],
    :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, Sep 11, 2007
    #7
  8. Paul Butcher

    Brian Adkins Guest

    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 Adkins, Sep 11, 2007
    #8
  9. Paul Butcher

    Paul Butcher Guest

    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.
    --
    Posted via http://www.ruby-forum.com/.
     
    Paul Butcher, Sep 11, 2007
    #9
  10. 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
    --
    Posted via http://www.ruby-forum.com/.
     
    Frederick Cheung, Sep 11, 2007
    #10
  11. Paul Butcher

    Paul Butcher Guest

    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
    --
    Posted via http://www.ruby-forum.com/.
     
    Paul Butcher, Sep 16, 2007
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Patrick

    Help in solving queries.......

    Patrick, Jan 26, 2005, in forum: ASP .Net
    Replies:
    5
    Views:
    587
    John Vinson
    Jan 27, 2005
  2. Keyvan Jamaleddin

    Error Solving

    Keyvan Jamaleddin, Jul 7, 2005, in forum: VHDL
    Replies:
    1
    Views:
    2,009
    Mike Treseler
    Jul 7, 2005
  3. nb
    Replies:
    0
    Views:
    493
  4. Lionel
    Replies:
    14
    Views:
    1,191
  5. Govinda Khanal

    help solving problem in ruby

    Govinda Khanal, Dec 10, 2009, in forum: Ruby
    Replies:
    6
    Views:
    83
    Steve Wilhelm
    Dec 10, 2009
Loading...

Share This Page