/* CHANGELOG by M.Banbara
  - print_times/4 --> print_times/5
  - report_csv/2 is added.
   - user  --> user_output (stream alias)
*/

/* Common functions...       */
%print_times(T1,T2,T3,L) :-
%        TT1 is T2 - T1,
%        TT2 is T3 - T2,
%        TT is TT1 - TT2,
%        write('Net Time is: '), write(TT), nl,
%        Lips is L / TT,
%        Klips is Lips / 1000,
%        write('KLips are: '), write(Klips), nl.

print_times(Name,T1,T2,T3,L) :-
        TT1 is T2 - T1,
        TT2 is T3 - T2,
        TT is TT1 - TT2,
        write('# Name:             '),write(Name), nl,
        write('# Net Time is:      '),write(TT),write(' msec.'),nl,
        write('# KLips are:        '),
        Lips is L / TT,
        KLips is Lips / 1000,
        write(KLips),nl,
	report_csv(['###CSV###',Name,TT1,TT2,TT,KLips], ','),
	nl.

report_csv([], _) :- !.
report_csv([X], _) :- !, write(X), nl.
report_csv([X|Xs], Delim) :- write(X), write(Delim), report_csv(Xs, Delim).

compens_loop(0).
compens_loop(X) :- Y is X - 1, compens_loop(Y).

el(X,[X|L]).
el(X,[Y|L]):-el(X,L).

list50([27,74,17,33,94,18,46,83,65,2,
       32,53,28,85,99,47,28,82,6,11,
       55,29,39,81,90,37,10,0,66,51,
        7,21,85,27,31,63,75,4,95,99,
       11,28,61,74,18,92,40,53,59,8]).

/* Fibonacci Series the slow way            */
/* fibonacci(1) will do...                  */

fibonacci(N) :- statistics(runtime,[X|_]),
          fib_loop(N),
          statistics(runtime,[Now|_]),
          compens_loop(N),
          statistics(runtime,[M|_]),
          Li is 4932 * N,
          print_times(fibonacci(N),X,Now,M,Li).


fib_loop(0).
fib_loop(X) :- \+ \+ top_fib(15,Z), Y is X - 1, fib_loop(Y).

top_fib(0,1).
top_fib(1,1).
top_fib(X,Y):-X1 is X-1,X2 is X-2,top_fib(X1,Y1),
             top_fib(X2,Y2),Y is Y1+Y2.

/* ------------------------------------ */
/* Map colouring problem                */
/*  map(200) is advised.                */

map(N) :- statistics(runtime,[X|_]),
          map_loop(N),
          statistics(runtime,[Now|_]),
          compens_loop(N),
          statistics(runtime,[M|_]),
          Li is 68 * N,
          print_times(map(N),X,Now,M,Li).

map_loop(0).
map_loop(X) :- \+ \+ map_top, Y is X - 1, map_loop(Y).

map_top:-
	el(X1,[b]),
	el(X2,[r]),
	el(X7,[g]),
	el(X13,[w]),
	el(X3,[b,r,g,w]),
	\+(X2=X3),
	\+(X3=X13),
	el(X4,[b,r,g,w]),
	\+(X2=X4),
	\+(X7=X4),
	\+(X3=X4),
	el(X5,[b,r,g,w]),
	\+(X13=X5),
	\+(X3=X5),
	\+(X4=X5),
	el(X6,[b,r,g,w]),
	\+(X13=X6),
	\+(X5=X6),
	el(X8,[b,r,g,w]),
	\+(X7=X8),
	\+(X13=X8),
	el(X9,[b,r,g,w]),
	\+(X13=X9),
	\+(X4=X9),
	\+(X8=X9),
	el(X10,[b,r,g,w]),
	\+(X4=X10),
	\+(X5=X10),
	\+(X6=X10),
	\+(X9=X10),
	el(X11,[b,r,g,w]),
	\+(X11=X13),
	\+(X11=X10),
	\+(X11=X6),
	el(X12,[b,r,g,w]),
	\+(X12=X13),
	\+(X12=X11),
	\+(X12=X9).
	%write(user_output,[X1,X2,X3,X4,X5,X6,X7,X8,X9,X10,X11,X12,X13]),nl.

map_top.

/* ---------------------------------------------- */
/*  Hamiltonian Graphs...                         */
/*  Extremely long (nearly half a million LI's !) */
/*  Only 1 advised !                              */

