# Escape from Zurg

::

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

The author blogged about 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.

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41``` ```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] < 0 else generate_states(state).each {|new_state| play_game new_state } end end play_game({ :minutes => 60, :source => [ :buzz, :woody, :rex, :hamm, :foo, :bar ], :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.

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43``` ```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 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] < 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 } ```