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

On Sep 9, 4:08 am, Paul Butcher <p...@82ask.com> wrote:
> I recently got distracted by the Escape from Zurg puzzle

Yeah, thanks for distracting me too :) I'm too much of a sucker for
these things.

> Anyway - I've blogged about it here:
>
> http://www.texperts.com/2007/09/09/escape-from-zurg/

Nice solution. I gained some knowledge about Structs; I don't use them
often.

I've been looking into Lisp recently, so I thought I'd try a simpler
solution w/o Structs/Classes for fun. I learned something about the
advantages of functions over methods in some instances. If I had made
the combinations function a method of Array (I still love how Ruby
makes that easy), the generate_states function would've been more
awkward IMO. As a function, it's easier to compute the array argument
more dynamically.

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