mham(N) :- statistics(runtime,[X|_]),
          mham_loop(N),
          statistics(runtime,[Now|_]),
          compens_loop(N),
          statistics(runtime,[M|_]),
          Li is 493824 * N,
          print_times(mham(N),X,Now,M,Li).

mham_loop(0).
mham_loop(X) :- \+ \+ mham_top, Y is X - 1, mham_loop(Y).

mham_top:-
        cycle_ham([a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t],X),
        fail.
mham_top.

cycle_ham([X|Y],[X,T|L]):-
        chain_ham([X|Y],[],[T|L]),
        edge(T,X).

chain_ham([X],L,[X|L]).
chain_ham([X|Y],K,L):-
        delete(Z,Y,T),
        edge(X,Z),
        chain_ham([Z|T],[X|K],L).

delete(X,[X|Y],Y).
delete(X,[U|Y],[U|Z]):-
        delete(X,Y,Z).

edge(X,Y):-
        connect(X,L),
        el(Y,L).

connect(0,[1,2,3,4,5,6,7,8,9]).
connect(1,[0,2,3,4,5,6,7,8,9]).
connect(2,[0,1,3,4,5,6,7,8,9]).
connect(3,[0,1,2,4,5,6,7,8,9]).
connect(4,[0,1,2,3,5,6,7,8,9]).
connect(5,[0,1,2,3,4,6,7,8,9]).
connect(6,[0,1,2,3,4,5,7,8,9]).
connect(7,[0,1,2,3,4,5,6,8,9]).
connect(8,[0,1,2,3,4,5,6,7,9]).
connect(9,[0,1,2,3,4,5,6,7,8]).

connect(a,[b,j,k]).
connect(b,[a,c,p]).
connect(c,[b,d,l]).
connect(d,[c,e,q]).
connect(e,[d,f,m]).
connect(f,[e,g,r]).
connect(g,[f,h,n]).
connect(h,[i,g,s]).
connect(i,[j,h,o]).
connect(j,[a,i,t]).
connect(k,[o,l,a]).
connect(l,[k,m,c]).
connect(m,[l,n,e]).
connect(n,[m,o,g]).
connect(o,[n,k,i]).
connect(p,[b,q,t]).
connect(q,[p,r,d]).
connect(r,[q,s,f]).
connect(s,[r,t,h]).
connect(t,[p,s,j]).

/* -------------------------------------------- */
/*  Hofstader's mu math (mutest) proving muiiu  */
/*  from Godel Escher Bach                      */
mutest(N) :- statistics(runtime,[X|_]),
          mu_loop(N),
          statistics(runtime,[Now|_]),
          compens_loop(N),
          statistics(runtime,[M|_]),
          Li is 1366 * N,
          print_times(mutest(N),X,Now,M,Li).

mu_loop(0).
mu_loop(X) :- \+ \+ mu_top, Y is X - 1, mu_loop(Y).

mu_top:- theorem(5,[m,u,i,i,u]).

rules(S, R) :- rule3(S,R).
rules(S, R) :- rule4(S,R).
rules(S, R) :- rule1(S,R).
rules(S, R) :- rule2(S,R).

rule1(S,R) :-
        append(X, [i], S),
        append(X, [i,u], R).

rule2([m | T], [m | R]) :- append(T, T, R).

rule3([], -) :- fail.
rule3(R, T) :-
        append([i,i,i], S, R),
        append([u], S, T).
rule3([H | T], [H | R]) :- rule3(T, R).

rule4([], -) :- fail.
rule4(R, T) :- append([u, u], T, R).
rule4([H | T], [H | R]) :- rule4(T, R).

theorem(Depth, [m, i]).
theorem(Depth, []) :- fail.

theorem(Depth, R) :-
        Depth > 0,
        D is Depth - 1,
        theorem(D, S),
        rules(S, R).

append([], X, X).
append([A | B], X, [A | B1]) :-
        !,
        append(B, X, B1).
/* ------------------------------------  */
/*  Quicksort of 50 element list         */
/*                                       */

qs(N) :-  list50(L),
          statistics(runtime,[X|_]),
          qs_loop(N,L),
          statistics(runtime,[Now|_]),
          compens_loop(N),
          statistics(runtime,[M|_]),
          Li is 601 * N,
          print_times(qs(N),X,Now,M,Li).

