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

11–20 of 31 posts

Re: Solving a Dungeons and Dragons riddle using Prolog

#11

Post by Jtsummers »

mLuby wrote: post #9
Jtsummers wrote: post #7

Earlier quoted context omitted.

FYI, you can abbreviate some of that: Vixen -> Rudolph; Vixen -> Prancer; Vixen -> Dasher; Is equivalent to: Vixen -> {Rudolph Prancer Dasher} You can also do: {Comet Dancer} -> Vixen -> {Rudolph Prancer Dasher} Very nice when dealing with larger graphs.

Oh cool, didn't know it could do that so easily. GraphViz is really something.

I spent a lot of time with it a few years back developing some documentation. I had actually forgotten the correct syntax and had to look it up. It was a lot of fun to use, though.

I should probably brush up on it a bit and maybe use it for some crap we have at work that's incomprehensible ("What calls what again? Does anyone know? And it's a bespoke language so there is no tooling to help? Shit.")

Re: Solving a Dungeons and Dragons riddle using Prolog

#12

Post by _xgw »

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 solution! If I understand correctly, we're graphing the sequence of reindeer and then extracting the order of the nodes in the graph?

Re: Solving a Dungeons and Dragons riddle using Prolog

#13

Post by tannhaeuser »

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…

Putting OP's and your clauses together, I get the following pure ISO Prolog program and query that you can paste directly into Quantum Prolog's in-browser execution console at https://quantumprolog.sgml.io/browser-demo/browser-demo.html for execution in no time:

    % Vixen should be behind Rudolph,
    % Prancer and Dasher,
    is_behind(vixen, rudolph).
    is_behind(vixen, prancer).
    is_behind(vixen, dasher).

    % whilst Vixen should be in front
    % of Dancer and Comet.
    is_behind(dancer, vixen).
    is_behind(comet, vixen).

    % Dancer should be behind Donder,
    % Blitzen and Rudolph.
    is_behind(dancer, donder).
    is_behind(dancer, blitzen).
    is_behind(dancer, rudolph).

    % Comet should be behind Cupid,
    % Prancer and Rudolph.
    is_behind(comet, cupid).
    is_behind(comet, prancer).
    is_behind(comet, rudolph).

    % Donder should be behind Comet,
    % Vixen, Dasher, Prancer and
    % Cupid.
    is_behind(donder, comet).
    is_behind(fonder, vixen).
    is_behind(donder, dasher).
    is_behind(donder, prancer).
    is_behind(donder, cupid).

    % Cupid should be in front of
    % Comet, Blitzen, Vixen, Dancer
    % and Rudolph.
    is_behind(comet, cupid).
    is_behind(blitzen, cupid).
    is_behind(vixen, cupid).
    is_behind(dancer, cupid).
    is_behind(rudolph, cupid).

    % Prancer should be in front of
    % Blitzen, Donder and Cupid.
    is_behind(blitzen, prancer).
    is_behind(donder, prancer).
    is_behind(cupid, prancer).

    % Blitzen should be behind Cupid
    % but in front of Dancer, Vixen
    % and Donder.
    is_behind(blitzen, cupid).
    is_behind(dancer, blitzen).
    is_behind(vixen, blitzen).
    is_behind(donder, blitzen).

    % Rudolph should be behind Prancer
    % but in front of Dasher, Dancer
    % and Donder.
    is_behind(rudolph, prancer).
    is_behind(dasher, rudolph).
    is_behind(dancer, rudolph).
    is_behind(donder, rudolph).

    % Finally, Dasher should be behind
    % Prancer but in front of Blitzen,
    % Dancer and Vixen.
    is_behind(dasher, prancer).
    is_behind(blitzen, dasher).
    is_behind(dancer, dasher).
    is_behind(vixen, dasher).

    follows(Last, First) :-
      is_behind(Last, First).
    follows(Last, First) :-
      is_behind(Middle, First),
      follows(Last, Middle).

    order([]).
    order([_]).
    order([X,Y|L]) :-
        follows(Y, X), order([Y|L]).

    ?- order([A,B,C,D,E,F,G,H,I])

