CODEWITHSUNDEEP
listlogic-programminganswer-set-programmingclingo
Duda
Duda

Reputation: 3736

Riddle puzzle in clingo

So in the tag prolog someone wanted to solve the "the giant cat army riddle" by Dan Finkel (see video / Link for description of the puzzle).

Since I want to improve in answer set programming I hereby challenge you to solve the puzzle more efficient than me. You will find my solution as answer. I'll accept the fastest running answer (except if it's using dirty hacks).

Rules:

Upvotes: 0

Views: 417

Answers (2)

Max Ostrowski
Max Ostrowski

Reputation: 623

num(0..59).

%valid operation pairs
op(N*N,N):- N=2..7.  
% no need to add operations that start with 14
op(Ori,New):- num(Ori), New = Ori+7, num(New), Ori!=14.
op(Ori,New):- num(Ori), New = Ori+5, num(New), Ori!=14.

%iteratively create new numbers from old numbers
l(0,0).
{l(T+1,New) : op(Old,New)} = 1 :- l(T,Old), num(T+1), op(Old,_).

%no number twice
:- 2 #sum {1,T : l(T,Value)}, num(Value).

%2 before 10 before 14
%linear encoding
reached(T,10) :- l(T,10).
reached(T+1,10) :- reached(T,10), num(T+1).
:- reached(T,10), l(T,2).

:- l(T,14), l(T+1,_).

%looks nicer, but quadratic
%:- l(T2,2), l(T10,10), T10<T2.
%:- l(T14,14), l(T10,10), T14<T10.

%we must have these three numbers in the list somewhere
:- not l(_,2).
:- not l(_,10).
:- not l(_,14).

#show r(T,V) : l(T,V).
#show.

Having a slightly more ugly encoding improves grounding a lot (which was your main problem).

  1. I restricted op/2 to not start with 14, as this should be the last element in the list
  2. I do create the list iteratively, this may not be as nice, but at least for the start of the list it already removed impossible to reach values via grounding. So you will never have l(1,33) or l(2,45) etc... Also list generation stops when reaching the value 14, as no more operation is possible/needed.
  3. I also added a linear scaling version of the "before" section, although it is not really necessary for this short list (but a cool trick in general if you have long lists!) This is called "chaining".
  4. Also note that your show statement is non-trivial and does create some constraints/variables.

I hope this helps, otherwise feel free to ask such questions also on our potassco mailing list ;)

Upvotes: 1

Duda
Duda

Reputation: 3736

My first attempt is to generate a permutation of numbers and force successor elements to be connected by one of the 3 operations (+5, +7 or sqrt). I predefine the operations to avoid choosing/counting problems. Testing for <60 is not necessary since the output of an operation has to be a number between 0 and 59. The generated List l/2 is forwarded to the output r/2 until the number 14 appears. I guess there is plenty of room to outrun my solution.

num(0..59).

%valid operation pairs
op(N*N,N):- N=2..7.  
op(Ori,New):- num(Ori), New = Ori+7, num(New).
op(Ori,New):- num(Ori), New = Ori+5, num(New).

%for each position one number
l(0,0).
{l(T,N):num(N)}==1:-num(T).  
{l(T,N):num(T)}==1:-num(N).

% following numbers are connected with an operation until 14
:- l(T,Ori), not op(Ori,New), l(T+1,New), l(End,14), T+1<=End.

% 2 before 10 before 14
:- l(T2,2), l(T10,10), T10<T2.
:- l(T14,14), l(T10,10), T14<T10.

% output
r(T,E):- l(T,E), l(End,14), T<=End.
#show r/2.

first Answer:

r(0,0) r(1,5) r(2,12) r(3,19) r(4,26) r(5,31) r(6,36) r(7,6) 
r(8,11) r(9,16) r(10,4) r(11,2) r(12,9) r(13,3) r(14,10) r(15,15) 
r(16,20) r(17,25) r(18,30) r(19,37) r(20,42) r(21,49) r(22,7) r(23,14)

There are multiple possible lists with different length.

Upvotes: 0

Related Questions