qs_loop(0,_).
qs_loop(X,L) :- qsort(L,Z,[]), Y is X - 1,qs_loop(Y,L).

qsort([X|L],R,R0) :-
      partition(L,X,L1,L2),
      qsort(L2,R1,R0),
      qsort(L1,R,[X|R1]).
qsort([],R,R).

partition([X|L],Y,[X|L1],L2) :- X =< Y,!,
      partition(L,Y,L1,L2).
partition([X|L],Y,L1,[X|L2]) :-
      partition(L,Y,L1,L2).
partition([],_,[],[]).

/* ------------------------------------ */
/*  Queens on a chess board problem...  */
/*  Only two solution on a 4x4 board... */
/*  about 5 - 10 is advised for N.      */
qu(N) :- statistics(runtime,[X|_]),
          qu_nloop(N),
          statistics(runtime,[Now|_]),
          compens_loop(N),
          statistics(runtime,[M|_]),
          Li is 684 * N,
          print_times(qu(N),X,Now,M,Li).

qu_nloop(0).
qu_nloop(X) :- qu_top, Y is X - 1, qu_nloop(Y).

qu_top :-  run(4,X), fail.
qu_top.

size(4).
snint(1).
snint(2).
snint(3).
snint(4).

run(Size, Soln) :- get_solutions(Size, Soln).

get_solutions(Board_size, Soln) :- solve(Board_size, [], Soln).

/*  newsquare generates legal positions for next queen     */

newsquare([], square(1, X)) :- snint(X).
newsquare([square(I, J) | Rest], square(X, Y)) :-
        X is I + 1,
        snint(Y),
        \+(threatened(I, J, X, Y)),
        safe(X, Y, Rest).

/*   safe checks whether square(X, Y) is threatened by any */
/*   existing queens                                       */

safe(X, Y, []).
safe(X, Y, [square(I, J) | L]) :-
        \+(threatened(I, J, X, Y)),
        safe(X, Y, L).

/*    threatened checks whether squares (I, J) and (X, Y) */
/*    threaten each other                                 */

threatened(I, J, X, Y) :-
        (I = X),
        !.
threatened(I, J, X, Y) :-
        (J = Y),
        !.
threatened(I, J, X, Y) :-
        (U is I - J),
        (V is X - Y),
        (U = V),
        !.
threatened(I, J, X, Y) :-
        (U is I + J),
        (V is X + Y),
        (U = V),
        !.

/* solve accumulates the positions of occupied squares */

solve(Bs, [square(Bs, Y) | L], [square(Bs, Y) | L]) :- size(Bs).
solve(Board_size, Initial, Final) :-
        newsquare(Initial, Next),
        solve(Board_size, [Next | Initial], Final).

/* ------------------------------------ */
/* Query does simple database queries.  */
/*                                      */

query(N) :- statistics(runtime,[X|_]),
          que_nloop(N),
          statistics(runtime,[Now|_]),
          compens_loop(N),
          statistics(runtime,[M|_]),
          Li is 2294 * N,
          print_times(query(N),X,Now,M,Li).

que_nloop(0).
que_nloop(X) :- que_top, Y is X - 1, que_nloop(Y).

que_top:- que(X), fail.
que_top.

que([C1,D1,C2,D2]) :-
      density(C1,D1),
      density(C2,D2),
      D1>D2,
      20*D1<21*D2.

density(C,D) :-
      pop(C,P),
      area(C,A),
      D is (P*100)/A.

pop(china,8250).
pop(india,5863).
pop(ussr,2521).
pop(usa,2119).
pop(indonesia,1276).
pop(japan,1097).
pop(brazil,1042).
pop(bangladesh,750).
pop(pakistan,682).
pop(w_germany,620).
pop(nigeria,613).
pop(mexico,581).
pop(uk,559).
pop(italy,554).
pop(france,525).
pop(philippines,415).
pop(thailand,410).
pop(turkey,383).
pop(egypt,364).
pop(spain,352).
pop(poland,337).
pop(s_korea,335).
pop(iran,320).
pop(ethiopia,272).
pop(argentina,251).

area(china,3380).
area(india,1139).
area(ussr,8708).
area(usa,3609).
area(indonesia,570).
area(japan,148).
area(brazil,3288).
area(bangladesh,55).
area(pakistan,311).
area(w_germany,96).
area(nigeria,373).
area(mexico,764).
area(uk,86).
area(italy,116).
area(france,213).
area(philippines,90).
area(thailand,200).
area(turkey,296).
area(egypt,386).
area(spain,190).
area(poland,121).
area(s_korea,37).
area(iran,628).
area(ethiopia,350).
area(argentina,1080).

