Skip to content
Snippets Groups Projects
solution01.pl 4.22 KiB
Newer Older
  • Learn to ignore specific revisions
  • %%usage of testcases: simply typing in <name>(). and it should be true
    %%testcases only show that one example works, you should create more of them for yourself!
    %%So there is no guarantee that these testcases ensure that your implementation is correct!
    
    %%==========Problem 1.1===============
    %TODO: implement removeDuplicates(List,ListWithoutDuplicates)
    delete([],_,[]).
    delete([X],X,[]).
    delete([Head|Tail],Head,Result):-
    	delete(Tail,Head,Result).
    delete([Head|Tail],X,[Head|Result]):-
    	Head \= X,
    	delete(Tail,X,Result).
    
    removeDuplicates([],[]).
    removeDuplicates([Head|Tail],[Head|Tail2]):-
    	delete(Tail,Head,Result),
    	removeDuplicates(Result,Tail2).
    
    %testcase
    testcase_remove():-
    	removeDuplicates([1,1,1,1,2,2,3,4,1,2,7],[1, 2, 3, 4, 7]).
    %--------------------------------------------------------------------
    %TODO: implement myReverse(List,ReversedList)
    
    append([],List2,List2).
    append([Head|Tail],List2,[Head|Result]):-
    	append(Tail,List2,Result).
    
    myReverse([],[]).
    myReverse([Head|Tail],ReversedList):-
    	myReverse(Tail,TempList),
    	append(TempList,[Head],ReversedList).
    
    %testcase
    testcase_reverse():-
    	myReverse([1,2,3,4,5],[5,4,3,2,1]).
    %--------------------------------------------------------------------
    %TODO: implement myPermutations(List,OnePossiblePermutationOfList)
    %note: by re-evaluating the function (using the space bar or ";"), one gets all possible permutations
    
    buildRandom(List,Element,[Element|List]).
    buildRandom([Head|Tail],Element,[Head|ResultList]):-
    	buildRandom(Tail,Element,ResultList).
    
    
    myPermutations([],[]).
    myPermutations([Head|Tail],Result):-
    	myPermutations(Tail,TempList),
    	buildRandom(TempList,Head,Result).
    
    %testcase:
    testcase_permut(X):-
    	myPermutations([1,2,3,4],X).
    %confirm yourself that your implementation outputs all 16 permutations and produces no doubles
    %--------------------------------------------------------------------
    %TODO: implement zip(ListA,ListB,ZippedList)
    % the length difference of ListA and ListB is at most 1
    % ZippedList is a list of Lists with length 2 (the last element may have length 1)
    zip([X],[],[[X]]).
    zip([],[X],[[X]]).
    zip([A],[B],[[A,B]]).
    zip([Head1|Tail1],[Head2|Tail2],Result):-
    	zip(Tail1,Tail2,TempList),
    	append([[Head1,Head2]],TempList,Result).
    
    
    
    
    %testcase
    testcase_zip():-
    	zip([1,2],[3,4,5],[[1,3],[2,4],[5]]).
    
    %%==========Problem 1.2===============
    %Please see the exercise sheet for detailed instructions about what these functions do
    
    tree(nil).
    tree(_,L,R):-
    	tree(L),
    	tree(R).
    
    %TODO implement construct(List,Tree)
    construct(List,Tree):-
    	insert(List,nil,Tree).
    
    insert([],Tree,Tree).
    insert([Head|Tail],TempTree,Tree):-
    	insert_help(Head,TempTree,NewTempTree),
    	insert(Tail,NewTempTree,Tree).
    
    insert_help(X, nil, tree(X,nil,nil)).
    insert_help(X,tree(Y,L,R), tree(Y,L,NewTree)):-
    	X>Y,
    	insert_help(X,R,NewTree).
    insert_help(X,tree(Y,L,R), tree(Y,NewTree,R)):-
    	X<Y,
    	insert_help(X,L,NewTree).
    
    
    %testcase
    testcase_construct():-
    	construct([5,2,4,1,3],tree(5,tree(2,tree(1,nil,nil),tree(4,tree(3,nil,nil),nil)),nil)).
    %--------------------------------------------------------------------
    %TODO: implement count_leaves(Tree,NumberOfLeaves)
    
    count_leaves(nil,0).
    count_leaves(tree(_,nil,nil),1):-!.
    count_leaves(tree(_,L,R),Result):-
    	count_leaves(L,Temp1),
    	count_leaves(R,Temp2),
    	Result is Temp1 + Temp2.
    
    %testcase
    testcase_count():-
    	count_leaves(tree(3,tree(1,nil,tree(2,nil,nil)),nil),1).
    %TODO: Use it to test how cost efficient your previous function is (in terms of the
    % structure that you obtain). What can you observe for larger lists of numbers?
    % Answer these questions as a comment or hand in a separate file
    
    
    
    %--------------------------------------------------------------------
    %TODO: implement symmetric(Tree) that is true, if the Tree is symmetric
    
    %symmetric(tree(_,nil,nil)).
    symmetric(tree(_,L,R)):-
    	mirrored(L,R).
    
    mirrored(nil,nil).
    mirrored(tree(_,L1,R1), tree(_,L2,R2)):-
    	mirrored(L1,R2),
    	mirrored(R1,L2).
    
    
    %testcase
    testcase_symm():-
    	construct([5,2,3,7,6],X),
    	symmetric(X).
    
    %=========================================
    %% total test
    test(X):-
    	testcase_remove(),
    	testcase_reverse(),
    	testcase_zip(),
    	testcase_construct(),
    	testcase_count(),
    	testcase_symm(),
    	writeln("everything correct up to myPermutations,"),
    	writeln("now all permutations of [1,2,3,4]:"),
    	testcase_permut(X).