Re: Solving a Dungeons and Dragons riddle using Prolog

#14

Post by tbensky »

owenmarshall wrote: post #3
triska wrote: post #2

Very nice! This solution uses the library predicate list_to_set/2, relating a (known) list Ls0 of elements to a list Ls without duplicates , where the elements occur in the same order in which they first appear in Ls0. I think it is interesting to consider how such a relation can be described in Prolog, and also how efficient it can be. An immediate solution suggests itself, considering the elements of Ls0 in the ord…

I wanted to swing by with two notes. First, for those who don’t recognize the username, this post was from Markus Triska, whose homepage (metalevel.at) is an absolute wealth of knowledge on Prolog. I’ve learned so much from it. Second, for Markus: thank you :-)

I also would like to echo the thank you to Markus. His Power of Prolog videos have taught me so much about Prolog. His recent one on DCGs is incredibly eye-opening.

Re: Solving a Dungeons and Dragons riddle using Prolog

#15

Post by SloopJon »

I got the solution with a straightforward set of assertions in Z3. It was a lot of typing, and I wonder if there's a more succinct way to do this than the following:

    (declare-const blitzen Int)
    (declare-const comet Int)
    ...
    (assert
      (and
        ; lower bound for readability (1 is front)
        (> blitzen 0)
        (> comet 0)
        ...
        ; upper bound for readability (9 is rear)
        ( vixen rudolph)
        ...
        (

Re: Solving a Dungeons and Dragons riddle using Prolog

#17

Post by IncRnd »

While it's not quite the same, we can create a short makefile.

  vixen: rudolph prancer dasher cupid blitzen
   echo vixen

  dancer : vixen donder blitzen rudolph cupid dasher
   echo dancer

  comet: vixen cupid prancer rudolph
   echo comet

  donder: comet vixen dasher prancer cupid blitzen rudolph
   echo donder

  cupid: prancer
   echo cupid

  blitzen: cupid dasher
   echo blitzen

  rudolph: cupid prancer
   echo rudolph

  dasher: rudolph prancer
   echo dasher

  prancer: ;
   echo prancer

  order: vixen dancer comet donder cupid blitzen rudolph dasher prancer
   echo Get in Line
Then: make -n order

outputs:

  echo prancer
  echo cupid
  echo rudolph
  echo dasher
  echo blitzen
  echo vixen
  echo comet
  echo donder
  echo dancer
  echo Get in Line
Which, for me, is:

  real 0m0.015s
  user 0m0.003s
  sys 0m0.006s

Re: Solving a Dungeons and Dragons riddle using Prolog

#18

Post by Guthur »

tbensky wrote: post #14
owenmarshall wrote: post #3

Earlier quoted context omitted.

I wanted to swing by with two notes. First, for those who don’t recognize the username, this post was from Markus Triska, whose homepage (metalevel.at) is an absolute wealth of knowledge on Prolog. I’ve learned so much from it. Second, for Markus: thank you :-)

I also would like to echo the thank you to Markus. His Power of Prolog videos have taught me so much about Prolog. His recent one on DCGs is incredibly eye-opening.

Echoing the echo :)

Thanks Markus.

Re: Solving a Dungeons and Dragons riddle using Prolog

#19

Post by tkanarsky »

_xgw wrote: post #8
mLuby wrote: post #6

Very nice. I just solved it with GraphViz: https://gist.github.com/mLuby/d184c08c507fa03292c72acb38a146...

That's super interesting! I like how straightforward the solution is. The problem almost fades away! :)

That's because fundamentally it's a topological sort problem, and it seems like graphviz sorts the nodes appropriately before drawing the digraph.

Re: Solving a Dungeons and Dragons riddle using Prolog

#20

Post by Labo333 »

From a more algorithmic point of view, this is exactly the task of topological sorting [1].

And it runs linearly in the number of edges!

I expect Prolog to be slower for large and hard inputs. But Makefiles solve exactly that!

[1]: https://en.m.wikipedia.org/wiki/Topological_sorting

Post reply on HN