/****************************************************************/
 Solutions in B-Prolog for the 2011 Prolog Programming Contest 
 http://users.ugent.be/~tschrijv/ppc/ppc2011_probs.pdf
 Team members: Salvador Abreu, Ulrich Neumerkel, and Neng-Fa Zhou 
****************************************************************/

%% chicken.pl
% sample query ?-chicken(3).

chicken(N):-
    NR is 5+2*(N-1),
    NC is 7*2*(N-1)+6,
    new_array(A,[NR,NC]),
    place_u(A,2*(N-1)+1,1,N),
    (N mod 2=:=0->place_c2(A,1,7*(N-1)+1);place_c1(A,1,7*(N-1)+1)),
    place_d(A,3,7*(N-1)+7,N),
    foreach(R in 1..NR, 
            (foreach(C in 1..NC, [E], 
                     (E@=A[R,C],(var(E)->write(' ');format("~s",[E])))),nl)).

place_u(A,R,C,I):-I=<1,!.
place_u(A,R,C,I):-
    place_cb(A,R,C),
    R1 is R-2,
    C1 is C+7,
    I1 is I-1,
    place_u(A,R1,C1,I1).

place_d(A,R,C,I):-I=<1,!.
place_d(A,R,C,I):-
    place_bc(A,R,C),
    R1 is R+2,
    C1 is C+7,
    I1 is I-1,
    place_d(A,R1,C1,I1).
    
place_c1(A,R,C):-
    place_s(A,R,C,  "   \\\\ "),
    place_s(A,R+1,C,"   (o>"),
    place_s(A,R+2,C,"\\\\_//)"),
    place_s(A,R+3,C," \\_/_)"),
    place_s(A,R+4,C,"___|__").

place_c2(A,R,C):-
    place_s(A,R,C,  "   // "),
    place_s(A,R+1,C,"   <o)"),
    place_s(A,R+2,C,"(\\\\_//"),
    place_s(A,R+3,C,"(_\\_/)"),
    place_s(A,R+4,C,"__|___").

place_cb(A,R,C):-
    place_s(A,R,C,  "   \\\\  "),
    place_s(A,R+1,C,"   (o> "),
    place_s(A,R+2,C,"\\\\_//) "),
    place_s(A,R+3,C," \\_/_)|"),
    place_s(A,R+4,C,"___|__|").

place_bc(A,R,C):-
    place_s(A,R,C,  "  //   "),
    place_s(A,R+1,C," <o)  "),
    place_s(A,R+2,C," (\\\\_//"),
    place_s(A,R+3,C,"|(_\\_/ "),
    place_s(A,R+4,C,"|__|___").

place_s(A,R,C,[]).
place_s(A,R,C,[X|Xs]):-
    A[R,C] @= X,
    C1 is C+1,
    place_s(A,R,C1,Xs).
  


%% pattern.pl
% sample query ?-pattern(3,L).

pattern(N,L):-
    M is 2**N,
    length(LBs,M),
    foreach(Bs in LBs, (length(Bs,N), Bs :: 0..1)),
    Bs0 @= [0 : I in 1..N],
    LBs=[Bs0|LBs1],
    last(LBs,Bs1),
    constr([Bs1|LBs]),
    term_variables(LBs,Vars),
    labeling(Vars),
    N1 is N-1,
    length(Dum,N1),
    append(LBs2,Dum,LBs1),
    flat(LBs2,L1),
    append(Bs0,L1,L).
    
constr([_]):-!.
constr([Bs1,Bs2|LBs]):-
    [_|Sub] = Bs1,
    append(Sub,[_],Bs2),
    foreach(Bs in LBs, dif(Bs,Bs2)),
    constr([Bs2|LBs]).

flat([],[]).
flat([Bs|LBs],[B|L]):-
    last(Bs,B),
    flat(LBs,L).


%% race.pl
% sample query ?-race([1-1,1-2],4,4,Winner).

race(Ps,N,M,W):-
  L @= [(Len,P) : P in Ps, [Len], path(P,1,1,N,M,Len)],
  sort(L,SL),
  SL=[(_,W)|_].


:-table path(+,+,+,+,+,min).
path(_,N,M,N,M,Len):-!,Len=0.
path(P,I,J,N,M,Len):-
  next(P,I,J,I1,J1,N,M),
  path(P,I1,J1,N,M,Len1),
  Len is Len1+1.

