# Lojic Technologies

## Escape from Zurg

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 }
```

September 10, 2007 at 3:38 pm

Posted in programming

Tagged with , ,

### 3 Responses

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.

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