/* --------------------------------------------------*/
/*       differen (times10,divide10,log10,ops8)      */
/*       These 4 examples are from Warren's thesis   */
/*       differen(150) will do.                      */

differen(N) :- statistics(runtime,[X|_]),
          differenloop(N),
          statistics(runtime,[Now|_]),
          compens_loop(N),
          statistics(runtime,[M|_]),
          Li is 71 * N,
          print_times(differen(N),X,Now,M,Li).

differenloop(0).
differenloop(X) :- \+ \+(differen_top), Y is X - 1, differenloop(Y).

differen_top:-
        times10(I1),
        d(I1,x,D1),
        divide10(I2),
        d(I2,x,D2),
        log10(I3),
        d(I3,x,D3),
        ops8(I4),
        d(I4,x,D4).

d(U+V,X,DU+DV) :- !, d(U,X,DU), d(V,X,DV).
d(U-V,X,DU-DV) :- !, d(U,X,DU), d(V,X,DV).
d(U*V,X,DU*V+U*DV) :- !, d(U,X,DU), d(V,X,DV).
d(U/V,X,(DU*V-U*DV)/(^(V,2))) :- !, d(U,X,DU), d(V,X,DV).
d(^(U,N),X,DU*N*(^(U,N1))) :- !, integer(N), N1 is N - 1, d(U,X,DU).
d(-U,X,-DU) :- !, d(U,X,DU).
d(exp(U),X,exp(U)*DU) :- !, d(U,X,DU).
d(log(U),X,DU/U) :- !, d(U,X,DU).
d(X,X,1).
d(C,X,0).

times10( ((((((((x*x)*x)*x)*x)*x)*x)*x)*x)*x ).
divide10( ((((((((x/x)/x)/x)/x)/x)/x)/x)/x)/x ).
log10( log(log(log(log(log(log(log(log(log(log(x)))))))))) ).
ops8( (x+1)*((^(x,2)+2)*(^(x,3)+3)) ).

/* --------------------------------------------------- */
/*  Difference Lists                                   */
/*       quicksort on 50 items (difference lists)      */

diff(N) :- list50(L),
          statistics(runtime,[X|_]),
          difflistloop(N,L),
          statistics(runtime,[Now|_]),
          compens_loop(N),
          statistics(runtime,[M|_]),
          Li is 608 * N,
          print_times(diff(N),X,Now,M,Li).

difflistloop(0,_).
difflistloop(X,L) :- qdsort(L,Z), Y is X - 1, difflistloop(Y,L).

qdsort([X|L],R-R0) :-
        dpartition(L,X,L1,L2),
        qdsort(L1,R-[X|R1]),
        qdsort(L2,R1-R0).
qdsort([],R0-R0).

dpartition([X|L],Y,[X|L1],L2) :-
        X<Y, !,
        dpartition(L,Y,L1,L2).
dpartition([X|L],Y,L1,[X|L2]) :-
        dpartition(L,Y,L1,L2).
dpartition([],_,[],[]).

/* -------------------------------------------------- */
/*  Naive reverse for variable length lists...        */
/*  try with 10, 30, 50, 100, 150, 200.               */

nrev(X) :- 
        conslist(X, List),
        statistics(runtime,[T1|_]),
        nreverse(List, _),
        statistics(runtime,[T2|_]),
        I is (X*(X+3))/2 + 1,
	print_times(nrev(X),T1,T2,T2,I).

nrev:- write('list length: '),
        read(X),
        conslist(X, List),
        statistics(runtime,[T1|_]),
        nreverse(List, _),
        statistics(runtime,[T2|_]),
        T is T2 - T1,
        I is (X*(X+3))/2 + 1,
        LIPS is I/T,
        write('LIPS= '),
        write(LIPS).

nreverse([], []).
nreverse([X|L0],L) :- nreverse(L0, L1),
    concatenate(L1, [X], L).

concatenate([], L, L).
concatenate([X|L1], L2, [X|L3]) :- concatenate(L1, L2, L3).

conslist(0, []) :- !.
conslist(N, [N|L]) :-
        N1 is N-1,
        conslist(N1, L).