next(D1-D2,I,J,I1,J1,N,M):-
  I1 is I+D1, J1 is J+D2,
  I1>=1, I1=<N,
  J1>=1, J1=<M.
next(D1-D2,I,J,I1,J1,N,M):-
  I1 is I-D1, J1 is J+D2,
  I1>=1, I1=<N,
  J1>=1, J1=<M.
next(D1-D2,I,J,I1,J1,N,M):-
  I1 is I+D1, J1 is J-D2,
  I1>=1, I1=<N,
  J1>=1, J1=<M.
next(D1-D2,I,J,I1,J1,N,M):-
  I1 is I-D1, J1 is J-D2,
  I1>=1, I1=<N,
  J1>=1, J1=<M.
%
next(D1-D2,I,J,I1,J1,N,M):-
  I1 is I+D2, J1 is J+D1,
  I1>=1, I1=<N,
  J1>=1, J1=<M.
next(D1-D2,I,J,I1,J1,N,M):-
  I1 is I-D2, J1 is J+D1,
  I1>=1, I1=<N,
  J1>=1, J1=<M.
next(D1-D2,I,J,I1,J1,N,M):-
  I1 is I+D2, J1 is J-D1,
  I1>=1, I1=<N,
  J1>=1, J1=<M.
next(D1-D2,I,J,I1,J1,N,M):-
  I1 is I-D2, J1 is J-D1,
  I1>=1, I1=<N,
  J1>=1, J1=<M.


%% war.pl
% sample query ?-t(N).

war(Js,Ss,NW):-
    length(Js,N),
    Ws @= [W : joint(X,_,_,_) in Js, [W], nw(X,Js,Ss,N,W)],
    sort(Ws,SWs),
    SWs=[NW|_].

nw(X,Js,Ss,N,W):-
    nw(X,Js,Ss,[],N,W).

:- table nw(+,+,+,+,+,min).
nw(X,Js,_Ss,_Path,1,W):-!,
    (member(joint(X,Ne,In,De),Js)->true;true),
    W is max(In+De,Ne).
nw(X,Js,Ss,Path,C,W):-
    (member(street(X,Y),Ss);
     member(street(Y,X),Ss)),
    \+ member(Y,Path), 
    C1 is C-1,
    nw(Y,Js,Ss,[X|Path],C1,W1),
    (member(joint(X,Ne,In,De),Js)->true;true),
    W is max(W1+In+De,Ne).
    
t(N):-
    war([joint(m,5,5,5),joint(p,10,5,5),joint(s,5,1,1)],
	[street(m,s),street(p,s)],N).

%% plumber.pl
% sample query ?-t.

plumber(Grid, Ps) :-
    length(Grid,N),
    TagPs @= [(P,Tag) : P in Ps,[Tag]],
    foreach(I in 1..N, J in 1..N, place(Grid,I,J,N,TagPs)).

place(Grid,I,J,N,Ps):-
    place_piece(Grid,I,J,Ps,P),
    (I==1->no_up(P); I==N->no_down(P); true),
    (J==1->no_left(P); J==N->no_right(P); true),
    I1 is I+1,
    (I1=<N->
     place_piece(Grid,I1,J,Ps,Pd),    
     match(P,Pd,down);
     true),
    J1 is J+1,
    (J1=<N->
     place_piece(Grid,I,J1,Ps,Pr),    
     match(P,Pr,right);
     true).

place_piece(Grid,I,J,Ps,P):-
    P @= Grid[I,J],
    (var(P)->member((P,Tag),Ps),var(Tag),Tag=1;true).

match(pipe(X,_,_,_),pipe(_,_,X,_),down).
match(pipe(_,_,_,X),pipe(_,X,_,_),right).

no_up(pipe(no,_,_,_)).
no_right(pipe(_,no,_,_)).
no_down(pipe(_,_,no,_)).
no_left(pipe(_,_,_,no)).

t :-
   Grid = [[_,_],[pipe(yes,yes,no,no),_]],
   Pieces = [pipe(yes,no,no,yes),pipe(no,yes,yes,no),pipe(no,no,yes,yes)],
   plumber(Grid, Pieces),
   writeln(Grid),
   Grid = [[pipe(no,yes,yes,no),pipe(no,no,yes,yes)],
           [pipe(yes,yes,no,no),pipe(yes,no,no,yes)]].