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.
···
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/.
very nice indeed, and is a good demonstration of the power