Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Solving a Dungeons and Dragons riddle using Prolog

gist.github.com

Post reply on HN
Print view View original

21–30 of 31 posts

Re: Solving a Dungeons and Dragons riddle using Prolog

#21

Post by YeGoblynQueenne »

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(
If you squint a bit you'll notice the polarity of "" 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.)

Re: Solving a Dungeons and Dragons riddle using Prolog

#22

Post by [deleted] »

colanderman wrote: post #10

You can do this without the intermediate step of generating all permutations simply like so: order([]). order([_]). order([X,Y|L]) :- follows(Y, X), order([Y|L]). ?- length(L, 9), order(L). L = [prancer, cupid, rudolph, dasher, blitzen, vixen, comet, donder, dancer] . This is likely more efficient as we're cutting short the generation of most permutations. Or you can use CPL(FD) as suggested by @Avshalom below, thoug…

[deleted]

Re: Solving a Dungeons and Dragons riddle using Prolog

#23

Post by soveran »

For an alternative solution, describe the directed graph by listing the nodes and using whitespace to represent the arcs:

  $ cat riddle
  Vixen Rudolph
  Vixen Prancer
  Vixen Dasher
  Dancer Vixen
  Comet Vixen
  ...
  Vixen Dasher
Then use tsort:

  $ tsort riddle
  Dancer
  Donder
  Comet
  Vixen
  Blitzen
  Dasher
  Rudolph
  Cupid
  Prancer

Re: Solving a Dungeons and Dragons riddle using Prolog

#24

Post by gpderetta »

soveran wrote: post #23

For an alternative solution, describe the directed graph by listing the nodes and using whitespace to represent the arcs: $ cat riddle Vixen Rudolph Vixen Prancer Vixen Dasher Dancer Vixen Comet Vixen ... Vixen Dasher Then use tsort: $ tsort riddle Dancer Donder Comet Vixen Blitzen Dasher Rudolph Cupid Prancer

Yep, I was wondering if this didn't just need a topological sort (as shown by the make solution elsethread).

Re: Solving a Dungeons and Dragons riddle using Prolog

#25

Post by kwon-young »

Prolog was made to parse text, so shouldn't we derive the constraints from the text itself with a DCG ?

  :- set_prolog_flag(double_quotes, codes).
  
  text("Vixen should be behind Rudolph, Prancer and Dasher, whilst Vixen should be in front of Dancer and Comet. Dancer should be behind Donder, Blitzen and Rudolph. Comet should be behind Cupid, Prancer and Rudolph. Donder should be behind Comet, Vixen, Dasher, Prancer and Cupid. Cupid should be in front of Comet, Blitzen, Vixen, Dancer and Rudolph. Prancer should be in front of Blitzen, Donder and Cupid. Blitzen should be behind Cupid but in front of Dancer, Vixen and Donder. Rudolph should be behind Prancer but in front of Dasher, Dancer and Donder. Finally, Dasher should be behind Prancer but in front of Blitzen, Dancer and Vixen.").
  
  space -->
     " ".
  
  reindeer('Blitzen') -->
     "Blitzen".
  reindeer('Comet') -->
     "Comet".
  reindeer('Cupid') -->
     "Cupid".
  reindeer('Dancer') -->
     "Dancer".
  reindeer('Dasher') -->
     "Dasher".
  reindeer('Donder') -->
     "Donder".
  reindeer('Prancer') -->
     "Prancer".
  reindeer('Rudolph') -->
     "Rudolph".
  reindeer('Vixen') -->
     "Vixen".
  
  complement(S, P, [[S, P, Reindeer] | R], R) -->
     reindeer(Reindeer).
  
  sep -->
     ", ".
  sep -->
     " and ".
  
  list(Pred, Sep, S1, S3) -->
     call(Pred, S1, S2),
     list_next(Pred, Sep, S2, S3).
  list_next(Pred, Sep, S1, S3) -->
     Sep,
     call(Pred, S1, S2),
     list_next(Pred, Sep, S2, S3).
  list_next(_, _, S, S) -->
     [].
  
  position(>) -->
     "behind".
  position(
     "in front of".
  
  text(S) -->
     list(proposition, space, S, S2),
     space,
     last_sentence(S2, []).
  
  last_sentence(S1, S2) -->
     "Finally, ",
     proposition(S1, S2).
  
  proposition(S1, S3) -->
     proposition(R, S1, S2),
     inverse_proposition(R, S2, S3),
     ".".
  
  proposition(R, S1, S2) -->
     reindeer(R),
     " should be ",
     position_list(R, S1, S2).
  
  position_list(R, S1, S2) -->
     position(P),
     space,
     list(complement(R, P), sep, S1, S2).
  
  inverse_proposition(R, S1, S2) -->
     " but ",
     position_list(R, S1, S2).
  inverse_proposition(R, S1, S2) -->
     ", whilst ",
     proposition(R, S1, S2).
  inverse_proposition(_, S, S) -->
     [].
  
  :- table(follows/3).
  
  follows(R1, R2, Pairs) :-
     member([R1, >, R2], Pairs).
  follows(R1, R2, Pairs) :-
     member([R2,
And we can solve the riddle with:

  ?- text(T), phrase(text(Pairs), T), length(L, 9), order(L, Pairs).
  T = [86, 105, 120, 101, 110, 32, 115, 104, 111|...],
  Pairs = [['Vixen', >, 'Rudolph'], ['Vixen', >, 'Prancer'], ['Vixen', >, 'Dasher'], ['Vixen', , 'Donder'], ['Dancer', >|...], ['Dancer'|...]
  , [...|...]|...],
  L = ['Prancer', 'Cupid', 'Rudolph', 'Dasher', 'Blitzen', 'Vixen', 'Comet', 'Donder', 'Dancer']
One nice thing we can do with this grammar is that we can also generate the text from a list of constraints:

  ?- Pairs = [['Prancer',

Re: Solving a Dungeons and Dragons riddle using Prolog

#26

Post by colanderman »

_xgw wrote: post #12
colanderman wrote: post #10

You can do this without the intermediate step of generating all permutations simply like so: order([]). order([_]). order([X,Y|L]) :- follows(Y, X), order([Y|L]). ?- length(L, 9), order(L). L = [prancer, cupid, rudolph, dasher, blitzen, vixen, comet, donder, dancer] . This is likely more efficient as we're cutting short the generation of most permutations. Or you can use CPL(FD) as suggested by @Avshalom below, thoug…

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 solut…

No, `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] .

Re: Solving a Dungeons and Dragons riddle using Prolog

#27

Post by tbensky »

Avshalom wrote: post #5

Now I immediately turned to library(clpfd). Something along the lines of: Names = [rudolph, dancer... Vars = [Rudolph, Dancer... Vars ins 1..9, all_different(Vars), Rudolph #> Dancer, ... ... pairs_keys_values(P,Vars,Names), keysort(P,S), write(S).

I like the clpfd approach too:

:- use_module(library(clpfd)).

go(L) :- L = [Vixen, Rudolph, Prancer, Dasher, Comet, Dancer, Donder, Blitzen, Cupid], L ins 1..9,

        % Vixen should be behind Rudolph, Prancer and Dasher,
        maplist(#>(Vixen),[Rudolph,Prancer,Dasher]),
        
        %  Vixen should be in front of Dancer and Comet.
        maplist(#(Dancer),[Donder,Blitzen,Rudolph]),
        
        % Comet should be behind Cupid, Prancer and Rudolph.
        maplist(#>(Comet),[Cupid,Prancer,Rudolph]),

        % Donder should be behind Comet, Vixen, Dasher, Prancer and Cupid. 
        maplist(#>(Donder),[Comet, Vixen, Dasher, Prancer,Cupid]),

        % Cupid should be in front of Comet, Blitzen, Vixen, Dancer and Rudolph
        maplist(# Cupid,

        % but in front of Dancer, Vixen and Donder.
        maplist(# Prancer,
        
        % but in front of Dasher, Dancer and Donder.
        maplist(# Prancer,

        % but in front of Blitzen, Dancer and Vixen.
        maplist(#

Re: Solving a Dungeons and Dragons riddle using Prolog

#28

Post by eklitzke »

YeGoblynQueenne wrote: post #21

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 orde…

Sorting a list of N items in less than O(N) time would be quite a trick.

Re: Solving a Dungeons and Dragons riddle using Prolog

#29

Post by YeGoblynQueenne »

eklitzke wrote: post #28
YeGoblynQueenne wrote: post #21

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 orde…

Sorting a list of N items in less than O(N) time would be quite a trick.

Meh. Don't know where that came from, sorry.
Post reply on HN