On Sep 10, 10:57 am, Paul Butcher <p... / 82ask.com> wrote:
> Matthew Rudy wrote:
> > yeah,
> > that's pretty nice Paul.
>
> Thanks Matthew :-) The thing that impressed me was that what felt like a
> very "natural" Ruby implementation (not using anything tricky or
> obscure) ended up being (in my opinion) just as concise and efficient as
> the Haskell solution which intimately relies on lazy evaluation to
> achieve its efficiency.
>
> > I do like passing a block to Struct.new,
> > never thought about that before, but it makes sense.
>
> Something that I discovered as I was thinking about this problem, in
> fact!
>
> Cheers!
>
> Paul.
> --
> Posted viahttp://www.ruby-forum.com/.

I agree, a very nice solution.  The one aspect you missed out on is
the possibility to truncate your search based on cumulative cost.  For
example,

SearchProblem = Struct.new(:initial, :max_cost) do
  def each_candidate(&proc)
    step [], initial, &proc
  end

  def step(history, state, &proc)
    return if state.cost > max_cost
    if state.terminal?
      yield history, state.cost
    else
      state.each_successor do |move, state|
        step history + [move], state, &proc
      end
    end
  end
end

# ...

State = Struct.new(:pos, :group, :cost) do
  def terminal?
    group.empty?
  end

  def each_successor
    case pos
      when :left
        group.each_pair do |pair|
          move = Move.new(:right, pair)
          yield move, State.new(:right, group - pair, cost +
move.cost)
        end
      when :right
        (Toys - group).each do |toy|
          move = Move.new(:left, [toy])
          yield move, State.new(:left, group + [toy], cost +
move.cost)
        end
    end
  end
end

# ...

problem = SearchProblem.new(State.new(:left, Toys, 0), 60)
problem.each_candidate {|history, cost|
  p history, cost
}


Like you said, since your first solution generated is valid, it's not
terribly important in this specific case, but in general, it's good to
truncate early.
Your original code generates all 108 ( 4c2 * 2c1 * 3c2 * 3c1 * 2c2 = 6
* 2 * 3 * 3 * 1 = 108) candidates, but many of those candidates can be
ruled out
before examining the full history.

For example:
if Rex & Ham go over (25 minutes)
and Ham comes back (25 minutes)
then Ham & Buzz go over (25 minutes)
we've already exceeded our max cost, and we don't need to examine any
of the solution tree that starts with that pattern.
In this case, it cuts out 3 possibilities.  In a more general case, it
may cut out more.

Altering the code as above yields only the 2 allowable cost solutions,
on which you can do whatever checking you wished.

For more elaborate problems, you could also introduce a partial
solution check criterion (possibly passed in a block) rather than the
simple cost comparison.

Cool problem.  Nice solution.