Escape from Zurg

:: programming, puzzle, ruby

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 }