From: Brian Adkins <lojicdotcom@...>
Date: 2007-09-11T08:40:05+09:00
Subject: Re: Solving the Zurg puzzle in Ruby

I reviewed Paul's solution again, and I like his use of blocks. My
first solution didn't compute the whole tree in advance, but it did
compute an array of states at each level of recursion. I redesigned it
to use blocks in a few places which should make it more efficient. I
also added a block to play_game instead of hardcoding the output
printing which makes it more flexible.

Ruby blocks are awesome :)

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
  forward = state[:position] == :forward
  args = forward ? [state[:source], 2] : [state[:destination], 1]
  combinations(*args).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 }