Brian Adkins
9/10/2007 11:35:00 PM
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 }