% Alain V. De Lara

/*#######################################################################

#########################################################################

EXERCISE 1

In prolog mod is the mod function.

?- X is 23 mod 20.

X = 3.

Use the range/3 predicate and the mod function to generate

a list of the divisors of a number.

?- divisors(28, Ds).

Ds = [1, 2, 4, 7, 14]

#########################################################################

#######################################################################*/

range(H,H,[H]).

range( Low , Hig , [Low|LT] ):- Low < Hig,

L1 is Low+1,

range(L1,Hig,LT).

nullmod(Num,Quot):-X is Num mod Quot,X=0.

hasnullmod(_,[],[]).

hasnullmod(N,[H|Lchk],[H|LGood]) :- nullmod(N,H) , hasnullmod(N,Lchk,LGood).

hasnullmod(N,[H|Lchk], LGood) :- not(nullmod(N,H)) , hasnullmod(N,Lchk,LGood).

divisors(0,[0]).

divisors(1,[1]).

divisors(N,Dlist):-range(1,N,Temp),hasnullmod(N,Temp,Dlist).

/*#######################################################################

#########################################################################

EXERCISE 2

Do the homework at the end of Prolog and graphs

by using the following strategy.

See if there is a path of length 0.

If not, see if there is a path of length 1.

If not, see if there is a path of length 2.

If not, see if there is a path of length 3. Etc....

This strategy is known as Generate and Test. You are generating the integers in

sequence and then testing to see if there is a path of that length. You continue

to do that until you find a path or you determine that no path is possible.

In some cases you might simply search forever. (You will learn about this in CS 486.)

Use something like is_integer/1 to generate successively larger integers.

Assume you know the total number of edges in the graph. Don't allow the possible

length of the path to exceed the total number of edges. That is, as you increment

the possible path length, don't allow it to exceed the total number of edges.

If no path is found, fail.

#########################################################################

#######################################################################*/

%----------------

% BEFORE

%----------------

/*--------------------------------------------------------------------

edge(1,2).

edge(1,4).

edge(1,3).

edge(2,3).

edge(2,5).

edge(3,4).

edge(3,5).

edge(4,5).

connected(X,Y) :- edge(X,Y) ; edge(Y,X).

path(A,B,Path) :- travel(A,B,[A],Q),reverse(Q,Path).

travel(A,B, P ,[B|P]) :- connected(A,B).

travel(A,B,Visited ,Path ) :- connected(A,C), C \== B,

\+member(C,Visited),

travel(C,B,[C|Visited],Path).

-------------------------------------------------------------------*/

%----------------------------------------------------------------------------------

% MY DATABASE, modified now edges have length: edgelen(Vertex1,Vertex1, Length )

% Refer to the picture below

%----------------------------------------------------------------------------------

%----------------

% AFTER

%----------------

edgelen(1,2,1).

edgelen(1,3,1).

edgelen(1,4,2).

edgelen(2,4,1).

edgelen(2,7,3).

edgelen(3,4,1).

edgelen(3,5,3).

edgelen(4,5,1).

edgelen(4,6,2).

edgelen(4,7,1).

edgelen(6,7,1).

edgelen(5,6,1).

% Distance Generator

is_dist(0).

is_dist(X):-is_dist(Y), X is Y+1.

% modified, used to get distance between 2 points

connectedl(X,Y,Len) :- edgelen(X,Y,Len) ; edgelen(Y,X,Len).

sumlist([],0).

sumlist([H|T],S) :- sumlist(T,Sr), S is H + Sr.

% calculate the total distance of a path

distance(PathVertices,Len):-path_dist_calc(PathVertices,L), sumlist(L,Len).

path_dist_calc([E1,E2] , L):- connectedl(E1,E2,Ls),append([Ls],[],L).

path_dist_calc([E1,E2|Tail],ListF):- connectedl(E1,E2,Lcalc), append([Lcalc],ListB,ListF), path_dist_calc([E2|Tail],ListB).

% Modified path, also return the distance of a path

pathl(A,B,Path,Len) :- travell(A,B,[A],Q),reverse(Q,Path), distance(Path,Len).

travell(A,B, P ,[B|P]) :- connectedl(A,B,_).

travell(A,B,Visited ,Path ) :- connectedl(A,C,_), C \== B, \+member(C,Visited), travell(C,B,[C|Visited],Path).

% find the shortest path, but we dont want any distance bigger than "Max"

% "is_dist" and "pathl" are distance and path generators

shortpath(V1,V2,Minlen,Max):- is_dist(Dist), pathl(V1,V2,Pat,Dist), Minlen is Dist, Dist<Max,

write('The shortest path is='),write(Pat),

write(' and the minimum distance is '),write(Dist), !.

% cut on the first valid unification

/*================================================

TEST RUN OUTPUT

?- shortpath(1,7,L,10).

The shortest path is=[1, 2, 4, 7] and the minimum distance is 3

L = 3 ;

================================================*/

/*#######################################################################

#########################################################################

EXERCISE 3

Use generate and test to find (on backtracking) all perfect integers

i.e., integers which are the sum of their divisors.

?- is_perfect(X).

X = 6;

X = 28; …

#########################################################################

#######################################################################*/

/*---------------------------------------------------------

some prime number and perfect numbers=2^(n-1)x(2^n - 1)

n= 2 ==> 6

n= 3 ==> 28

n= 5 ==> 496

n= 7 ==> 8128

n=13 ==> 33550336

n=17 ==> 8589869056

n=19 ==> 137438691328

n=31 ==> 2305843008139952128

---------------------------------------------------------*/

% GENERATOR (page 77 of "programming in prolog"), generate integer number>0

is_integer(0).

is_integer(X) :- is_integer(Y), X is Y+1.

%==== Testor function Prime ====

/*------------------------------------

equivalent code in turbo-pascal for prime(X)

function IsPrime(N: Integer): Boolean;

var j, Stop: Integer;

Factored: Boolean;

begin

Factored:=False;

j:=2;

Stop:=Trunc(Sqrt(N))+1;

while (j<=Stop) and (j<N) and (Factored=false) do

begin

Factored:=((N mod j)=0);

j:=j+1;

end;

IsPrime := not Factored;

end;

--------------------------------------*/

% 2 and 3 are the first two prime numbers

prime(2).

prime(3).

prime(N):- N>3,N mod 2 =\=0 ,Stop is truncate(sqrt(N))+1, factored(N,Stop,3).

factored(N,Stop,Stop).

factored(N,Stop,J):- I is J+1 ,J=<Stop, N mod J=\= 0,factored(N,Stop,I).

is_perfect(PerfectNumber):-is_integer(N), prime(N), PerfectNumber is 2 ** (N-1)*(2 ** N -1).

%--- comment: float overflow at PerfectNumber=1.40445e+306 ---

/*#######################################################################

#########################################################################

#######################################################################*/