Lojic Technologies

Escape from Zurg

with 3 comments

I came across a little programming puzzle on comp.lang.ruby.

The author blogged about it here – nice solution. He refers to the original paper that got things started, but I haven’t had time to read it in depth yet.

I thought I’d try something a little different. I was going for simple and came up with a 3 function solution using just hashes and arrays. It’s not very general except for the handy combinations(array, n) function I wrote, and it certainly doesn’t feel Rubyish, but it was fun.

Something tells me that Lisp can handle this nicely, so I’ll probably write a Lisp version later.

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 < 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]  60,
  :source => [ :buzz, :woody, :rex, :hamm ],
  :destination => [],
  :position => :forward,
  :history => [] })

UPDATE: Something didn’t quite feel right about my first solution, so I took a second look at the op’s solution and decided I liked his use of Ruby blocks. They add some flexibility and efficiency in this case. Instead of computing a full array of possible states at each level of recursion (not as bad as precomputing the entire tree, but still not good), the new solution does a depth first search via block yields. I also removed the hardcoded print statement in play_game and yield the solution to the caller’s block to do with as they please.

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 < 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
  combinations(*(
    forward = state[:position] == :forward) ?
    [state[:source], 2] :
    [state[:destination], 1]).each {|movers| yield execute_move(state, forward, movers) }
end

def play_game state, &b
  if state[:source].empty?
    yield(state[:history]) unless state[:minutes]  60,
  :source => [ :buzz, :woody, :rex, :hamm ],
  :destination => [],
  :position => :forward,
  :history => [] }) {|history| pp history }

Written by Brian Adkins

September 10, 2007 at 3:38 pm

Posted in programming

Tagged with , ,

3 Responses

Subscribe to comments with RSS.

  1. It looks like the more functional approach has side benefits. I timed the op’s code and mine, and mine took ~32s vs. ~116 for the op’s. I don’t have time to analyze the difference, but I posted a note on comp.lang.ruby with profile output in case anyone feels like analyzing it.

    Brian Adkins

    September 10, 2007 at 8:11 pm

  2. Thanks! I found this on Google searching for a Ruby combinations algorithm (it’s built into the Array class on Ruby 1.8.7, but I’m limited to Ruby 1.8.6).

    Colin Jones

    July 25, 2008 at 1:13 pm

  3. Brian, I gave this a try in Clojure. You can see my solution over here: http://scott.andstuff.org/ClojureSpikes.

    Scott Moonen

    August 8, 2009 at 2:36 pm


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: