Main page: http://www.cs.kuleuven.be/~bmd/PrologProgrammingContests/Contest2008.html , contest net version page: http://www.cs.kuleuven.be/~bmd/PrologProgrammingContests/2008/net2008.html
Problem Specification: probs.pdf
Date: Dec 11, 2008 12:57 AM
Subject: PPC2008
%%%%%%%%%%%%%begin submission%%%%%%%%%%%%%
Name(s): Diptikalyan Saha, Paul Fodor, Senlin Liang
Affiliation(s): Stony Brook University, Motorola Research
Prolog system used: XSB
%%%%%%%%%%%%%chocolate.pl%%%%%%%%%%%%
chocolate(X,Y):-
top(X),nl,
write('.'),sides(X),nl,
write('|\'),bottom(X),nl,
Y1 is Y-1,
for(I,1,Y1,1,
[I2 is I*2-1, I3 is 2*I,
blank(I2),write('\\\\'),sides(X),nl,
blank(I3),write('\\\\'),(I=Y1->bottom1(X);bottom(X)),nl]),
Y2 is 2*Y1+1,
blank(Y2),write('\|'),
X1 is X*5-1,
bar1(X1),write('|').
top(X):-
for(I,1,X,1,
[blank(2),bar(3)]).
sides(X):-
for(I,1,X,1,
[write('''\__\')]).
bottom(X):-
for(I,1,X,1,
[write('/ __\')]).
bottom1(X):-
for(I,1,X,1,
[write('/ \')]).
blank(0):-!.
blank(I):-
I>0,
I1 is I-1,
write(' '),
blank(I1).
bar1(0):-!.
bar1(I):-
I>0,
I1 is I-1,
write('_'),
bar1(I1).
bar(0):-!.
bar(I):-
I>0,
I1 is I-1,
write('-'),
bar(I1).
for(I,Start,End,Increment,Do):-
Start=
(I=Start,
perform(Do),fail;true),
S1 is Start + Increment,
for(I,S1,End,Increment,Do)
;
true.
perform([]).
perform([X|L]):- X,perform(L).
%%%%%%%%%%%%%pixels.pl%%%%%%%%%%%%
% pix/1
%Algorithm:
%Let Matrix a matrix that is initially empty (NxM variables "_")
%for each pixel(I,J) in the pattern A (take all pixels - on first row,second row,...):
% - if the pixel is _, go over it
% - if the pixel is a number X:
% - if its equivalent in the matrix Matrix is lighted up, do nothing
% - if its equivalent in the matrix Matrix is not lighted up,
% search for a pair (equivalent number X) Right to it or Below it
% check the distance,
% check if in the matrix nothing in that path is lighten up already
% light all the pixels traversed by this path in the Matrix
%print Matrix (print * for variable)
%
% pix(square(pixels(_,_,_),pixels(_,_,_),pixels(_,_,_))).
% pix(square(pixels(3,3,3),pixels(_,_,_),pixels(3,3,3))).
% pix(square(pixels(3,_,3),pixels(3,_,3),pixels(3,_,3))).
% An example that can have two lightnings:
% pix(square(pixels(3,_,3),pixels(_,_,_),pixels(3,_,3))).
% pix(square(pixels(3,_,2),pixels(_,_,2),pixels(3,_,_))).
% pix(square(pixels(_,3,_),pixels(3,_,3),pixels(_,3,_))).
% pix(square(pixels(3,_,3),pixels(_,_,_),pixels(3,_,_))).
% pix(square(pixels(2,2,_),pixels(2,_,2),pixels(_,2,2))).
% pix(square(pixels(5,_,_,5,_,_,4,_,_,4,_,_,4,_,_,_,_,_,5,_,_,_,_,_,4,3,_,3),pixels(_,_,_,_,_,_,3,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,3),pixels(_,2,2,_,_,_,_,3,_,3,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_),pixels(_,_,_,_,_,_,3,_,_,_,_,_,4,_,_,_,_,_,_,_,_,_,_,_,4,_,_,3),pixels(5,_,_,5,_,_,4,_,_,4,_,_,4,_,_,4,_,_,5,3,_,3,_,_,4,_,_,4))).
% trace, pix(square(pixels(2,2))).
% trace, pix(square(pixels(3,3,3),pixels(_,_,_),pixels(3,3,3),pixels(3,_,3))).
pix(A):-
A=..[square|Pixels],
lengthList(Pixels,N), % number of rows
transformPixels(Pixels,Pattern),
Pattern = [OneRow|_],
lengthList(OneRow,M), % number of columns
createMatrix(N,M,Matrix),
N1 is N + 1, M1 is M + 1,
iterate(Pattern,N1,M1,1,1,Matrix,Matrix2),
printMatrix(Matrix2).
% iterate/7
% iterate(Pattern,N1,M1,I,J,Matrix,Matrix2)
iterate(_Pattern,N1,_M1,N1,1,Matrix,Matrix).
iterate(Pattern,N1,M1,I,J,Matrix,Matrix2):-
I < N1,
ithMatrix(I,J,Pattern,X),
(
var(X)
-> TempMatrix = Matrix
;(
ithMatrix(I,J,Matrix,Y),
(
var(Y)
->
(
check(Pattern,N1,M1,I,J,Matrix,X,TempMatrix)
)
; TempMatrix = Matrix % Y is already marked with '*'
)
)
),
N is N1 - 1, M is M1 - 1,
next(N,M,I,J,NI,NJ),
iterate(Pattern,N1,M1,NI,NJ,TempMatrix,Matrix2).
% check/8
% check(+Pattern,+N1,+M1,+I,+J,+Matrix,+X,-Matrix2)
% check([[3,_,3],[_,_,_],[3,_,_]],4,4,1,1,[[_,_,_],[_,_,_],[_,_,_]],3,Matrix2).
% check([[_,_,3],[_,_,_],[3,_,3]],4,4,3,1,[[_,_,'*'],[_,_,'*'],[_,_,'*']],3,Matrix2).
% check([[_,3,_],[3,_,3],[_,3,_]],4,4,2,1,[[_,'*',_],[_,'*',_],[_,'*',_]],3,Matrix2).
check(Pattern,N1,M1,I,J,Matrix,X,Matrix2):-
(
(
NJ is J + X - 1,
NJ < M1,
NI = I
);
(
NI is I + X - 1,
NI < N1,
NJ = J
)
),
ithMatrix(NI,NJ,Pattern,P),
not(var(P)),
P == X,
checkPatternAllVars(I,J,I,J,NI,NJ,Pattern), %check if in the pattern nothing in that path (except extremities) is not a variable
checkMatrixLightenUp(I,J,I,J,NI,NJ,Matrix,Matrix2). % check if in the matrix nothing in that path is lighten up already and light up pixels
% checkMatrixLightenUp/8
% checkMatrixLightenUp(+StartI,+StartJ,+I,+J,+FinalI,+FinalJ,+Matrix,-Matrix2)
% checkMatrixLightenUp(1,1,1,1,1,3,[[_,_,_],[_,_,_],[_,_,_]],Matrix2).
% checkMatrixLightenUp(1,1,1,1,1,3,[[_,'*',_],[_,_,_],[_,_,_]],Matrix2).
% checkMatrixLightenUp(1,1,1,1,3,1,[[_,_,_],[_,_,_],[_,_,_]],Matrix2).
% checkMatrixLightenUp(1,1,1,1,3,1,[[_,_,_],['*',_,_],[_,_,_]],Matrix2).
% checkMatrixLightenUp(1,1,1,1,3,1,[[_,_,_],[_,_,_],['*',_,_]],Matrix2).
checkMatrixLightenUp(_,_,FinalI,FinalJ,FinalI,FinalJ,Matrix2,Matrix2):-
ithMatrix(FinalI,FinalJ,Matrix2,X),
var(X),
X = '*'.
checkMatrixLightenUp(StartI,StartJ,I,J,FinalI,FinalJ,Matrix,Matrix2):-
ithMatrix(I,J,Matrix,X),
var(X),
X = '*',
(
I == FinalI
-> (
NJ is J + 1,
NI is I
)
; (
NJ is J,
NI is I + 1
)
),
checkMatrixLightenUp(StartI,StartJ,NI,NJ,FinalI,FinalJ,Matrix,Matrix2).
% checkPatternAllVars/7
% checkPatternAllVars(+StartI,+StartJ,+I,+J,+FinalI,+FinalJ,+Pattern)
% checkPatternAllVars(1,1,1,1,1,3,[[3,_,3],[_,_,_],[3,_,_]]).
% checkPatternAllVars(1,1,1,1,1,3,[[3,2,3],[_,_,_],[3,_,_]]).
% checkPatternAllVars(1,1,1,1,3,1,[[3,_,_],[_,_,_],[3,_,_]]).
% checkPatternAllVars(1,1,1,1,3,1,[[3,_,_],[2,_,_],[3,_,_]]).
checkPatternAllVars(_,_,FinalI,FinalJ,FinalI,FinalJ,_Pattern).
checkPatternAllVars(StartI,StartJ,I,J,FinalI,FinalJ,Pattern):-
(
( I \= StartI;J \= StartJ )
-> (
ithMatrix(I,J,Pattern,P),
var(P)
)
; 1 == 1
),
(
I == FinalI
-> (
NJ is J + 1,
NI is I
)
; (
NJ is J,
NI is I + 1
)
),
checkPatternAllVars(StartI,StartJ,NI,NJ,FinalI,FinalJ,Pattern).
% next/6
% next(+N,+M,+I,+J,-NI,-NJ)
% next(4,3,1,1,NI,NJ).
% next(4,3,1,3,NI,NJ).
% next(4,3,4,3,NI,NJ).
next(_N,M,I,J,NI,NJ):-
J < M,
!,
NJ is J + 1,
NI = I.
next(_N,M,I,J,NI,NJ):-
J == M,
NI is I + 1,
NJ is 1.
% printMatrix/1
% printMatrix([[*,_,*],[*,_,*]]).
printMatrix([]).
printMatrix([Row|T]):-
printRow(Row),
printMatrix(T).
printRow([]):-
nl.
printRow([H|T]):-
( H == '*' -> write('*'); write(' ') ),
printRow(T).
transformPixels([],[]).
transformPixels([H1|T1],[Row|T2]):-
H1=..[pixels|Row],
transformPixels(T1,T2).
% createMatrix/3
% createMatrix(+N,+M,-Matrix)
% createMatrix(3,4,Matrix).
createMatrix(1,M,[Row]):-
createRow(M,Row).
createMatrix(N,M,[Row|RestMatrix]):-
N > 1,
createRow(M,Row),
N1 is N - 1,
createMatrix(N1,M,RestMatrix).
% createRow/2
% createRow(+M,-Row)
% createRow(4,Row).
createRow(1,[_]).
createRow(M,[_|RestRow]):-
M > 1,
M1 is M - 1,
createRow(M1,RestRow).
% ithMatrix/4
% ithMatrix(+I,+J,?Matrix,?X)
% ithMatrix(2,2,[[1,2,3],[4,5,6],[7,8,9]],X).
% M = [[_,_,_],[_,_,_],[_,_,_]], ithMatrix(2,2,M,5).
ithMatrix(1,J,[Row|_],X):-
ith(J,Row,X).
ithMatrix(I,J,[_|RestMatrix],X):-
number(I),
I > 1,
I1 is I - 1,
ithMatrix(I1,J,RestMatrix,X).
% ith/3
% ith(+I,+L,-X)
% ith(2,[1,2,3],X).
ith(1,[H|_],H).
ith(I,[_|RestRow],X):-
number(I),
I > 1,
I1 is I - 1,
ith(I1,RestRow,X).
% lengthList/2
% lengthList(L,S)
lengthList([],0).
lengthList([_|T],S):-
lengthList(T,S1),
S is S1 + 1.
%%%%%%%%%%%%%chain.pl%%%%%%%%%%%%
large(N,P,T):-
listlen(N,List),
findall((P1,T1),(
position(N,P1),
find_T(P1,List,List,T1)),M),
find_max(M,(P,T)).
% create a random list of length N
listlen(0,[]):-!.
listlen(N,[X|List]):-
X is 100+N,
N1 is N-1,
listlen(N1,List).
createlist(0,[]):-!.
createlist(N,[X|List]):-
X = N,
N1 is N-1,
createlist(N1,List).
% create a position list of size N
position(N,X):-
createlist(N,List),
permutation(List,X).
find_T(Pos,List,L,T):-
apply_perm(Pos,List,List1),
(List1=L->
T=1;
find_T(Pos,List1,L,T1),
T is T1+1).
:- import ith/3 from basics.
apply_perm([],_,[]):-!.
apply_perm([N|Ns],List,[X|Xs]):-
ith(N,List,X),
apply_perm(Ns,List,Xs).
find_max([(X,Y)],(X,Y)):-!.
find_max([(X,Y)|L],(A,B)):-
find_max(L,(C,D)),
(Y>D->
A=X,B=Y;
A=C,B=D).
permutation([],[]).
permutation([X|L],P):-permutation(L,L1),insert(X,L1,P).
insert(X,L,[X|L]).
insert(X,[Y|L],[Y|L1]):-
insert(X,L,L1).
%%%%%%%%%%%%%flip.pl%%%%%%%%%%%%
% flip/4
% flip(+L, -MaxSum, -MinFlips, -MaxFlips)
% ?- flip([[1,2],[1,2]], MaxSum, MinFlips,MaxFlips). -> MaxSum = 174, MinFlips = 2, MaxFlips = 2
% ?- flip([[1,2,3,4,5],[2,3,4,5,6],[0,0,9,3,4],[7,6,5,4,3],[3,0,3,0,3]], MaxSum, MinFlips,MaxFlips). -> MaxSum = 409604, MinFlips = 4, MaxFlips = 6
flip(L, MaxSum, MinFlips,MaxFlips):-
lengthList(L,Size),
createList(Size,Rows),
createList(Size,Columns),
findall(
f(Sum,NoFlips),
apply_flip(L,Rows,Columns,_L2,Sum,NoFlips),
RawResults
),
findMaxSum(RawResults,0,[],MaxSum,SelectedResults1),
SelectedResults1 = [StartMin|_],
findMin(SelectedResults1,StartMin,MinFlips),
findMax(SelectedResults1,0,MaxFlips).
:- table(apply_flip/6).
% apply_flip/6
% apply_flip(L1,Rows,Columns,L2,Sum,NoFlips)
% ?- apply_flip([[1,2,3,4,5],[2,3,4,5,6],[0,0,9,3,4],[7,6,5,4,3],[3,0,3,0,3]], [1,2,3,4,5], [1,2,3,4,5], L2,Sum,NoFlips).
% ?- apply_flip([[1,2],[1,2]], [1,2], [1,2], L2,Sum,NoFlips).
% ?- apply_flip([[1,2,3],[1,2,3],[1,2,3]], [1,2,3], [1,2,3], L2,Sum,NoFlips),fail.
% ?- apply_flip([[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]], [1,2,3,4], [1,2,3,4], L2,Sum,NoFlips),fail.
% ?- apply_flip([[1,2,3,4,5],[1,2,3,4,5],[1,2,3,4,5],[1,2,3,4,5],[1,2,3,4,5]], [1,2,3,4,5], [1,2,3,4,5], L2,Sum,NoFlips),fail.
apply_flip(L1,Rows,Columns,L2,Sum,NoFlips):-
select(Row,Rows,RestRows),
row_flip(L1,Row,TempL),
(
(
L2 = TempL,
sumMatrix(L2,Sum),
NoFlips = 1
);
(
apply_flip(TempL,RestRows,Columns,L2,Sum,NoFlips1),
NoFlips is NoFlips1 + 1
)
).
apply_flip(L1,Rows,Columns,L2,Sum,NoFlips):-
select(Column,Columns,RestColumns),
column_flip(L1,Column,TempL),
(
(
L2 = TempL,
sumMatrix(L2,Sum),
NoFlips = 1
);
(
apply_flip(TempL,Rows,RestColumns,L2,Sum,NoFlips1),
NoFlips is NoFlips1 + 1
)
).
% sumMatrix/2
% sumMatrix(+L,-Sum)
% ?- sumMatrix([[1,2,3,4,5],[2,3,4,5,6],[0,0,9,3,4],[7,6,5,4,3],[3,0,3,0,3]], Sum).
sumMatrix([],0).
sumMatrix([H|T],Sum):-
list2no(H,0,S1),
sumMatrix(T,S2),
Sum is S1 + S2.
% list2no/2
% list2no(+L,-N)
% ?- list2no([1,2,3,4,5],N).
list2no(L,N):-
list2no(L,0,N).
list2no([],Partial,Partial).
list2no([H|T],Partial,N):-
Partial2 is (Partial * 10) + H,
list2no(T,Partial2,N).
% row_flip/3
% row_flip(+L1, +R,-L2)
% ?- row_flip([[1,2,3,4,5],[2,3,4,5,6],[0,0,9,3,4],[7,6,5,4,3],[3,0,3,0,3]], 3, L2).
row_flip([H1|T],1,[H2|T]):-
!, % flip first row
flip_row_elem(H1,H2).
row_flip([H|T1],R,[H|T2]):-
1 < R,
R1 is R - 1,
row_flip(T1,R1,T2).
% flip_row_elem/2
% flip_row_elem(+L1,-L2)
% ?- flip_row_elem([1,2,3],L2).
flip_row_elem([],[]).
flip_row_elem([H1|T1],[H2|T2]):-
flip_row_elem(T1,T2),
H2 is 9 - H1.
% column_flip/3
% column_flip(+L1, +C,-L2)
% ?- column_flip([[1,2,3,4,5],[2,3,4,5,6],[0,0,9,3,4],[7,6,5,4,3],[3,0,3,0,3]], 3, L2).
column_flip([H1|T1],C,[H2|T2]):-
flip_column_elem(H1,C,H2),
column_flip(T1,C,T2).
column_flip([],_,[]).
% flip_column_elem/3
% flip_column_elem(+L1,?C,-L2)
% ?- flip_column_elem([1,2,3],2,L2).
% ?- flip_column_elem([1,2,3],I,L2).
flip_column_elem([H1|T],1,[H2|T]):-
H2 is 9 - H1.
flip_column_elem([H|T1],C,[H|T2]):-
number(C), C > 1,
C1 is C - 1,
flip_column_elem(T1,C1,T2).
flip_column_elem([H|T1],C,[H|T2]):-
not(number(C)),
flip_column_elem(T1,C1,T2),
C is C1 + 1.
% findMaxSum/5
% findMaxSum(+RawResults,+PartialMax,+PartialResults,-MaxSum,-SelectedResults1)
% ?- findMaxSum([f(99, 1), f(174, 2), f(34, 3), f(24, 4), f(164, 3), f(24, 4), f(99, 2)],0,[],MaxSum,SelectedResults1).
findMaxSum([],PartialMax,PartialResults,PartialMax,PartialResults).
findMaxSum([f(Sum,NoFlips)|T],PartialMax,_PartialResults,MaxSum,SelectedResults):-
Sum > PartialMax,
!,
findMaxSum(T,Sum,[NoFlips],MaxSum,SelectedResults).
findMaxSum([f(Sum,NoFlips)|T],PartialMax,PartialResults,MaxSum,SelectedResults1):-
Sum == PartialMax,
!,
findMaxSum(T,PartialMax,[NoFlips|PartialResults],MaxSum,SelectedResults1).
findMaxSum([f(Sum,_NoFlips)|T],PartialMax,PartialResults,MaxSum,SelectedResults1):-
Sum < PartialMax,
!,
findMaxSum(T,PartialMax,PartialResults,MaxSum,SelectedResults1).
% lengthList/2
% lengthList(L,S)
lengthList([],0).
lengthList([_|T],S):-
lengthList(T,S1),
S is S1 + 1.
% ith/3
% ith(?I,?List,?Elem)
%:- ith(1,[1,2,3],E). -> E = 1
%:- ith(I,[1,2,3],E). -> I=1,E=1; I=2,E=2; I=3,E=3;
ith(I,[H|T],Elem):-
number(I),
!,
( I == 1 -> Elem = H
; (
I1 is I - 1,
ith(I1, T,Elem)
)
).
ith(I,[H|_],Elem):-
% I is a variable
Elem = H,
I = 1.
ith(I,[_|T],Elem):-
% I is a variable
ith(I1, T,Elem),
I is I1 + 1.
% member/2
member(H,[H|_]).
member(H,[_|T]):-
member(H,T).
% createList/2
% createList(+Size,-L)
% ?- createList(10,L).
createList(Size,L):-
createList(Size,[],L).
createList(0,L,L).
createList(Size,PL,R):-
number(Size),
Size > 0,
Size1 is Size - 1,
createList(Size1,[Size|PL],R).
% select/2
% select(?X,?L,?Rest)
% ?- select(X,[1,2,3,4,5],Rest).
select(H,[H|T],T).
select(X,[H|T1],[H|T2]):-
select(X,T1,T2).
% findMax/2
% findMax(+L,-M)
% ?- findMax([1,2,3],0,Max).
findMax([],PartialMax,PartialMax).
findMax([H|T],PartialMax,Max):-
H > PartialMax,
!,
findMax(T,H,Max).
findMax([_|T],PartialMax,Max):-
findMax(T,PartialMax,Max).
% findMin/2
% findMin(+L,-M)
% ?- findMin([1,2,3],100,Min).
findMin([],PartialMin,PartialMin).
findMin([H|T],PartialMin,Min):-
H < PartialMin,
!,
findMin(T,H,Min).
findMin([_|T],PartialMin,Min):-
findMin(T,PartialMin,Min).
%%%%%%%%%%%%%dice.pl%%%%%%%%%%%%
% dice([arc(a,b), arc(b,a), arc(b,z), arc(z,b)],[3,5],N).
% dice([arc(a,b), arc(b,z)],[4,2,6],N).
% dice([arc(a,b), arc(b,c), arc(c,z)], [1],N).
% dice([arc(a,b), arc(c,z), arc(a,d), arc(d,e), arc(e,d)], [1],N).
% dice([arc(a,b), arc(b,z), arc(a,z)],[1],N).
% dice([arc(a,b), arc(b,c), arc(c,z), arc(a,d), arc(d,z)],[1],N).
dice(Edges,Throws,Min):-
findall(Path,reach(a,z,Edges,Throws,1,Path,_NewThrowPosition),L),
list2lenghts(L,LL),
LL = [InitialMin|_],
findMin(LL,InitialMin,Min1),
Min is Min1 - 1.
list2lenghts([],[]).
list2lenghts([H|T1],[HL|T2]):-
lengthList(H,HL),
list2lenghts(T1,T2).
% reach/7
% reach(+X,+Y,+Graph,+Throws,+ThrowPosition,-Path,-NewThrowPosition)
% reach(a,z,[arc(a,b), arc(b,a), arc(b,z)],[1],1,Path,NewThrowPosition).
% reach(a,Y,[arc(a,b), arc(b,a), arc(b,z)],[1],1,Path,NewThrowPosition).
% reach(X,Y,[arc(a,b), arc(b,a), arc(b,z)],[1],1,Path,NewThrowPosition).
% findall(Path,reach(X,Y,[arc(a,b), arc(b,a), arc(b,z)],[1],1,Path,NewThrowPosition),L).
:- table(reach/7).
reach(X,Y,Edges,Throws,ThrowPosition,[f(X,ThrowPosition),f(Y,NewThrowPosition)],NewThrowPosition):-
ith(ThrowPosition,Throws,Steps),
goto(X,Y,Edges,Steps),
lengthList(Throws,Len),
circularIncrement(ThrowPosition,Len,NewThrowPosition).
reach(X,Y,Edges,Throws,ThrowPosition,Path,NewThrowPosition):-
reach(X,Z,Edges,Throws,ThrowPosition,Path1,TempThrowPosition),
ith(TempThrowPosition,Throws,Steps),
goto(Z,Y,Edges,Steps),
tnot(member(f(Y,TempThrowPosition),Path1)),
append(Path1,[f(Y,TempThrowPosition)],Path),
lengthList(Throws,Len),
circularIncrement(TempThrowPosition,Len,NewThrowPosition).
% circularIncrement(+Pos,+Max,-NewPos)
% circularIncrement(1,2,NewPos).
% circularIncrement(2,2,NewPos).
%:- table(circularIncrement/3).
circularIncrement(Pos,Max,NewPos):-
Pos == Max,
NewPos = 1.
circularIncrement(Pos,Max,NewPos):-
\+(Pos = Max),
NewPos is Pos + 1.
:- table(myEqual/2).
myEqual(X,X).
% goto(+X,+Y,+Graph,+Steps)
% goto(a,z,[arc(a,b), arc(b,a), arc(b,z)],2).
% goto(a,Y,[arc(a,b), arc(b,a), arc(b,z)],2).
% goto(X,Y,[arc(a,b), arc(b,a), arc(b,z)],2).
% findall(path(X,Y),goto(X,Y,[arc(a,b), arc(b,a), arc(b,z)],2),L).
:- table(goto/4).
goto(X,Y,Edges,1):-
member(arc(X,Y),Edges).
goto(X,Y,Edges,Steps):-
Steps > 1,
Steps1 is Steps - 1,
goto(X,Z,Edges,Steps1),
member(arc(Z,Y),Edges).
% member/2
:- table(member/2).
member(H,[H|_]).
member(H,[_|T]):-
member(H,T).
% append/3
:- table(append/3).
append([],L,L).
append([H|T],L,[H|R]):-
append(T,L,R).
% ith/3
% ith(?I,?List,?Elem)
% ith(1,[1,2,3],E).
% ith(I,[1,2,3],E).
:- table(ith/3).
ith(1,[H|_],H).
ith(I,[_|T],Elem):-
number(I),
I > 1,
I1 is I - 1,
ith(I1, T,Elem).
% lengthList/2
% lengthList(L,S)
lengthList([],0).
lengthList([_|T],S):-
lengthList(T,S1),
S is S1 + 1.
% findMin/3
% findMin(+L,+PartialMin,-M)
% ?- findMin([1,2,3],100,Min).
findMin([],PartialMin,PartialMin).
findMin([H|T],PartialMin,Min):-
H < PartialMin,
!,
findMin(T,H,Min).
findMin([_|T],PartialMin,Min):-
findMin(T,PartialMin,Min).
%%%%%%%%%%%%%end submission%%%%%%%%%%%%