Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
%%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).