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.
Something that I discovered as I was thinking about this problem, in
fact!
Cheers!
Paul.
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.