<div class="notebook"> <div class="nb-cell markdown" name="md5"> ## Assignment 1 ### Problem 1.1 </div> <div class="nb-cell program" name="p4"> myReverse(Ls1,Ls2):- myReverseAcc(Ls1,[],Ls2). myReverseAcc([],X,X). myReverseAcc([X|Y],Z,W) :- myReverseAcc(Y,[X|Z],W). removeDuplicates([], []). removeDuplicates([H|T],[H|R]):- delete(H,T,S), removeDuplicates(S,R). delete(_,[],[]). delete(X,[X|T],R):- delete(X,T,R). delete(X, [H|T], [H|R]):- \+(X=H), delete(X,T,R). myPermutations([],[]). myPermutations([H|T],P):-myPermutations(T,Q), takeout(H,P,Q). takeout(X,[X|T],T). takeout(X,[H|T1],[H|T2]):- \+(X=H),takeout(X,T1,T2). </div> <div class="nb-cell query" name="q3"> myPermutations([1,2,3,4],P) </div> <div class="nb-cell markdown" name="md7"> ### Problem 1.2 Binary tree: tree(n,t1,t2) where n is a natural number and t1, t2 are binary trees; nil is the empty tree. </div> <div class="nb-cell program" name="p5"> construct(Ls,Tree):- constructAcc(Ls,Tree,nil). add(X,nil,tree(X,nil,nil)). add(X,tree(Root,L,R),tree(Root,L1,R)):- X @< Root, add(X,L,L1). add(X,tree(Root,L,R),tree(Root,L,R1)):- X @> Root, add(X,R,R1). constructAcc([],T,T). constructAcc([N|Ns],T,A):- add(N,A,A1), constructAcc(Ns,T,A1) . </div> <div class="nb-cell query" name="q5"> construct([a,b,c,d,e],X) </div> <div class="nb-cell markdown" name="md1"> ## Presence Problem II In this tutorial, we are going to generate trees for Problem 2.2 (you can use them for testing). You already saw a binary tree implementation in assignment 1. However, for search algorithms we need a general tree implementation to represent the search space. As in Problem 2.2, a tree consists of a root labelled V (a string) and a list of its children TS (which are in turn trees). Leaves are the trees with an empty list of children: </div> <div class="nb-cell program" name="p2"> istree(tree(V,TS)) :- string(V), istreelist(TS). istreelist([]). istreelist([T|TS]) :- istree(T), istreelist(TS). </div> <div class="nb-cell markdown" name="md2"> We are going to generate trees of depth D, with a random number N of children where 0<=N<5 and labels taken from a list. We will start with a predicate that generates input lists for us. We are going to use Prolog's internal predicate number_string/2 and is/2 predicates. </div> <div class="nb-cell program" data-background="true" name="p3"> makeLabels(F,F,[]). makeLabels(F,T,[L|Ls]):- number_string(F,L), Fi is F+1, makeLabels(Fi,T,Ls),!. </div> <div class="nb-cell query" name="q4"> makeLabels(0,100,Ls). </div> <div class="nb-cell markdown" name="md3"> Can you think of a tail for the following clause (hint: random_between/3 is an internal prolog predicate to generate a random integer)? </div> <div class="nb-cell program" data-background="true" name="p6"> % makeTree(T,D,Ls,Ls2) holds if T is a tree of depth at most D with a random number 0<=N<5 of children % node labels are taken from the list Ls, and the list Ls2 of remaining labels is returned makeTree(tree(V,TS),D,[L|Ls],Ls2):- V=L, random_between(0,4,N), makeTreelist(N,TS,D,Ls,Ls2). % number of remaining children is 0 makeTreelist(0,[],_,Ls,Ls):-!. % depth has become 0. makeTreelist(_,[],0,Ls,Ls):-!. % to make N trees, we make a tree T of random depth D2 below D and then make N-1 more trees TS makeTreelist(N,[T|Ts],D,Ls1, Ls3):- ND is D-1, random_between(0,ND,D2), makeTree(T,D2,Ls1, Ls2), NN is N-1, makeTreelist(NN,Ts,D,Ls2,Ls3). </div> <div class="nb-cell query" name="q1"> makeTree(A, 2, [c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,z], _). </div> <div class="nb-cell query" name="q2"> makeLabels(0,100,Ls), makeTree(A, 6, Ls, _). </div> </div>