|
The raindeer in the riddle are in a total ordering, with each following one
other, like a linked list. That means we can just... sort them. We could do that by hand-rolling a sorting algorithm with a custom comparison.
Or, if we want to leave time for breakfast, there's SWI-Prolog's predsort/3 that
takes as an argument a custom ordering predicate, and then sorts a list of
arbitrary Prolog terms according to that ordering. For example, I define raindeer_order/2 as an ordering predicate, reusing
follows/2 from the article above, like this: raindeer_order(>,R1,R2):-
once(follows(R1,R2)).
raindeer_order(<,R1,R2):-
once(follows(R2,R1)).
raindeer_order(=,R,R).
If you squint a bit you'll notice the polarity of "<" and ">" is inverted.
That's because follows/2 is an inverse order.Now we can find all the raindeer and sort them: ordered_raindeer(Rs_):-
setof(R1
,R2^( is_behind(R1,R2)
; is_behind(R2,R1)
)
,Rs)
,predsort(raindeer_order,Rs,Rs_).
And, at the command line: ?- ordered_raindeer(Rs).
Rs = [prancer, cupid, rudolph, dasher, blitzen, vixen, comet, donder, dancer] ;
false.
Runs in O(log(n)) :P(Edit: I think it's n log n actually: follows/2 might have to run the length of the list to compare two reindeer.) |