Main page: http://www.cs.kuleuven.be/~toms/PPC16/.
Problem Specification: probs.pdf
%%%%%%%%%%%%%begin%%%%%%%%%%%%%
Name(s): Paul Fodor, Beata Sarna-Starosta
Affiliations: State University of New York at Stony Brook, LogicBox
Prolog system used: XSB
%%%%%%%%%%%%%flag.pl%%%%%%%%%%%%
flag(N):-
flag1,
flag2(N),
flag3,
!.
flag1:-
write(' -'), nl,
write(' (_)'), nl,
write('<___>'), nl.
flag3:-
write_beginning, nl.
flag2(1):-
write_beginning, write('_____'), nl,
write_beginning, write(' |'), nl,
write_beginning, write(' |'), nl,
write_beginning, write(' |'), nl,
write_beginning, write('~~~~~'), nl.
flag2(2):-
write_beginning, write('_____'), nl,
write_beginning, write(' )'), nl,
write_beginning, write(' (_____'), nl,
write_beginning, write(' | |'), nl,
write_beginning, write('~~~~| |'), nl,
write_beginning, write(' | |'), nl,
write_beginning, write(' ~~~~~~'), nl.
flag2(N):-
write_beginning, write('_____'), nl,
write_beginning, write(' )'), nl,
write_beginning, write(' (_____'), nl,
write_beginning, write(' | )'), nl,
write_beginning, write('~~~~| (_____'), nl,
( N=3 ->
(write_beginning, write(' | | |'), nl);
(write_beginning, write(' | | )'), nl)
),
for(I,3,N),
Shift is I-3,
flag2_1(N,I,Shift),
fail.
flag2(_).
flag2_1(N,N,Shift):-
write_beginning, writeN(4,' '), write_shift(Shift), write('~~~~~| |'), nl,
write_beginning, writeN(4,' '), write_shift(Shift), write(' | |'), nl,
write_beginning, writeN(4,' '), write_shift(Shift), write(' ~~~~~~'), nl,
!.
flag2_1(N,I,Shift):-
N1 is N-1,
I=N1,
write_beginning, writeN(4,' '), write_shift(Shift), write('~~~~~| (_____'), nl,
write_beginning, writeN(4,' '), write_shift(Shift), write(' | | |'), nl,
!.
flag2_1(_,_,Shift):-
write_beginning, writeN(4,' '), write_shift(Shift), write('~~~~~| (_____'), nl,
write_beginning, writeN(4,' '), write_shift(Shift), write(' | | )'), nl,
!.
for(I,I,J):- I =< J.
for(K,I,J):- I < J,
I1 is I + 1,
for(K,I1,J).
writeN(N,C):-
N > 0,
M is N -1,
write(C),
writeN(M,C),
!.
writeN(_N,_C).
write_beginning:-
write(' | |').
write_shift(Shift):-
for(_I,1,Shift),
writeN(5,' '),
fail.
write_shift(_).
%%%%%%%%%%%%%split.pl%%%%%%%%%%%%
split(Large,Small1,Small2,How):-
findall( f(How1,Count1), split1(Large,Small1,Small2,How1,Count1), L),
L=[f(How2,Count2)|T],
min(How2,Count2,T,How).
min(How,_Count2,[],How):-
!.
min(_How2,Count2,[f(How3,Count3)|T],How):-
Count3 < Count2,
min(How3,Count3,T,How),
!.
min(How2,Count2,[_|T],How):-
min(How2,Count2,T,How),
!.
split1(Large,Small1,Small2,How,Count):-
split2(Large,Small1,Small2,How),
How = [H|T],
count_changes(T,Count,H,1).
count_changes([],N,_,N):-
!.
count_changes([H|T],Count,H,N):-
count_changes(T,Count,H,N),
!.
count_changes([H2|T],Count,_,N):-
N1 is N+1,
count_changes(T,Count,H2,N1),
!.
split2([],[],[],[]):-
!.
split2([H|T],[H|T1],L2,[1|RT]):-
split2(T,T1,L2,RT).
split2([H|T],L1,[H|T2],[2|RT]):-
split2(T,L1,T2,RT).
%%%%%%%%%%%%%panoz.pl%%%%%%%%%%%%
panoz(Outlets,Sol) :- solveX(Outlets,X), solveY(Outlets,Y), Sol=(X,Y).
solveX(Outlets,X) :- minX(Outlets,MinX), maxX(Outlets,MaxX), Sum is MinX+MaxX, X is Sum//2.
minX([(X,_)],X):-
!.
minX([(X,_)|Xs],Min) :- minX(Xs,Min1), (Min1 =< X -> Min=Min1 ; Min=X).
maxX([(X,_)],X):-
!.
maxX([(X,_)|Xs],Max) :- maxX(Xs,Max1), (Max1>=X -> Max=Max1 ; Max=X).
solveY(Outlets,Y) :- minY(Outlets,MinY), maxY(Outlets,MaxY), Sum is MinY+MaxY, Y is Sum//2.
minY([(_,Y)],Y):-
!.
minY([(_,Y)|Ys],Min) :- minY(Ys,Min1), (Min1 =< Y -> Min=Min1 ; Min=Y).
maxY([(_,Y)],Y):-
!.
maxY([(_,Y)|Ys],Max) :- maxY(Ys,Max1), (Max1 >= Y -> Max=Max1 ; Max=Y).
%%%%%%%%%%%%%circ.pl%%%%%%%%%%%%
circ(G,Three,Length):- findall( f(Three1,Length1), threeDist(Three1,G,Length1), L), L=[f(Three2,Length2)|T], max(Three2,Length2,T,Three,Length), !.
dist(X,Y,G,Length):- reach(X,Y,G,[X],Path), myLength(Path,Length1), Length is Length1-1.
threeDist([X,Y,Z],G,D):- node(X,G), node(Y,G), X\=Y, node(Z,G), Z\=Y, Z\=X, threeDist1([X,Y,Z],G,D).
threeDist1([X,Y,Z],G,D):- dist(X,Y,G,D1), dist(Y,Z,G,D2), dist(X,Z,G,D3), D is D1+D2+D3.
node(X,G):- member(edge(X,_),G).
node(X,G):- member(edge(_,X),G).
max(Three,Length,[],Three,Length):-
!.
max(_,PLength,[f(Three1,Length1)|T],Three,Length):-
PLength < Length1,
max(Three1,Length1,T,Three,Length),
!.
max(PThree,PLength,[_|T],Three,Length):-
max(PThree,PLength,T,Three,Length).
% reachability reach and path computation with tabling
% reach/4
% reach(+X,+Y,+Graph,-Path)
% reach(a,z,[edge(a,b), edge(b,a), edge(b,z)],P).
% reach(a,Y,[edge(a,b), edge(b,a), edge(b,z)],P).
% reach(X,Y,[edge(a,b), edge(b,a), edge(b,z)],P).
% findall(P,reach(X,Y,[edge(a,b), edge(b,a), edge(b,z)],P),L).
reach(X,Y,G,Partial,[X,Y]):-
\+ (member(Y,Partial)),
member(edge(X,Y),G),
!.
reach(X,Y,G,Partial,[X,Y]):-
\+ (member(Y,Partial)),
member(edge(Y,X),G),
!.
reach(X,Y,G,Partial,Path):-
\+ (member(Y,Partial)),
member(edge(X,Z),G),
\+ (member(Z,Partial)),
reach(Z,Y,G,[Z|Partial],Path1),
Path=[X|Path1].
reach(X,Y,G,Partial,Path):-
\+ (member(Y,Partial)),
member(edge(Z,X),G),
\+ (member(Z,Partial)),
reach(Z,Y,G,[Z|Partial],Path1),
Path=[X|Path1].
% member/2
member(H,[H|_]).
member(H,[_|T]):- member(H,T).
% append/3
append([],L,L).
append([H|T],L,[H|R]):- append(T,L,R).
% length/2
myLength([],0).
myLength([_|T],L):- myLength(T,L1), L is L1+1.
%%%%%%%%%%%%%bishop.pl%%%%%%%%%%%%
% There is a simple solution: N is Size-2
% Still, this is a complete solution with n-queens and (I,J)-safeness
bishop(Size,N):-
findall(Solution, go(Size,Solution), L1),
pairSolutionMaxRooks(Size,L1,L2), % pair all solutions with the maximal number of rooks, so that we can add a bishop
max(L2,0,N).
go(Size,Solution):-
poss_rows(Size,PossList),
solve(PossList,0,[],Solution).
poss_rows(N,R):- poss_rows(N,[],R).
poss_rows(0,L,L).
poss_rows(N,K,L):-
N > 0,
N1 is N-1,
poss_rows(N1,[N|K],L).
solve([Poss1|RestPoss],Col,Current,Final):-
Col1 is Col+1,
select([Poss1|RestPoss],Row,NewPossRows),
safe(Col1,Row,Current),
solve(NewPossRows,Col1,[s(Col1,Row) | Current],Final).
solve([],_,Final,Final).
safe(X,Y,[s(I,J)|Rest]):-
not(threaten(X,Y,I,J)),
safe(X,Y,Rest).
safe(_,_,[]).
threaten(X,Y,I,J):-
U is X+Y,
U is I+J.
threaten(X,Y,I,J):-
U is X-Y,
U is I-J.
max([],Max,Max):- !.
max([f(_,I)|T],PMax,Max):-
PMax < I,
max(T,I,Max),
!.
max([_|T],PMax,Max):-
max(T,PMax,Max).
select([Y|L],X,[Y|M]):- select(L,X,M).
select([X|L],X,L).
pairSolutionMaxRooks(_,[],[]):- !.
pairSolutionMaxRooks(Size,[H|T],[f(H,N)|T2]):-
pairSolutionMaxRooks1(Size,H,N),
pairSolutionMaxRooks(Size,T,T2).
pairSolutionMaxRooks1(Size,Solution,N):-
for(I,1,Size),
br(Solution,I,NewSolution),
testAllowsExtraBishop(Size,NewSolution),
N is Size-I,
!.
pairSolutionMaxRooks1(_Size,_Solution,0).
br([],0,[]).
br([s(X,Y)|RestSolution],I,[s(r,X,Y)|NewSolution]):-
br(RestSolution,I,NewSolution).
br([s(X,Y)|RestSolution],I,[s(b,X,Y)|NewSolution]):-
I>0,
I1 is I-1,
br(RestSolution,I1,NewSolution).
testAllowsExtraBishop(Size,NewSolution):-
putExtraBishop(Size,NewSolution,NewSolution2),
testSafeness(NewSolution2,NewSolution2),
!.
putExtraBishop(Size,NewSolution,NewSolution2):-
for(I,1,Size),
for(J,1,Size),
\+( member(s(_,I,J),NewSolution) ),
NewSolution2 = [s(b,I,J)|NewSolution].
testSafeness([],_):-
!.
testSafeness([s(X,I,J)|T],Solution):-
testSafeness2(s(X,I,J),Solution),
testSafeness(T,Solution),
!.
testSafeness2(_,[]):-
!.
testSafeness2(s(X,I,J),[H|T]):-
H = s(X,I,J),
testSafeness2(s(X,I,J),T),
!.
testSafeness2(s(X,I,J),[H|T]):-
\+( testSafeness3(s(X,I,J),H) ),
testSafeness2(s(X,I,J),T),
!.
testSafeness3(s(b,I1,J1),s(_,I2,J2)):-
U1 is I1+J1, % same right diagonal
U2 is I2+J2,
U1 = U2.
testSafeness3(s(b,I1,J1),s(_,I2,J2)):-
U1 is I1-J1, % same left diagonal
U2 is I2-J2,
U1 = U2.
testSafeness3(s(_,I1,J1),s(b,I2,J2)):-
U1 is I1+J1, % same right diagonal
U2 is I2+J2,
U1 = U2.
testSafeness3(s(_,I1,J1),s(b,I2,J2)):-
U1 is I1-J1, % same left diagonal
U2 is I2-J2,
U1 = U2.
testSafeness3(s(_,I,_),s(r,I,_)).
testSafeness3(s(_,_,J),s(r,_,J)).
for(I,I,J):- I =< J.
for(K,I,J):- I < J,
I1 is I + 1,
for(K,I1,J).
%%%%%%%%%%%%%end submission%%%%%%%%%%%%