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 << {
      :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 ]] }
    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 => [] })

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

This entry was posted on Monday, September 10th, 2007 at 3:38 pm and is filed under programming, ruby. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.