6 ms·
Ah, interesting! I figured there would be a way without having to "brute-force" the solution by using the `permutation` predicate but I wasn't able to come up w
by _xgw 4y ago
Ah, interesting! I figured there would be a way without having to "brute-force" the solution by using the `permutation` predicate but I wasn't able to come up with one. I wonder if there's a way of not depending on permutation generation, nor list length. Does querying with `order(L)` require `length(L, 9)` to work?
As for the topological sort solution, I assume it's what Graphviz uses under the hood in mLuby's solution! If I understand correctly, we're graphing the sequence of reindeer and then extracting the order of the nodes in the graph?
- colanderman 4y agoNo, `order/1` generates "too-short" solutions otherwise. If you redefine `order/1` to be a little smarter, like so: order([]) :- \+ follows(_, _). order([X]) :- \+ follows(_, X). order([X,Y|L]) :- follows(Y, X), order([Y|L]). Then this works without knowing the length a priori, but it's less efficient: ?- order(L), forall((is_behind(X, _); is_behind(_, X)), member(X, L)). L = [prancer, cupid, rudolph, dasher, blitzen, vixen, comet, donder, dancer] . Instead I'd discover the set of names (and therefore list length) using `setof/3`; this is similarly efficient to my original solution: ?- setof(X, Y^(is_behind(X, Y); is_behind(Y, X)), M), length(M, N), length(L, N), order(L). M = [blitzen, comet, cupid, dancer, dasher, donder, prancer, rudolph, vixen], N = 9, L = [prancer, cupid, rudolph, dasher, blitzen, vixen, comet, donder, dancer] .