% Alain V. De Lara
/*#######################################################################
#########################################################################
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 same used from last homework
range(H,H,[H]).
range( Low , Hig ,
[P1|LT] ):- Low < Hig,
L1 is Low+1,
P1 is L1-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).
/*#######################################################################
#########################################################################
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).
is_dist(0).
is_dist(X):-is_dist(Y),
X is Y+1.
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.
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).
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 ;
No
================================================*/
/*#######################################################################
#########################################################################
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 pascal for prime
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):-
J<N,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
---
/*#######################################################################
#########################################################################
#########################################################################
#######################################################################*/