summaryrefslogtreecommitdiff
path: root/prolog/problems/trees
diff options
context:
space:
mode:
Diffstat (limited to 'prolog/problems/trees')
-rw-r--r--prolog/problems/trees/deletebt_3/common.py17
-rw-r--r--prolog/problems/trees/deletebt_3/en.py14
-rw-r--r--prolog/problems/trees/depthbt_2/common.py17
-rw-r--r--prolog/problems/trees/depthbt_2/en.py12
-rw-r--r--prolog/problems/trees/insertbt_3/common.py20
-rw-r--r--prolog/problems/trees/insertbt_3/en.py15
-rw-r--r--prolog/problems/trees/maxt_2/common.py25
-rw-r--r--prolog/problems/trees/maxt_2/en.py12
-rw-r--r--prolog/problems/trees/memberbt_2/common.py13
-rw-r--r--prolog/problems/trees/memberbt_2/en.py14
-rw-r--r--prolog/problems/trees/membert_2/common.py18
-rw-r--r--prolog/problems/trees/membert_2/en.py14
-rw-r--r--prolog/problems/trees/mirrorbt_2/common.py12
-rw-r--r--prolog/problems/trees/mirrorbt_2/en.py12
-rw-r--r--prolog/problems/trees/numberbt_2/common.py13
-rw-r--r--prolog/problems/trees/numberbt_2/en.py12
-rw-r--r--prolog/problems/trees/tolistbt_2/common.py17
-rw-r--r--prolog/problems/trees/tolistbt_2/en.py12
18 files changed, 269 insertions, 0 deletions
diff --git a/prolog/problems/trees/deletebt_3/common.py b/prolog/problems/trees/deletebt_3/common.py
new file mode 100644
index 0000000..76550f6
--- /dev/null
+++ b/prolog/problems/trees/deletebt_3/common.py
@@ -0,0 +1,17 @@
+id = 137
+group = 'trees'
+number = 47
+visible = True
+facts = None
+
+solution = '''\
+deleteBT(X, b(nil, X, nil), nil).
+deleteBT(X, b(b(Ls, E, Rs), X, R), b(L, E, R)) :-
+ deleteBT(E, b(Ls, E, Rs), L).
+deleteBT(X, b(L, X, b(Ls, E, Rs)), b(L, E, R)) :-
+ deleteBT(E, b(Ls, E, Rs), R).
+deleteBT(X, b(L, E, R), b(L1, E, R)) :-
+ deleteBT(X, L, L1).
+deleteBT(X, b(L, E, R), b(L, E, R1)) :-
+ deleteBT(X, R, R1).
+'''
diff --git a/prolog/problems/trees/deletebt_3/en.py b/prolog/problems/trees/deletebt_3/en.py
new file mode 100644
index 0000000..557efaa
--- /dev/null
+++ b/prolog/problems/trees/deletebt_3/en.py
@@ -0,0 +1,14 @@
+id = 137
+name = 'deleteBT/3'
+slug = 'delete an element from a binary tree'
+
+description = '''\
+<p><code>deleteBT(X, T, NewT)</code>: the binary tree <code>NewT</code> is obtained from <code>T</code> by deleting one occurence of the element <code>X</code>. If <code>X</code> is not a leaf node, the root of one of its subtrees is moved up. Your code should generate all valid solutions.</p>
+<pre>
+ ?- deleteBT(1, b(b(b(nil,4,nil),2,b(nil,6,nil)),1,b(nil,3,b(nil,5,nil))), T).
+ T = b(b(nil,4,b(nil,6,nil)),2,b(nil,3,b(nil,5,nil))) ;
+ T = b(b(b(nil,4,nil),6,nil),2,b(nil,3,b(nil,5,nil))) ;
+ T = b(b(b(nil,4,nil),2,b(nil,6,nil)),3,b(nil,5,nil)).
+</pre>'''
+
+hint = {}
diff --git a/prolog/problems/trees/depthbt_2/common.py b/prolog/problems/trees/depthbt_2/common.py
new file mode 100644
index 0000000..9e26f21
--- /dev/null
+++ b/prolog/problems/trees/depthbt_2/common.py
@@ -0,0 +1,17 @@
+id = 140
+group = 'trees'
+number = 45
+visible = True
+facts = None
+
+solution = '''\
+depthBT(nil, 0).
+depthBT(b(L, _, R), D) :-
+ depthBT(L, DL),
+ depthBT(R, DR),
+ (DL >= DR,
+ D is DL + 1
+ ;
+ DL < DR,
+ D is DR + 1).
+'''
diff --git a/prolog/problems/trees/depthbt_2/en.py b/prolog/problems/trees/depthbt_2/en.py
new file mode 100644
index 0000000..37cb3cd
--- /dev/null
+++ b/prolog/problems/trees/depthbt_2/en.py
@@ -0,0 +1,12 @@
+id = 140
+name = 'depthBT/2'
+slug = 'find the depth of a binary tree'
+
+description = '''\
+<p><code>depthBT(T, D)</code>: <code>D</code> is the depth of the binary tree <code>T</code>.</p>
+<pre>
+ ?- depthBT(b(b(b(nil,4,nil),2,b(nil,6,nil)),1,nil), D).
+ D = 3.
+</pre>'''
+
+hint = {}
diff --git a/prolog/problems/trees/insertbt_3/common.py b/prolog/problems/trees/insertbt_3/common.py
new file mode 100644
index 0000000..efbfb7d
--- /dev/null
+++ b/prolog/problems/trees/insertbt_3/common.py
@@ -0,0 +1,20 @@
+id = 138
+group = 'trees'
+number = 48
+visible = True
+facts = None
+
+solution = '''\
+deleteBT138(X, b(nil, X, nil), nil).
+deleteBT138(X, b(b(Ls, E, Rs), X, R), b(L, E, R)) :-
+ deleteBT138(E, b(Ls, E, Rs), L).
+deleteBT138(X, b(L, X, b(Ls, E, Rs)), b(L, E, R)) :-
+ deleteBT138(E, b(Ls, E, Rs), R).
+deleteBT138(X, b(L, E, R), b(L1, E, R)) :-
+ deleteBT138(X, L, L1).
+deleteBT138(X, b(L, E, R), b(L, E, R1)) :-
+ deleteBT138(X, R, R1).
+
+insertBT(X, T, NewT) :-
+ deleteBT138(X, NewT, T).
+'''
diff --git a/prolog/problems/trees/insertbt_3/en.py b/prolog/problems/trees/insertbt_3/en.py
new file mode 100644
index 0000000..202df0a
--- /dev/null
+++ b/prolog/problems/trees/insertbt_3/en.py
@@ -0,0 +1,15 @@
+id = 138
+name = 'insertBT/3'
+slug = 'insert an element into a binary tree'
+
+description = '''\
+<p><code>insertBT(X, T, NewT)</code>: the binary tree <code>NewT</code> is obtained from <code>T</code> by inserting the element <code>X</code> at a certain position. This is the opposite of the predicate <code>deleteBT/3</code>. Your code should generate all valid solutions.</p>
+<pre>
+ ?- insertBT(2, b(nil,1,nil), T).
+ T = b(b(nil,1,nil),2,nil) ;
+ T = b(nil,2,b(nil,1,nil)) ;
+ T = b(b(nil,2,nil),1,nil) ;
+ T = b(nil,1,b(nil,2,nil)).
+</pre>'''
+
+hint = {}
diff --git a/prolog/problems/trees/maxt_2/common.py b/prolog/problems/trees/maxt_2/common.py
new file mode 100644
index 0000000..be51d46
--- /dev/null
+++ b/prolog/problems/trees/maxt_2/common.py
@@ -0,0 +1,25 @@
+id = 143
+group = 'trees'
+number = 50
+visible = True
+facts = None
+
+solution = '''\
+max143([X], X).
+max143([H|T], Max):-
+ max143(T, Max1),
+ ( H > Max1, Max is H
+ ;
+ H =< Max1, Max is Max1 ).
+
+maxT(t(E), E) :- !.
+maxT(Tree, Max) :-
+ Tree =.. [t, E|SubTrees],
+ getMaxElems(SubTrees, MaxElems),
+ max143([E|MaxElems], Max).
+
+getMaxElems([], []).
+getMaxElems([SubTree|SubTrees], [MaxElem|MaxElems]) :-
+ maxT(SubTree, MaxElem),
+ getMaxElems(SubTrees, MaxElems).
+'''
diff --git a/prolog/problems/trees/maxt_2/en.py b/prolog/problems/trees/maxt_2/en.py
new file mode 100644
index 0000000..3e15b34
--- /dev/null
+++ b/prolog/problems/trees/maxt_2/en.py
@@ -0,0 +1,12 @@
+id = 143
+name = 'maxT/2'
+slug = 'find the greatest element in a tree'
+
+description = '''\
+<p><code>maxT(Tree, Max)</code>: <code>Max</code> is the greatest element in the tree <code>Tree</code>.</p>
+<pre>
+ ?- maxT(t(1, t(2), t(3)), Max).
+ Max = 3.
+</pre>'''
+
+hint = {}
diff --git a/prolog/problems/trees/memberbt_2/common.py b/prolog/problems/trees/memberbt_2/common.py
new file mode 100644
index 0000000..f0ae0bd
--- /dev/null
+++ b/prolog/problems/trees/memberbt_2/common.py
@@ -0,0 +1,13 @@
+id = 135
+group = 'trees'
+number = 42
+visible = True
+facts = None
+
+solution = '''\
+memberBT(X, b(_, X, _)).
+memberBT(X, b(L, _, _)) :-
+ memberBT(X, L).
+memberBT(X, b(_, _, R)) :-
+ memberBT(X, R).
+'''
diff --git a/prolog/problems/trees/memberbt_2/en.py b/prolog/problems/trees/memberbt_2/en.py
new file mode 100644
index 0000000..fcca1d9
--- /dev/null
+++ b/prolog/problems/trees/memberbt_2/en.py
@@ -0,0 +1,14 @@
+id = 135
+name = 'memberBT/2'
+slug = 'find elements in a binary tree'
+
+description = '''\
+<p><code>memberBT(X, T)</code>: <code>X</code> is an element of the binary tree <code>T</code>. A binary tree node is represented with the structure <code>b(L, E, R)</code>, where <code>L</code> and <code>R</code> are left and right subtrees, respectively, and <code>E</code> is the node's value. An empty tree is denoted by <code>nil</code>.</p>
+<pre>
+ ?- memberBT(X, b(b(nil,2,nil),1,b(nil,3,nil))).
+ X = 1 ;
+ X = 2 ;
+ X = 3.
+</pre>'''
+
+hint = {}
diff --git a/prolog/problems/trees/membert_2/common.py b/prolog/problems/trees/membert_2/common.py
new file mode 100644
index 0000000..177309f
--- /dev/null
+++ b/prolog/problems/trees/membert_2/common.py
@@ -0,0 +1,18 @@
+id = 142
+group = 'trees'
+number = 49
+visible = True
+facts = None
+
+solution = '''\
+memb142(X, [X|_]).
+memb142(X, [_|T]) :-
+ memb142(X, T).
+
+memberT(X, Tree) :-
+ Tree =.. [t, X|_].
+memberT(X, Tree) :-
+ Tree =.. [t, _|SubTrees],
+ memb142(SubTree, SubTrees),
+ memberT(X, SubTree).
+'''
diff --git a/prolog/problems/trees/membert_2/en.py b/prolog/problems/trees/membert_2/en.py
new file mode 100644
index 0000000..a6fdffb
--- /dev/null
+++ b/prolog/problems/trees/membert_2/en.py
@@ -0,0 +1,14 @@
+id = 142
+name = 'memberT/2'
+slug = 'find elements in a tree'
+
+description = '''\
+<p><code>memberT(X, T)</code>: <code>X</code> is an element of the tree <code>T</code>. A tree node is represented with the structure <code>t(E, T1, T2...)</code>, where <code>E</code> is the node's value, followed by any number of subtrees. An empty tree is denoted by <code>nil</code>.</p>
+<pre>
+ ?- memberT(X, t(3, t(1), t(2))).
+ X = 3 ;
+ X = 1 ;
+ X = 2.
+</pre>'''
+
+hint = {}
diff --git a/prolog/problems/trees/mirrorbt_2/common.py b/prolog/problems/trees/mirrorbt_2/common.py
new file mode 100644
index 0000000..dc8d337
--- /dev/null
+++ b/prolog/problems/trees/mirrorbt_2/common.py
@@ -0,0 +1,12 @@
+id = 136
+group = 'trees'
+number = 43
+visible = True
+facts = None
+
+solution = '''\
+mirrorBT(nil, nil).
+mirrorBT(b(L, X, R), b(NewR, X, NewL)) :-
+ mirrorBT(L, NewL),
+ mirrorBT(R, NewR).
+'''
diff --git a/prolog/problems/trees/mirrorbt_2/en.py b/prolog/problems/trees/mirrorbt_2/en.py
new file mode 100644
index 0000000..d44f463
--- /dev/null
+++ b/prolog/problems/trees/mirrorbt_2/en.py
@@ -0,0 +1,12 @@
+id = 136
+name = 'mirrorBT/2'
+slug = 'flip a binary tree horizontally'
+
+description = '''\
+<p><code>mirrorBT(T, NewT)</code>: the binary tree <code>NewT</code> is obtained from <code>T</code> by flipping it over the vertical axis through the root node.</p>
+<pre>
+ ?- mirrorBT(b(b(b(nil,4,nil),2,b(nil,5,nil)),1,b(nil,3,nil)), X).
+ X = b(b(nil,3,nil), 1, b(b(nil,5,nil), 2, b(nil,4,nil))).
+</pre>'''
+
+hint = {}
diff --git a/prolog/problems/trees/numberbt_2/common.py b/prolog/problems/trees/numberbt_2/common.py
new file mode 100644
index 0000000..65baa14
--- /dev/null
+++ b/prolog/problems/trees/numberbt_2/common.py
@@ -0,0 +1,13 @@
+id = 139
+group = 'trees'
+number = 44
+visible = True
+facts = None
+
+solution = '''\
+numberBT(nil, 0).
+numberBT(b(L, _, R), N) :-
+ numberBT(L, LN),
+ numberBT(R, RN),
+ N is LN + RN + 1.
+'''
diff --git a/prolog/problems/trees/numberbt_2/en.py b/prolog/problems/trees/numberbt_2/en.py
new file mode 100644
index 0000000..6f735ed
--- /dev/null
+++ b/prolog/problems/trees/numberbt_2/en.py
@@ -0,0 +1,12 @@
+id = 139
+name = 'numberBT/2'
+slug = 'find the number of nodes in a binary tree'
+
+description = '''\
+<p><code>numberBT(T, N)</code>: <code>N</code> is the number of nodes in the binary tree <code>T</code>.</p>
+<pre>
+ ?- numberBT(b(b(nil,2,nil),1,b(nil,3,nil)), N).
+ N = 3.
+</pre>'''
+
+hint = {}
diff --git a/prolog/problems/trees/tolistbt_2/common.py b/prolog/problems/trees/tolistbt_2/common.py
new file mode 100644
index 0000000..6df7cdd
--- /dev/null
+++ b/prolog/problems/trees/tolistbt_2/common.py
@@ -0,0 +1,17 @@
+id = 141
+group = 'trees'
+number = 46
+visible = True
+facts = None
+
+solution = '''\
+conc141([], L, L).
+conc141([H|T], L2, [H|L]) :-
+ conc141(T, L2, L).
+
+tolistBT(nil, []).
+tolistBT(b(L, E, R), List) :-
+ tolistBT(L, LL),
+ tolistBT(R, RL),
+ conc141(LL, [E|RL], List).
+'''
diff --git a/prolog/problems/trees/tolistbt_2/en.py b/prolog/problems/trees/tolistbt_2/en.py
new file mode 100644
index 0000000..c4bf5ba
--- /dev/null
+++ b/prolog/problems/trees/tolistbt_2/en.py
@@ -0,0 +1,12 @@
+id = 141
+name = 'tolistBT/2'
+slug = 'construct a list with all elements of a binary tree'
+
+description = '''\
+<p><code>tolistBT(T, L)</code>: the list <code>L</code> contains all the elements in the binary tree <code>T</code>, in infix order.</p>
+<pre>
+ ?- tolistBT(b(b(nil,2,nil),1,b(nil,3,nil)), L).
+ L = [2,1,3].
+</pre>'''
+
+hint = {}