diff options
| author | Aleš Smodiš <aless@guru.si> | 2015-08-18 16:06:19 +0200 |
|---|---|---|
| committer | Aleš Smodiš <aless@guru.si> | 2015-08-18 16:06:19 +0200 |
| commit | 95e2fe57f6e4639f6ae9f1fef368829d5090dbf6 (patch) | |
| tree | 462ba05eb0c4732ca1c97739548801258bf47b40 | |
Exported all problems from the SQLite database into the new directory structure.
174 files changed, 2872 insertions, 0 deletions
diff --git a/prolog/facts/denotational_semantics_aux__predicates.py b/prolog/facts/denotational_semantics_aux__predicates.py new file mode 100644 index 0000000..4bf315b --- /dev/null +++ b/prolog/facts/denotational_semantics_aux__predicates.py @@ -0,0 +1,32 @@ +id = 2 + +name = 'denotational semantics aux. predicates' + +facts = '''\ +findblank(R, Bx) :- + findblank(R, 1, Bx). +findblank([0|_], Bx, Bx) :- !. +findblank([_|T], Cx, Bx) :- + Cx1 is Cx + 1, + findblank(T, Cx1, Bx). + +swap([H1,H2|T],2,[H2,H1|T]). +swap([H|T],C0,[H|NewT]):- + C0 > 2, + C is C0 - 1, + swap(T,C,NewT). + +swap(R, I1, I2, NewR) :- + (I1 < I2, !, + Ix1 = I1, Ix2 = I2 + ; + Ix1 = I2, Ix2 = I1), + Cut1 is Ix1 - 1, + Cut2 is Ix2 - Ix1 - 1, + length(LBef, Cut1), + length(LMid, Cut2), + lists:append(LBef, [E1|RRest], R), + lists:append(LMid, [E2|LAft], RRest), + lists:append(LBef, [E2|RIntermediate], NewR), + lists:append(LMid, [E1|LAft], RIntermediate). +''' diff --git a/prolog/facts/family_relations.py b/prolog/facts/family_relations.py new file mode 100644 index 0000000..6be71fa --- /dev/null +++ b/prolog/facts/family_relations.py @@ -0,0 +1,76 @@ +id = 1 + +name = 'family relations' + +facts = '''\ +parent(tina, william). +parent(thomas, william). +parent(thomas, sally). +parent(thomas, jeffrey). +parent(sally, andrew). +parent(sally, melanie). +parent(andrew, joanne). +parent(jill, joanne). +parent(joanne, steve). +parent(william, vanessa). +parent(william, patricia). +parent(vanessa, susan). +parent(patrick, susan). +parent(patricia, john). +parent(john, michael). +parent(john, michelle). + +parent(frank, george). +parent(estelle, george). +parent(morty, jerry). +parent(helen, jerry). +parent(jerry, anna). +parent(elaine, anna). +parent(elaine, kramer). +parent(george, kramer). + +parent(margaret, nevia). +parent(margaret, alessandro). +parent(ana, aleksander). +parent(aleksandr, aleksander). +parent(nevia, luana). +parent(aleksander, luana). +parent(nevia, daniela). +parent(aleksander, daniela). + +male(william). +male(thomas). +male(jeffrey). +male(andrew). +male(steve). +male(patrick). +male(john). +male(michael). +male(frank). +male(george). +male(morty). +male(jerry). +male(kramer). +male(aleksandr). +male(alessandro). +male(aleksander). + +female(tina). +female(sally). +female(melanie). +female(joanne). +female(jill). +female(vanessa). +female(patricia). +female(susan). +female(michelle). +female(estelle). +female(helen). +female(elaine). +female(anna). +female(margaret). +female(ana). +female(nevia). +female(luana). +female(daniela). +''' diff --git a/prolog/problems/clp_fd/gcd_3/common.py b/prolog/problems/clp_fd/gcd_3/common.py new file mode 100644 index 0000000..8ab99ef --- /dev/null +++ b/prolog/problems/clp_fd/gcd_3/common.py @@ -0,0 +1,16 @@ +id = 149 +group = 'clp_fd' +number = 61 +visible = True +facts = None + +solution = '''\ +cd(X, Y, CD):- + X #= _ * CD, + Y #= _ * CD, + indomain(CD). + +gcd(X, Y, GCD):- + cd(X, Y, GCD), + \+ ( cd(X, Y, CD), CD > GCD ). +''' diff --git a/prolog/problems/clp_fd/gcd_3/en.py b/prolog/problems/clp_fd/gcd_3/en.py new file mode 100644 index 0000000..6d64602 --- /dev/null +++ b/prolog/problems/clp_fd/gcd_3/en.py @@ -0,0 +1,13 @@ +id = 149 +name = 'gcd/3' +slug = 'greatest common divisor' + +description = '''\ +<p><code>gcd(X, Y, GCD)</code>: <code>GCD</code> is the greatest common divisor of <code>X</code> and <code>Y</code>. Implement this predicate using constraints.</p> +<p>Hint: try writing a predicate to find <em>all</em> common divisors of two numbers first.</p> +<pre> + ?- gcd(36, 84, GCD). + GCD = 12. +</pre>''' + +hint = {} diff --git a/prolog/problems/clp_fd/magic_1/common.py b/prolog/problems/clp_fd/magic_1/common.py new file mode 100644 index 0000000..0308e1d --- /dev/null +++ b/prolog/problems/clp_fd/magic_1/common.py @@ -0,0 +1,17 @@ +id = 151 +group = 'clp_fd' +number = 60 +visible = True +facts = None + +solution = '''\ +magic(L):- + L = [A1,A2,A3,B1,B2,B3,C1,C2,C3], + L ins 1..9, + all_different(L), + A1+A2+A3 #= B1+B2+B3, + A1+A2+A3 #= C1+C2+C3, + A1+B1+C1 #= A2+B2+C2, + A1+B1+C1 #= A3+B3+C3, + A1+B2+C3 #= A3+B2+C1, + labeling([], L).''' diff --git a/prolog/problems/clp_fd/magic_1/en.py b/prolog/problems/clp_fd/magic_1/en.py new file mode 100644 index 0000000..6fcf252 --- /dev/null +++ b/prolog/problems/clp_fd/magic_1/en.py @@ -0,0 +1,13 @@ +id = 151 +name = 'magic/1' +slug = 'generate a 3x3 magic square' + +description = '''\ +<p><code>magic(S)</code>: the list <code>S</code> represents a 3×3 magic square (<code>S</code> is a permutation of numbers 1 to 9 - three numbers for each row). The sums of numbers in each row, column and diagonal of a magic squre are equal. Implement this predicate using constraints. Your code should return all possible solutions.</p> +<pre> + ?- magic(S). + S = [2, 7, 6, 9, 5, 1, 4, 3, 8] ; + … +</pre>''' + +hint = {} diff --git a/prolog/problems/clp_fd/puzzle_abc_3/common.py b/prolog/problems/clp_fd/puzzle_abc_3/common.py new file mode 100644 index 0000000..ee5da6f --- /dev/null +++ b/prolog/problems/clp_fd/puzzle_abc_3/common.py @@ -0,0 +1,14 @@ +id = 153 +group = 'clp_fd' +number = 57 +visible = True +facts = None + +solution = '''\ +puzzle_abc(A, B, C) :- + A #= B + 2, + B #= 2 * C, + A+B+C #= 27, + [A,B,C] ins 0..inf, + labeling([], [A,B,C]). +''' diff --git a/prolog/problems/clp_fd/puzzle_abc_3/en.py b/prolog/problems/clp_fd/puzzle_abc_3/en.py new file mode 100644 index 0000000..5385fe2 --- /dev/null +++ b/prolog/problems/clp_fd/puzzle_abc_3/en.py @@ -0,0 +1,9 @@ +id = 153 +name = 'puzzle_abc/3' +slug = 'age puzzle: abc' + +description = '''\ +<p>Person <code>A</code> is two years older than <code>B</code> who is twice as old as <code>C</code>. The total of the ages of A, B and C is 27.</p> +<p>Write the predicate <code>puzzle_abc(A, B, C)</code> that finds the ages of the three people.</p>''' + +hint = {} diff --git a/prolog/problems/clp_fd/puzzle_beth_1/common.py b/prolog/problems/clp_fd/puzzle_beth_1/common.py new file mode 100644 index 0000000..a7bcfeb --- /dev/null +++ b/prolog/problems/clp_fd/puzzle_beth_1/common.py @@ -0,0 +1,9 @@ +id = 155 +group = 'clp_fd' +number = 56 +visible = True +facts = None + +solution = '''\ +puzzle_beth(X) :- + X + 2 #= 2*(X-5).''' diff --git a/prolog/problems/clp_fd/puzzle_beth_1/en.py b/prolog/problems/clp_fd/puzzle_beth_1/en.py new file mode 100644 index 0000000..7f4ebc2 --- /dev/null +++ b/prolog/problems/clp_fd/puzzle_beth_1/en.py @@ -0,0 +1,10 @@ +id = 155 +name = 'puzzle_beth/1' +slug = 'age puzzle: beth' + +description = '''\ +<p>When asked how old she was, Beth replied "In two years I will be twice as old as I was five years ago".</p> +<p>Write the predicate <code>puzzle_beth(X)</code> that finds her current age as <code>X</code>.</p> +''' + +hint = {} diff --git a/prolog/problems/clp_fd/puzzle_momson_2/common.py b/prolog/problems/clp_fd/puzzle_momson_2/common.py new file mode 100644 index 0000000..f96f403 --- /dev/null +++ b/prolog/problems/clp_fd/puzzle_momson_2/common.py @@ -0,0 +1,14 @@ +id = 152 +group = 'clp_fd' +number = 58 +visible = True +facts = None + +solution = '''\ +puzzle_momson(M, S) :- + M #= 10*A + B, + S #= 10*B + A, + [A,B] ins 1..9, + M + S #= 66, + M #> S, + labeling([], [M, S]).''' diff --git a/prolog/problems/clp_fd/puzzle_momson_2/en.py b/prolog/problems/clp_fd/puzzle_momson_2/en.py new file mode 100644 index 0000000..8fa8a1f --- /dev/null +++ b/prolog/problems/clp_fd/puzzle_momson_2/en.py @@ -0,0 +1,9 @@ +id = 152 +name = 'puzzle_momson/2' +slug = 'age puzzle: mom & son' + +description = '''\ +<p>The sum of ages of mother and her son is 66. The mother's age is the son's age reversed. How old are they?</p> +<p>Write the predicate <code>puzzle_momson(M, S)</code> that finds the ages of mother <code>M</code> and son <code>S</code>.</p>''' + +hint = {} diff --git a/prolog/problems/clp_fd/puzzle_ratio_2/common.py b/prolog/problems/clp_fd/puzzle_ratio_2/common.py new file mode 100644 index 0000000..ba7585b --- /dev/null +++ b/prolog/problems/clp_fd/puzzle_ratio_2/common.py @@ -0,0 +1,17 @@ +id = 154 +group = 'clp_fd' +number = 59 +visible = True +facts = None + +solution = '''\ +puzzle_ratio(A, B) :- + A #= 5*X, + B #= 4*X, + X #> 0, + A+3 #= 11*Y, + B+3 #= 9*Y, + Y #> 0, + A #< 200, + B #< 200, + labeling([], [A, B]).''' diff --git a/prolog/problems/clp_fd/puzzle_ratio_2/en.py b/prolog/problems/clp_fd/puzzle_ratio_2/en.py new file mode 100644 index 0000000..aa5b647 --- /dev/null +++ b/prolog/problems/clp_fd/puzzle_ratio_2/en.py @@ -0,0 +1,9 @@ +id = 154 +name = 'puzzle_ratio/2' +slug = 'age puzzle: ratio' + +description = '''\ +<p>Present ages of <code>A</code> and <code>B</code> are in the ratio of 5:4. In three years the ratio of their ages will become 11:9.</p> +<p>Write the predicate <code>puzzle_ratio(A, B)</code> that finds the ages of <code>A</code> and <code>B</code>.</p>''' + +hint = {} diff --git a/prolog/problems/clp_fd/tobase_3/common.py b/prolog/problems/clp_fd/tobase_3/common.py new file mode 100644 index 0000000..fb88be0 --- /dev/null +++ b/prolog/problems/clp_fd/tobase_3/common.py @@ -0,0 +1,15 @@ +id = 150 +group = 'clp_fd' +number = 62 +visible = True +facts = None + +solution = '''\ +tobase(0, _, 0) :- !. +tobase(N, B, Nb) :- + B in 2..10, + indomain(B), + N #= N1 * B + Rem, + Rem #>= 0, Rem #< B, + Nb #= Nb1 * 10 + Rem, + tobase(N1, B, Nb1).''' diff --git a/prolog/problems/clp_fd/tobase_3/en.py b/prolog/problems/clp_fd/tobase_3/en.py new file mode 100644 index 0000000..bac8723 --- /dev/null +++ b/prolog/problems/clp_fd/tobase_3/en.py @@ -0,0 +1,16 @@ +id = 150 +name = 'tobase/3' +slug = 'convert numbers from/to the decimal system' + +description = '''\ +<p><code>tobase(Number, B, X)</code>: given a <code>Number</code> in the decimal system (base 10), <code>X</code> represents the same number in the system with base <code>B</code>. Implement this predicate using constraints. Limit the value of <code>B</code> to the interval [2..10].</p> +<pre> + ?- tobase(42, 2, X). + X = 101010. + ?- tobase(N, 2, 101010). + N = 42. + ?- tobase(42, B, 101010). + B = 2. +</pre>''' + +hint = {} diff --git a/prolog/problems/clp_r/bounding_box_3/common.py b/prolog/problems/clp_r/bounding_box_3/common.py new file mode 100644 index 0000000..631f017 --- /dev/null +++ b/prolog/problems/clp_r/bounding_box_3/common.py @@ -0,0 +1,14 @@ +id = 157 +group = 'clp_r' +number = 67 +visible = True +facts = None + +solution = '''\ +bounding_box([], Xa/Ya, Xb/Yb) :- + minimize(Xb - Xa), + minimize(Yb - Ya). +bounding_box([X/Y|L], Xa/Ya, Xb/Yb) :- + { Xa =< X, X =< Xb, + Ya =< Y, Y =< Yb }, + bounding_box(L, Xa/Ya, Xb/Yb).''' diff --git a/prolog/problems/clp_r/bounding_box_3/en.py b/prolog/problems/clp_r/bounding_box_3/en.py new file mode 100644 index 0000000..bc800b9 --- /dev/null +++ b/prolog/problems/clp_r/bounding_box_3/en.py @@ -0,0 +1,12 @@ +id = 157 +name = 'bounding_box/3' +slug = 'find the smallest bounding box' + +description = '''\ +<p><code>bounding_box(Points, X1/Y1, X2/Y2)</code>: <code>X1/Y1</code> and <code>X2/Y2</code> are the bottom-left and top-right points defining the smallest bounding box containing all points in the list <code>Points</code>. +<pre> + ?- bounding_box([4.5/2.3, 3.6/1.2, 6.7/0.1], X1/Y1, X2/Y2). + X1 = 3.6, Y1 = 0.1, X2 = 6.7, Y2 = 2.3. +</pre>''' + +hint = {} diff --git a/prolog/problems/clp_r/center_3/common.py b/prolog/problems/clp_r/center_3/common.py new file mode 100644 index 0000000..1474ef1 --- /dev/null +++ b/prolog/problems/clp_r/center_3/common.py @@ -0,0 +1,20 @@ +id = 158 +group = 'clp_r' +number = 68 +visible = True +facts = None + +solution = '''\ +memb158(X, [X|_]). +memb158(X, [_|T]) :- + memb158(X, T). + +check158([], _, _). +check158([X/Y | T], R, Xc/Yc) :- + { (X-Xc)*(X-Xc) + (Y-Yc)*(Y-Yc) =< R*R }, + check158(T, R, Xc/Yc). + +center(L, R, Xc/Yc) :- + memb158(Xc/Yc, L), + check158(L, R, Xc/Yc). +''' diff --git a/prolog/problems/clp_r/center_3/en.py b/prolog/problems/clp_r/center_3/en.py new file mode 100644 index 0000000..b2b4c8d --- /dev/null +++ b/prolog/problems/clp_r/center_3/en.py @@ -0,0 +1,13 @@ +id = 158 +name = 'center/3' +slug = 'find central points' + +description = '''\ +<p><code>center(Points, R, X/Y)</code>: <code>X/Y</code> is a point in the list <code>Points</code> that is at most <code>R</code> away from all other points.</p> +<pre> + ?- center([1.0/1.1, 2.0/2.1, 3.0/3.1, 4.0/4.1], 4.0, X/Y). + X = 2.0, Y = 2.1 ; + X = 3.0, Y = 3.1. +</pre>''' + +hint = {} diff --git a/prolog/problems/clp_r/linear_opt_3/common.py b/prolog/problems/clp_r/linear_opt_3/common.py new file mode 100644 index 0000000..95d7ea2 --- /dev/null +++ b/prolog/problems/clp_r/linear_opt_3/common.py @@ -0,0 +1,12 @@ +id = 159 +group = 'clp_r' +number = 63 +visible = True +facts = None + +solution = '''\ +linear_opt(X, Y, MaxE) :- + { X >= 0, Y >= 0, X =< 5, + X+Y =< 7, X+2*Y >= 4, Y =< X+5, + MaxE = -0.4*X+3.2*Y }, + maximize(MaxE).''' diff --git a/prolog/problems/clp_r/linear_opt_3/en.py b/prolog/problems/clp_r/linear_opt_3/en.py new file mode 100644 index 0000000..645a6c8 --- /dev/null +++ b/prolog/problems/clp_r/linear_opt_3/en.py @@ -0,0 +1,16 @@ +id = 159 +name = 'linear_opt/3' +slug = 'linear optimization' + +description = '''\ +<p>A set of points in the plane is defined by the inequalities</p> +<ul> + <li>0 ≤ <code>X</code> ≤ 5,</li> + <li><code>Y</code> ≥ 0,</li> + <li><code>X</code> + <code>Y</code> ≤ 7,</li> + <li><code>X</code> + 2*<code>Y</code> ≥ 4 and</li> + <li><code>Y</code> ≤ <code>X</code> + 5.</li> +</ul> +<p>The predicate <code>linear_opt(X, Y, MaxE)</code> should return the point (<code>X</code>, <code>Y</code>) where the expression <code>E = -0.4*X + 3.2*Y</code> has the largest value.</p>''' + +hint = {} diff --git a/prolog/problems/clp_r/max_sum_2/common.py b/prolog/problems/clp_r/max_sum_2/common.py new file mode 100644 index 0000000..ef4ea79 --- /dev/null +++ b/prolog/problems/clp_r/max_sum_2/common.py @@ -0,0 +1,12 @@ +id = 156 +group = 'clp_r' +number = 66 +visible = True +facts = None + +solution = '''\ +max_sum([_], S) :- + minimize(S). +max_sum([A,B|T], S) :- + { S >= A + B }, + max_sum([B|T], S).''' diff --git a/prolog/problems/clp_r/max_sum_2/en.py b/prolog/problems/clp_r/max_sum_2/en.py new file mode 100644 index 0000000..3e8f136 --- /dev/null +++ b/prolog/problems/clp_r/max_sum_2/en.py @@ -0,0 +1,14 @@ +id = 156 +name = 'max_sum/2' +slug = 'find maximal adjacent elements' + +description = '''\ +<p><code>max_sum(List, Max)</code>: <code>Max</code> is the maximal sum of two adjacent elements in <code>List</code>.</p> +<pre> + ?- max_sum([4.5, 3.6, 1.2, 6.7], Max). + Max = 8.1. + ?- max_sum([1.1, 1.2, -12.3, 8.8], Max). + Max = 2.3. +</pre>''' + +hint = {} diff --git a/prolog/problems/clp_r/megabytes_2/common.py b/prolog/problems/clp_r/megabytes_2/common.py new file mode 100644 index 0000000..e528c3c --- /dev/null +++ b/prolog/problems/clp_r/megabytes_2/common.py @@ -0,0 +1,9 @@ +id = 160 +group = 'clp_r' +number = 65 +visible = True +facts = None + +solution = '''\ +megabytes(SI, IEC) :- + { SI * 2^20 = IEC * 10^6 }.''' diff --git a/prolog/problems/clp_r/megabytes_2/en.py b/prolog/problems/clp_r/megabytes_2/en.py new file mode 100644 index 0000000..6db93c8 --- /dev/null +++ b/prolog/problems/clp_r/megabytes_2/en.py @@ -0,0 +1,14 @@ +id = 160 +name = 'megabytes/2' +slug = 'convert mebibytes to megabytes' + +description = '''\ +<p>A <em>mega</em>byte is the SI unit meaning 10<sup>6</sup> bytes, while a <em>mebi</em>byte is the IEC unit meaning 2<sup>20</sup> bytes. Write the predicate <code>megabytes(SI, IEC)</code> that converts between the two using constraints.</p> +<pre> + ?- megabytes(2, IEC). + IEC = 1.9073486328125. + ?- megabytes(SI, 2). + SI = 2.097152. +</pre>''' + +hint = {} diff --git a/prolog/problems/clp_r/turkey_3/common.py b/prolog/problems/clp_r/turkey_3/common.py new file mode 100644 index 0000000..6a99fc4 --- /dev/null +++ b/prolog/problems/clp_r/turkey_3/common.py @@ -0,0 +1,15 @@ +id = 161 +group = 'clp_r' +number = 64 +visible = True +facts = None + +solution = '''\ +turkey(Brand1, Brand2, Cost) :- + {Cost = Brand1*0.20 + Brand2*0.30, + A = Brand1*5 + Brand2*10, + B = Brand1*4 + Brand2*3, + C = Brand1*0.5, + A >= 90, B >= 48, C >= 1.5}, + minimize(Cost). +''' diff --git a/prolog/problems/clp_r/turkey_3/en.py b/prolog/problems/clp_r/turkey_3/en.py new file mode 100644 index 0000000..3117e35 --- /dev/null +++ b/prolog/problems/clp_r/turkey_3/en.py @@ -0,0 +1,10 @@ +id = 161 +name = 'turkey/3' +slug = 'turkey feed' + +description = '''\ +<p>The Holiday Meal Turkey Ranch is considering buying two different brands of turkey feed and blending them to provide a good, low-cost diet for its turkeys. Each brand of feed contains, in varying proportions, some or all of the three nutritional ingredients essential for fattening turkeys. Each kilogram of brand 1 contains 5 grams of ingredient <code>A</code>, 4 grams of ingredient <code>B</code> and 0.5 grams of ingredient <code>C</code>. Each kilogram of brand 2 contains 10 grams of ingredient <code>A</code>, 3 grams of ingredient <code>B</code>, but nothing of ingredient <code>C</code>. The brand 1 feed costs 0.20 € a kilogram, while the brand 2 feed costs 0.30 € a kilogram.</p> +<p>The minimum monthly requirement per turkey is: 90 grams of ingredient <code>A</code>; 48 grams of ingredient <code>B</code> and 1.5 grams of ingredient <code>C</code>.</p> +<p>Formulate an LP model to help the rancher decide how to mix the two brands of turkey feed so that the minimum monthly intake requirement for each nutritional ingredient is met at minimum cost. Write the predicate <code>turkey(Brand1, Brand2, Cost)</code> that returns the amount (in kg) of brands 1 and 2 per turkey per month, and the total cost (in €).</p>''' + +hint = {} diff --git a/prolog/problems/dcg/ab_2/common.py b/prolog/problems/dcg/ab_2/common.py new file mode 100644 index 0000000..8cce3df --- /dev/null +++ b/prolog/problems/dcg/ab_2/common.py @@ -0,0 +1,11 @@ +id = 162 +group = 'dcg' +number = 69 +visible = True +facts = None + +solution = '''\ +ab --> [a], ab. +ab --> t162. +t162 --> [b], t162. +t162 --> [].''' diff --git a/prolog/problems/dcg/ab_2/en.py b/prolog/problems/dcg/ab_2/en.py new file mode 100644 index 0000000..8025081 --- /dev/null +++ b/prolog/problems/dcg/ab_2/en.py @@ -0,0 +1,10 @@ +id = 162 +name = 'ab/2' +slug = 'a*b*' + +description = '''\ +<p>Write a DCG with the starting symbol <code>ab</code> for the language <code>a<sup>m</sup>b<sup>n</sup></code>, where m, n ≥ 0.</p> +<p>Example words: <code>[]</code>, <code>a</code>, <code>aab</code>, <code>abbb</code>, <code>bbb</code>.</p> +<p>Hint: to generate words of increasing length, use the query <code>conc(Word,_,_), ab(Word,[])</code>.</p>''' + +hint = {} diff --git a/prolog/problems/dcg/digit_2/common.py b/prolog/problems/dcg/digit_2/common.py new file mode 100644 index 0000000..9b82f15 --- /dev/null +++ b/prolog/problems/dcg/digit_2/common.py @@ -0,0 +1,9 @@ +id = 164 +group = 'dcg' +number = 71 +visible = True +facts = None + +solution = '''\ +digit --> ([0] ; [1] ; [2] ; [3] ; [4] ; [5] ; [6] ; [7] ; [8] ; [9]). +''' diff --git a/prolog/problems/dcg/digit_2/en.py b/prolog/problems/dcg/digit_2/en.py new file mode 100644 index 0000000..200689d --- /dev/null +++ b/prolog/problems/dcg/digit_2/en.py @@ -0,0 +1,8 @@ +id = 164 +name = 'digit/2' +slug = 'a decimal digit' + +description = '''\ +<p>Write a DCG with the starting symbol <code>digit</code> for the language defined by the set of words {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.</p>''' + +hint = {} diff --git a/prolog/problems/dcg/expr_2/common.py b/prolog/problems/dcg/expr_2/common.py new file mode 100644 index 0000000..49059f2 --- /dev/null +++ b/prolog/problems/dcg/expr_2/common.py @@ -0,0 +1,23 @@ +id = 170 +group = 'dcg' +number = 77 +visible = False +facts = None + +solution = '''\ +expr --> term170, addterm170. +addterm170 --> []. +addterm170 --> [+], expr. +term170 --> factor170, multfactor170. +multfactor170 --> []. +multfactor170 --> [*], term170. +factor170 --> num170. +factor170 --> ['('], expr, [')']. + +num170 --> digit170. +num170 --> nzdigit170, num_next170. +num_next170 --> digit170. +num_next170 --> digit170, num_next170. +digit170 --> ([0] ; [1] ; [2] ; [3] ; [4] ; [5] ; [6] ; [7] ; [8] ; [9]). +nzdigit170 --> ([1] ; [2] ; [3] ; [4] ; [5] ; [6] ; [7] ; [8] ; [9]). +''' diff --git a/prolog/problems/dcg/expr_2/en.py b/prolog/problems/dcg/expr_2/en.py new file mode 100644 index 0000000..9b30551 --- /dev/null +++ b/prolog/problems/dcg/expr_2/en.py @@ -0,0 +1,10 @@ +id = 170 +name = 'expr/2' +slug = 'arithmetic expressions' + +description = '''\ +<p>Write a DCG with the starting symbol <code>expr</code> for the language of arithmetic expressions consisting of numbers (without leading zeros), addition and multiplication. Subexpressions can be grouped using parentheses.</p> +<p>Example words: <code>(1+2)*3</code>, <code>42*8*3</code>, <code>(2+1)*(3+4)</code>.</p> +''' + +hint = {} diff --git a/prolog/problems/dcg/expr_3/common.py b/prolog/problems/dcg/expr_3/common.py new file mode 100644 index 0000000..daa5b31 --- /dev/null +++ b/prolog/problems/dcg/expr_3/common.py @@ -0,0 +1,24 @@ +id = 171 +group = 'dcg' +number = 78 +visible = False +facts = None + +solution = '''\ +expr(N) --> term171(N). +expr(N) --> term171(N1), [+], expr(N2), {N is N1 + N2}. + +term171(N) --> factor171(N). +term171(N) --> factor171(N1), [*], term171(N2), {N is N1 * N2}. + +factor171(N) --> number171(N). +factor171(N) --> ['('], expr(N), [')']. + +memb171(X, [X|_]). +memb171(X, [_|T]) :- + memb171(X, T). + +digit171(N) --> [N], { memb171(N, [0,1,2,3,4,5,6,7,8,9]) }. +number171(N) --> digit171(N). +number171(N) --> number171(N1), digit171(D), { N is 10*N1 + D }. +''' diff --git a/prolog/problems/dcg/expr_3/en.py b/prolog/problems/dcg/expr_3/en.py new file mode 100644 index 0000000..3f91977 --- /dev/null +++ b/prolog/problems/dcg/expr_3/en.py @@ -0,0 +1,14 @@ +id = 171 +name = 'expr/3' +slug = 'arithmetic expressions with meaning' + +description = '''\ +<p>Write a DCG with the starting symbol <code>expr</code> for the language of arithmetic expressions consisting of numbers (without leading zeros), addition and multiplication. Subexpressions can be grouped using parentheses. The meaning of a word in this language is the numeric value of the represented arithmetic expression.</p> +<p>Example words: <code>(1+2)*3</code>, <code>42*8*3</code>, <code>(2+1)*(3+4)</code>.</p> +<pre> + ?- expr(N, ['(',2,'+',1,')','*','(',3,'+',4,')'], []). % (2+1)*(3+4) = 21 + N = 21. +</pre> +''' + +hint = {} diff --git a/prolog/problems/dcg/flower_2/common.py b/prolog/problems/dcg/flower_2/common.py new file mode 100644 index 0000000..d380722 --- /dev/null +++ b/prolog/problems/dcg/flower_2/common.py @@ -0,0 +1,13 @@ +id = 163 +group = 'dcg' +number = 70 +visible = True +facts = None + +solution = '''\ +flower --> iflower163. +flower --> [+], flower, [+]. + +iflower163 --> [-]. +iflower163 --> [-], iflower163. +''' diff --git a/prolog/problems/dcg/flower_2/en.py b/prolog/problems/dcg/flower_2/en.py new file mode 100644 index 0000000..85d1e73 --- /dev/null +++ b/prolog/problems/dcg/flower_2/en.py @@ -0,0 +1,10 @@ +id = 163 +name = 'flower/2' +slug = 'words like +++--+++' + +description = '''\ +<p>Write a DCG with the starting symbol <code>flower</code> for the language <code>+<sup>n</sup>-<sup>m</sup>+<sup>n</sup></code>, where m > 0 and n ≥ 0.</p> +<p>Example words: <code>-</code>, <code>++-++</code>, <code>+---+</code>.</p> +''' + +hint = {} diff --git a/prolog/problems/dcg/number_2/common.py b/prolog/problems/dcg/number_2/common.py new file mode 100644 index 0000000..e248891 --- /dev/null +++ b/prolog/problems/dcg/number_2/common.py @@ -0,0 +1,12 @@ +id = 165 +group = 'dcg' +number = 72 +visible = True +facts = None + +solution = '''\ +digit165 --> ([0] ; [1] ; [2] ; [3] ; [4] ; [5] ; [6] ; [7] ; [8] ; [9]). + +number --> digit165. +number --> digit165, number. +''' diff --git a/prolog/problems/dcg/number_2/en.py b/prolog/problems/dcg/number_2/en.py new file mode 100644 index 0000000..6a3d33e --- /dev/null +++ b/prolog/problems/dcg/number_2/en.py @@ -0,0 +1,9 @@ +id = 165 +name = 'number/2' +slug = 'numbers with potential leading zeros' + +description = '''\ +<p>Write a DCG with the starting symbol <code>number</code> for the language of non-negative integers. The numbers may include leading zeros.</p> +<p>Example words: <code>123</code>, <code>54</code>, <code>0122</code>, <code>0001221</code>, <code>0</code>.</p>''' + +hint = {} diff --git a/prolog/problems/dcg/number_3/common.py b/prolog/problems/dcg/number_3/common.py new file mode 100644 index 0000000..cc4bde7 --- /dev/null +++ b/prolog/problems/dcg/number_3/common.py @@ -0,0 +1,30 @@ +id = 167 +group = 'dcg' +number = 74 +visible = True +facts = None + +solution = '''\ +number(Num) --> dig167(N), { l2n167(N,Num) }. +number(Num) --> nonzero167([N]), numb_next167(N1), { l2n167([N|N1],Num) }. + +zero167([0]) --> [0]. +nonzero167([N]) --> [N], {memb167(N, [1,2,3,4,5,6,7,8,9])}. + +dig167(N) --> zero167(N). +dig167(N) --> nonzero167(N). +numb_next167(N) --> dig167(N). +numb_next167([N|N1]) --> dig167([N]), numb_next167(N1). + +memb167(X, [X|_]). +memb167(X, [_|T]) :- + memb167(X, T). + +l2n167(L, N) :- + l2n167(L, 0, N). +l2n167([N], S, R) :- + R is S*10+N. +l2n167([H|T], S, N) :- + S1 is S*10+H, + l2n167(T, S1, N). +''' diff --git a/prolog/problems/dcg/number_3/en.py b/prolog/problems/dcg/number_3/en.py new file mode 100644 index 0000000..a7a22fa --- /dev/null +++ b/prolog/problems/dcg/number_3/en.py @@ -0,0 +1,13 @@ +id = 167 +name = 'number/3' +slug = 'numbers with meaning' + +description = '''\ +<p>Write a DCG with the starting symbol <code>number</code> for the language of non-negative integers. The numbers may contain leading zeros. The meaning of a word in this language is the numeric value of the represented number.</p> +<pre> + ?- number(N, [1,2,3,4], []). + N = 1234. +</pre> +''' + +hint = {} diff --git a/prolog/problems/dcg/number_proper_2/common.py b/prolog/problems/dcg/number_proper_2/common.py new file mode 100644 index 0000000..fdcc494 --- /dev/null +++ b/prolog/problems/dcg/number_proper_2/common.py @@ -0,0 +1,16 @@ +id = 166 +group = 'dcg' +number = 73 +visible = True +facts = None + +solution = '''\ +number_proper --> digit166. +number_proper --> nzdigit166, num_next166. + +num_next166 --> digit166. +num_next166 --> digit166, num_next166. + +digit166 --> ([0] ; [1] ; [2] ; [3] ; [4] ; [5] ; [6] ; [7] ; [8] ; [9]). +nzdigit166 --> ([1] ; [2] ; [3] ; [4] ; [5] ; [6] ; [7] ; [8] ; [9]). +''' diff --git a/prolog/problems/dcg/number_proper_2/en.py b/prolog/problems/dcg/number_proper_2/en.py new file mode 100644 index 0000000..37ad864 --- /dev/null +++ b/prolog/problems/dcg/number_proper_2/en.py @@ -0,0 +1,9 @@ +id = 166 +name = 'number_proper/2' +slug = 'numbers without leading zeros' + +description = '''\ +<p>Write a DCG with the starting symbol <code>number_proper</code> for the language of non-negative integers. The numbers should <em>not</em> contain leading zeros.</p> +<p>Example words: <code>123</code>, <code>54</code>, <code>122</code>, <code>1221</code>, <code>0</code>.</p>''' + +hint = {} diff --git a/prolog/problems/dcg/paren_2/common.py b/prolog/problems/dcg/paren_2/common.py new file mode 100644 index 0000000..ce5ec87 --- /dev/null +++ b/prolog/problems/dcg/paren_2/common.py @@ -0,0 +1,10 @@ +id = 168 +group = 'dcg' +number = 75 +visible = True +facts = None + +solution = '''\ +paren --> []. +paren --> ['('], paren, [')'], paren. +''' diff --git a/prolog/problems/dcg/paren_2/en.py b/prolog/problems/dcg/paren_2/en.py new file mode 100644 index 0000000..a4ab666 --- /dev/null +++ b/prolog/problems/dcg/paren_2/en.py @@ -0,0 +1,10 @@ +id = 168 +name = 'paren/2' +slug = 'properly nested parens' + +description = '''\ +<p>Write a DCG with the starting symbol <code>paren</code> for the language of properly nested sequences of parentheses. The terminal symbols in the grammar should be written like this: <code>['(']</code> and <code>[')']</code>.</p> +<p>Example words: <code>()</code>, <code>(())</code>, <code>()(())</code>, <code>(()())()</code>.</p> +<p>Example non-words: <code>)(</code>, <code>((()</code>, <code>))</code>.</p>''' + +hint = {} diff --git a/prolog/problems/dcg/paren_3/common.py b/prolog/problems/dcg/paren_3/common.py new file mode 100644 index 0000000..cf7c439 --- /dev/null +++ b/prolog/problems/dcg/paren_3/common.py @@ -0,0 +1,10 @@ +id = 169 +group = 'dcg' +number = 76 +visible = True +facts = None + +solution = '''\ +paren(0) --> []. +paren(D) --> ['('], paren(D1), [')'], paren(D2), { D1 >= D2, D is D1 + 1 ; D1 < D2 , D is D2 }. +''' diff --git a/prolog/problems/dcg/paren_3/en.py b/prolog/problems/dcg/paren_3/en.py new file mode 100644 index 0000000..f4d4c3b --- /dev/null +++ b/prolog/problems/dcg/paren_3/en.py @@ -0,0 +1,13 @@ +id = 169 +name = 'paren/3' +slug = 'properly nested parens with meaning' + +description = '''\ +<p>Write a DCG with the starting symbol <code>paren</code> for the language of properly nested sequences of parentheses. The meaning of a word in this language is the maximum depth of the nested parentheses.</p> +<pre> + ?- paren(D, ['(','(',')',')','(',')'], []). % (())() + D = 2. +</pre> +''' + +hint = {} diff --git a/prolog/problems/denotational_semantics/algol_3/common.py b/prolog/problems/denotational_semantics/algol_3/common.py new file mode 100644 index 0000000..fe6618d --- /dev/null +++ b/prolog/problems/denotational_semantics/algol_3/common.py @@ -0,0 +1,79 @@ +id = 176 +group = 'denotational_semantics' +number = 83 +visible = True +facts = None + +solution = '''\ +algol(fun(S0,S,apply176([printout=[]|S0],S,Minstructs))) --> + [begin], instructs176(Minstructs), [end]. + +instructs176(Minstr) --> instr176(Minstr). +instructs176(fun(S0,S, + (apply176(S0,S1,Minstr), + apply176(S1,S,Minstructs)))) + --> + instr176(Minstr), instructs176(Minstructs). + +instr176(Massign) --> assign176(Massign). +instr176(fun(S0,[printout = L1|S1], + (memb(X = V,S0), + del(printout = L0,S0,S1), + conc(L0,[V],L1)))) + --> + [print(X)]. +instr176(fun(S0,S, + loop176(S0,Mcond,Minstructs,S))) + --> + [while], cond176(Mcond), [do,begin], instructs176(Minstructs), [end]. + +assign176(fun(S0,[X = Value|S1], + (apply176(S0,Value,Mexpr), + del(X = _,S0,S1)))) + --> + var176(X), [:=], expr176(Mexpr). + +cond176( fun( S, TruthVal, + (apply176(S,Val1,ME1), + apply176(S,Val2,ME2), + (Val1 < Val2,!,TruthVal = true ; TruthVal = false)))) + --> + expr176(ME1), [<], expr176(ME2). + +var176(X) --> [X], {atom(X)}. + +expr176(fun(S,Value,eval(Expr,S,Value))) --> + [Expr]. + +apply176(In, Out, fun(In, Out, Goals)) :- + call(Goals). + +loop176( State0, Mcond, _, State0) :- + apply176( State0, false, Mcond), !. +loop176( S0, Mcond, MBody, S) :- + copy_term( MBody, MBodyCopy), + apply176( S0, S1, MBody), + loop176( S1, Mcond, MBodyCopy, S). + +eval176( N, _, N) :- + number176( N), !. +eval176( X, State, Val) :- % A program variable + atom( X), !, + memb( X = Val, State). +eval176( E1 + E2, State, Val) :- !, + eval176( E1, State, V1), + eval176( E2, State, V2), + Val is V1 + V2. +eval176( E1 - E2, State, Val) :- !, + eval176( E1, State, V1), + eval176( E2, State, V2), + Val is V1 - V2. +eval176( E1 * E2, State, Val) :- !, + eval176( E1, State, V1), + eval176( E2, State, V2), + Val is V1 * V2. +eval176( E1 / E2, State, Val) :- !, + eval176( E1, State, V1), + eval176( E2, State, V2), + Val is V1 / V2. +''' diff --git a/prolog/problems/denotational_semantics/algol_3/en.py b/prolog/problems/denotational_semantics/algol_3/en.py new file mode 100644 index 0000000..4b46b11 --- /dev/null +++ b/prolog/problems/denotational_semantics/algol_3/en.py @@ -0,0 +1,33 @@ +id = 176 +name = 'algol/3' +slug = 'interpreter for mini-algol' + +description = '''\ +<p>A DCG for mini-algol.</p> +<pre> + % apply a function to a starting state + ?- apply([a=2], Out, fun(_In, Out, eval(a+3, _In, Out))). + Out = 5. + + % a := a+b + % b := a-b + % a := a-b + ?- _Program = [begin,a,:=,a+b,b,:=,a-b,a,:=,a-b,end], + algol(_F, _Program, []), + apply([a=3,b=5], Output, _F). + Output = [a=5,b=3,printout=[]]. + + % a := 0 + % while a < 10 do + % begin + % print(a) + % a := a+1 + % end + ?- _Program = [begin,a,:=,0,while,a,<,10,do,begin,print(a),a,:=,a+1,end,end], + algol(_F, _Program, []), + apply([a=3], Output, _F). + Output = [a=10,printout=[0,1,2,3,4,5,6,7,8,9]]. +</pre> +''' + +hint = {} diff --git a/prolog/problems/denotational_semantics/algol_for_3/common.py b/prolog/problems/denotational_semantics/algol_for_3/common.py new file mode 100644 index 0000000..3917aa6 --- /dev/null +++ b/prolog/problems/denotational_semantics/algol_for_3/common.py @@ -0,0 +1,93 @@ +id = 178 +group = 'denotational_semantics' +number = 85 +visible = True +facts = None + +solution = '''\ +algol_for(fun(S0,S,apply178([printout=[]|S0],S,Minstructs))) --> + [begin], instructs178(Minstructs), [end]. + +instructs178(Minstr) --> instr178(Minstr). +instructs178(fun(S0,S, + (apply178(S0,S1,Minstr), + apply178(S1,S,Minstructs)))) + --> + instr178(Minstr), instructs178(Minstructs). + +instr178(Massign) --> assign178(Massign). +instr178(fun(S0,[printout = L1|S1], + (memb(X = V,S0), + del(printout = L0,S0,S1), + conc(L0,[V],L1)))) + --> + [print(X)]. +instr178(fun(S0,S, + loop178(S0,Mcond,Minstructs,S))) + --> + [while], cond178(Mcond), [do,begin], instructs178(Minstructs), [end]. +instr178(fun(S0, S, + (apply178(S0, S1, Minit), + for178(S1, Mcond, Mstep, Mbody, S)))) + --> + [for], assign178(Minit), [&], cond178(Mcond), [&], assign178(Mstep), [do, begin], instructs178(Mbody), [end]. + +assign178(fun(S0,[X = Value|S1], + (apply178(S0,Value,Mexpr), + del(X = _,S0,S1)))) + --> + var178(X), [:=], expr178(Mexpr). + +cond178( fun( S, TruthVal, + (apply178(S,Val1,ME1), + apply178(S,Val2,ME2), + (Val1 < Val2,!,TruthVal = true ; TruthVal = false)))) + --> + expr178(ME1), [<], expr178(ME2). + +var178(X) --> [X], {atom(X)}. + +expr178(fun(S,Value,eval(Expr,S,Value))) --> + [Expr]. + +apply178(In, Out, fun(In, Out, Goals)) :- + call(Goals). + +loop178( State0, Mcond, _, State0) :- + apply178( State0, false, Mcond), !. +loop178( S0, Mcond, MBody, S) :- + copy_term( MBody, MBodyCopy), + apply178( S0, S1, MBody), + loop178( S1, Mcond, MBodyCopy, S). + +for178(S0, Mcond, _, _, S0) :- + apply178(S0, false, Mcond), !. +for178(S0, Mcond, Mstep, Mbody, S) :- + copy_term(Mbody, Mbody2), + copy_term(Mstep, Mstep2), + apply178(S0, S1, Mbody), + apply178(S1, S2, Mstep), + for178(S2, Mcond, Mstep2, Mbody2, S). + +eval178( N, _, N) :- + number178( N), !. +eval178( X, State, Val) :- % A program variable + atom( X), !, + memb( X = Val, State). +eval178( E1 + E2, State, Val) :- !, + eval178( E1, State, V1), + eval178( E2, State, V2), + Val is V1 + V2. +eval178( E1 - E2, State, Val) :- !, + eval178( E1, State, V1), + eval178( E2, State, V2), + Val is V1 - V2. +eval178( E1 * E2, State, Val) :- !, + eval178( E1, State, V1), + eval178( E2, State, V2), + Val is V1 * V2. +eval178( E1 / E2, State, Val) :- !, + eval178( E1, State, V1), + eval178( E2, State, V2), + Val is V1 / V2. +''' diff --git a/prolog/problems/denotational_semantics/algol_for_3/en.py b/prolog/problems/denotational_semantics/algol_for_3/en.py new file mode 100644 index 0000000..3578b71 --- /dev/null +++ b/prolog/problems/denotational_semantics/algol_for_3/en.py @@ -0,0 +1,19 @@ +id = 178 +name = 'algol_for/3' +slug = 'interpreter for mini-algol with for-statement' + +description = '''\ +<p>Extend the given DCG for mini-algol to support the for-statement. Example:</p> +<pre> + % for a := 0 & a < 5 & a := a + 1 do + % begin + % print(a) + % end + ?- _Program = [begin,for,a,:=,0,&,a,<,5,&,a,:=,a+1,do,begin,print(a),end,end], + algol_for(_F, _Program, []), + apply([a=2], Output, _F). + Output = [a=5,printout=[0,1,2,3,4]]. +</pre> +''' + +hint = {} diff --git a/prolog/problems/denotational_semantics/algol_if_3/common.py b/prolog/problems/denotational_semantics/algol_if_3/common.py new file mode 100644 index 0000000..8ca92bc --- /dev/null +++ b/prolog/problems/denotational_semantics/algol_if_3/common.py @@ -0,0 +1,86 @@ +id = 177 +group = 'denotational_semantics' +number = 84 +visible = True +facts = None + +solution = '''\ +algol_if(fun(S0,S,apply177([printout=[]|S0],S,Minstructs))) --> + [begin], instructs177(Minstructs), [end]. + +instructs177(Minstr) --> instr177(Minstr). +instructs177(fun(S0,S, + (apply177(S0,S1,Minstr), + apply177(S1,S,Minstructs)))) + --> + instr177(Minstr), instructs177(Minstructs). + +instr177(Massign) --> assign177(Massign). +instr177(fun(S0,[printout = L1|S1], + (memb(X = V,S0), + del(printout = L0,S0,S1), + conc(L0,[V],L1)))) + --> + [print(X)]. +instr177(fun(S0,S, + loop177(S0,Mcond,Minstructs,S))) + --> + [while], cond177(Mcond), [do,begin], instructs177(Minstructs), [end]. +instr177(fun(S0, S, + (apply177(S0, true, Mcond), !, + apply177(S0, S, MinstructsA) + ; + apply177(S0, S, MinstructsB)))) + --> + [if], cond177(Mcond), [then], instructs177(MinstructsA), [else], instructs177(MinstructsB), [end]. + +assign177(fun(S0,[X = Value|S1], + (apply177(S0,Value,Mexpr), + del(X = _,S0,S1)))) + --> + var177(X), [:=], expr177(Mexpr). + +cond177( fun( S, TruthVal, + (apply177(S,Val1,ME1), + apply177(S,Val2,ME2), + (Val1 < Val2,!,TruthVal = true ; TruthVal = false)))) + --> + expr177(ME1), [<], expr177(ME2). + +var177(X) --> [X], {atom(X)}. + +expr177(fun(S,Value,eval(Expr,S,Value))) --> + [Expr]. + +apply177(In, Out, fun(In, Out, Goals)) :- + call(Goals). + +loop177( State0, Mcond, _, State0) :- + apply177( State0, false, Mcond), !. +loop177( S0, Mcond, MBody, S) :- + copy_term( MBody, MBodyCopy), + apply177( S0, S1, MBody), + loop177( S1, Mcond, MBodyCopy, S). + +eval177( N, _, N) :- + number177( N), !. +eval177( X, State, Val) :- % A program variable + atom( X), !, + memb( X = Val, State). +eval177( E1 + E2, State, Val) :- !, + eval177( E1, State, V1), + eval177( E2, State, V2), + Val is V1 + V2. +eval177( E1 - E2, State, Val) :- !, + eval177( E1, State, V1), + eval177( E2, State, V2), + Val is V1 - V2. +eval177( E1 * E2, State, Val) :- !, + eval177( E1, State, V1), + eval177( E2, State, V2), + Val is V1 * V2. +eval177( E1 / E2, State, Val) :- !, + eval177( E1, State, V1), + eval177( E2, State, V2), + Val is V1 / V2. +''' diff --git a/prolog/problems/denotational_semantics/algol_if_3/en.py b/prolog/problems/denotational_semantics/algol_if_3/en.py new file mode 100644 index 0000000..6bc0cb8 --- /dev/null +++ b/prolog/problems/denotational_semantics/algol_if_3/en.py @@ -0,0 +1,20 @@ +id = 177 +name = 'algol_if/3' +slug = 'interpreter for mini-algol with if-statement' + +description = '''\ +<p>Extend the given DCG for mini-algol to support the if-statement. You can assume that both branches are present in every if-statement. Example:</p> +<pre> + % if a < b then + % print(a) + % else + % print(b) + % end + ?- _Program = [begin,if,a,<,b,then,print(a),else,print(b),end,end], + algol_if(_F, _Program, []), + apply([a=3,b=5], Output, _F). + Output = [a=3,b=5,printout=[3]]. +</pre> +''' + +hint = {} diff --git a/prolog/problems/denotational_semantics/prog_8puzzle_2/common.py b/prolog/problems/denotational_semantics/prog_8puzzle_2/common.py new file mode 100644 index 0000000..4cc9c9e --- /dev/null +++ b/prolog/problems/denotational_semantics/prog_8puzzle_2/common.py @@ -0,0 +1,17 @@ +id = 172 +group = 'denotational_semantics' +number = 81 +visible = True +facts = None + +solution = '''\ +prog_8puzzle --> [begin], instructs172, [end]. + +instructs172 --> instr172. +instructs172 --> instr172, instructs172. + +instr172 --> [left]. +instr172 --> [right]. +instr172 --> [up]. +instr172 --> [down]. +''' diff --git a/prolog/problems/denotational_semantics/prog_8puzzle_2/en.py b/prolog/problems/denotational_semantics/prog_8puzzle_2/en.py new file mode 100644 index 0000000..eebf07b --- /dev/null +++ b/prolog/problems/denotational_semantics/prog_8puzzle_2/en.py @@ -0,0 +1,10 @@ +id = 172 +name = 'prog_8puzzle/2' +slug = '8-puzzle-solving language' + +description = '''\ +<p>Write a DCG for solving 8-puzzles. The first symbol in every word is <code>[begin]</code>, followed by any sequence of "instruction" symbols from the set {<code>left</code>, <code>right</code>, <code>up</code>, <code>down</code>}, and finally <code>[end]</code>. The starting symbol should be named <code>prog_8puzzle</code>.</p> + +<p>Example words: <code>[begin,left,down,right,end]</code>, <code>[begin,down,end]</code>.</p>''' + +hint = {} diff --git a/prolog/problems/denotational_semantics/prog_8puzzle_3/common.py b/prolog/problems/denotational_semantics/prog_8puzzle_3/common.py new file mode 100644 index 0000000..415dc17 --- /dev/null +++ b/prolog/problems/denotational_semantics/prog_8puzzle_3/common.py @@ -0,0 +1,37 @@ +id = 173 +group = 'denotational_semantics' +number = 82 +visible = True +facts = 'denotational_semantics_aux__predicates' + +solution = '''\ +prog_8puzzle(R0 --> R) --> + [begin], + { findblank(R0,C0) }, + instructs173(((R0,C0) --> (R,_C))), + [end]. + +instructs173((R0,C0) --> (R,C)) --> + instr173((R0,C0) --> (R,C)). +instructs173((R0,C0) --> (R,C)) --> + instr173((R0,C0) --> (R1,C1)), instructs173((R1,C1) --> (R,C)). + +instr173((R0,C0) --> (R,C)) --> + [left], {Pos is (C0-1) mod 3, + (Pos>0, C is C0-1, swap(R0,C0,C,R) + ; + Pos=0, C=C0, R=R0)}. +instr173((R0,C0) --> (R,C)) --> + [right], {Pos is (C0-1) mod 3, + (Pos<2, C is C0+1, swap(R0,C0,C,R) + ; + Pos=2, C=C0, R=R0)}. +instr173((R0,C0) --> (R,C)) --> + [up], { (C0>3, C is C0-3, swap(R0,C0,C,R) + ; + C0=<3, C=C0, R=R0)}. +instr173((R0,C0) --> (R,C)) --> + [down], { (C0=<6, C is C0+3, swap(R0,C0,C,R) + ; + C0>6, C=C0, R=R0)}. +''' diff --git a/prolog/problems/denotational_semantics/prog_8puzzle_3/en.py b/prolog/problems/denotational_semantics/prog_8puzzle_3/en.py new file mode 100644 index 0000000..c91b9e3 --- /dev/null +++ b/prolog/problems/denotational_semantics/prog_8puzzle_3/en.py @@ -0,0 +1,19 @@ +id = 173 +name = 'prog_8puzzle/3' +slug = '8-puzzle-solving language with semantics' + +description = '''\ +<p>Write a DCG for solving 8-puzzles. The syntax for this language should be the same as in the previous exercise: the first symbol in every word is <code>[begin]</code>, followed by any sequence of "instruction" symbols from the set {<code>left</code>, <code>right</code>, <code>up</code>, <code>down</code>}, and finally <code>[end]</code>. The starting symbol should be named <code>prog_8puzzle</code>.</p> + +<p>The meaning of a word (program) in this language has the form <code>In-->Out</code>, mapping from input to output states. Each state is a (permuted) list of numbers from 0 to 8, where 0 stands for the empty square and other numbers for the corresponding tiles. The first three numbers in the list correspond to the top row of the 8-puzzle, the next three numbers to the middle row, and the last three numbers to the last row. The meaning of instructions <code>left</code>, <code>right</code>, <code>up</code> and <code>down</code> is to move the blank tile in the given direction.</p> + +<pre> + ?- prog_8puzzle([0,1,2,3,4,5,6,7,8]-->Out, [begin,down,right,end], []). + Out = [3,1,2,4,0,5,6,7,8]. +</pre> + +<p>Helper predicates (already defined):<br /> + <code>findblank(List,I)</code> returns the 1-based index <code>I</code> of the element 0 in <code>List</code><br /> + <code>swap(List,I,J,NewList)</code> creates <code>NewList</code> by swapping elements <code>I</code> and <code>J</code> in <code>List</code></p>''' + +hint = {} diff --git a/prolog/problems/denotational_semantics/prog_listswap_2/common.py b/prolog/problems/denotational_semantics/prog_listswap_2/common.py new file mode 100644 index 0000000..ae1c220 --- /dev/null +++ b/prolog/problems/denotational_semantics/prog_listswap_2/common.py @@ -0,0 +1,16 @@ +id = 175 +group = 'denotational_semantics' +number = 79 +visible = True +facts = None + +solution = '''\ +program --> [begin], instructs175, [end]. + +instructs175 --> instr175. +instructs175 --> instr175, instructs175. + +instr175 --> [left]. +instr175 --> [right]. +instr175 --> [swap]. +''' diff --git a/prolog/problems/denotational_semantics/prog_listswap_2/en.py b/prolog/problems/denotational_semantics/prog_listswap_2/en.py new file mode 100644 index 0000000..4dd0ed5 --- /dev/null +++ b/prolog/problems/denotational_semantics/prog_listswap_2/en.py @@ -0,0 +1,11 @@ +id = 175 +name = 'prog_listswap/2' +slug = 'list-manipulation language' + +description = '''\ +<p>Write a DCG for manipulating list elements. The first symbol in every word is <code>[begin]</code>, followed by any sequence of "instruction" symbols from the set {<code>left</code>, <code>right</code>, <code>swap</code>}, and finally <code>[end]</code>. The starting symbol should be named <code>prog_listswap</code>.</p> + +<p>Example words: <code>[begin,right,swap,end]</code>, <code>[begin,right,left,end]</code>.</p> +''' + +hint = {} diff --git a/prolog/problems/denotational_semantics/prog_listswap_3/common.py b/prolog/problems/denotational_semantics/prog_listswap_3/common.py new file mode 100644 index 0000000..110890d --- /dev/null +++ b/prolog/problems/denotational_semantics/prog_listswap_3/common.py @@ -0,0 +1,24 @@ +id = 174 +group = 'denotational_semantics' +number = 80 +visible = True +facts = 'denotational_semantics_aux__predicates' + +solution = '''\ +prog_listswap(In-->Out) --> + [begin], instructs174((In,1)-->(Out,_)), [end]. + +instructs174((R0,C0)-->(R,C)) --> + instr174((R0,C0)-->(R,C)). +instructs174((R0,C0)-->(R,C)) --> + instr174((R0,C0)-->(R1,C1)), + instructs174((R1,C1)-->(R,C)). + +instr174((R0,C0)-->(R0,C)) --> + [left], { C0 > 1, C is C0 - 1 ; C0 =< 1, C is C0 }. +instr174((R0,C0)-->(R0,C)) --> + [right], { length(R0, LenR0), + ( C0 < LenR0, C is C0 + 1 ; C0 >= LenR0, C is C0 ) }. + +instr174((R0,C0)-->(R,C0)) --> + [swap], {swap(R0,C0,R)}.''' diff --git a/prolog/problems/denotational_semantics/prog_listswap_3/en.py b/prolog/problems/denotational_semantics/prog_listswap_3/en.py new file mode 100644 index 0000000..1a7cb79 --- /dev/null +++ b/prolog/problems/denotational_semantics/prog_listswap_3/en.py @@ -0,0 +1,18 @@ +id = 174 +name = 'prog_listswap/3' +slug = 'list-manipulation language with semantics' + +description = '''\ +<p>Write a DCG for manipulating list elements. The first symbol in every word is <code>[begin]</code>, followed by any sequence of "instruction" symbols from the set {<code>left</code>, <code>right</code>, <code>swap</code>}, and finally <code>[end]</code>. The starting symbol should be named <code>prog_listswap</code>.</p> + +<p>The meaning of a word (program) in this language has the form <code>In-->Out</code>, mapping from input to output lists. Besides the list contents, internal states also hold the current cursor position. The <code>left</code> and <code>right</code> instructions move the cursor one step in the given direction, while the <code>swap</code> instruction swaps the element under the cursor with its left neighbor (and fails if cursor is currently pointing to the first element of the list).</p> + +<pre> + ?- prog_listswap([1,2,3,4]-->Out, [begin,right,swap,end], []). + Out = [2,1,3,4]. +</pre> + +<p>Helper predicate (already defined):<br /> + <code>swap(List,I,NewList)</code> creates <code>NewList</code> by swapping the <code>I</code>th element with its left neighbor in <code>List</code></p>''' + +hint = {} diff --git a/prolog/problems/family_relations/ancestor_2/common.py b/prolog/problems/family_relations/ancestor_2/common.py new file mode 100644 index 0000000..61472b6 --- /dev/null +++ b/prolog/problems/family_relations/ancestor_2/common.py @@ -0,0 +1,13 @@ +id = 100 +group = 'family_relations' +number = 7 +visible = True +facts = 'family_relations' + +solution = '''\ +ancestor(X, Y) :- + parent(X, Y). +ancestor(X, Y) :- + parent(X, Z), + ancestor(Z, Y). +''' diff --git a/prolog/problems/family_relations/ancestor_2/en.py b/prolog/problems/family_relations/ancestor_2/en.py new file mode 100644 index 0000000..4853e15 --- /dev/null +++ b/prolog/problems/family_relations/ancestor_2/en.py @@ -0,0 +1,14 @@ +id = 100 +name = 'ancestor/2' +slug = 'the ancestor relation' + +description = '''\ +<p><code>ancestor(X, Y)</code>: <code>X</code> is an ancestor (parent, grandparent,...) of <code>Y</code>.</p> +<pre> + ?- ancestor(patricia, X). + X = john ; + X = michael ; + X = michelle. +</pre>''' + +hint = {} diff --git a/prolog/problems/family_relations/aunt_2/common.py b/prolog/problems/family_relations/aunt_2/common.py new file mode 100644 index 0000000..78e98c5 --- /dev/null +++ b/prolog/problems/family_relations/aunt_2/common.py @@ -0,0 +1,17 @@ +id = 98 +group = 'family_relations' +number = 5 +visible = True +facts = 'family_relations' + +solution = '''\ +sister98(X, Y) :- + parent(P, X), + parent(P, Y), + female(X), + X \== Y. + +aunt(X, Y) :- + sister98(X, Z), + parent(Z, Y). +''' diff --git a/prolog/problems/family_relations/aunt_2/en.py b/prolog/problems/family_relations/aunt_2/en.py new file mode 100644 index 0000000..95780a1 --- /dev/null +++ b/prolog/problems/family_relations/aunt_2/en.py @@ -0,0 +1,13 @@ +id = 98 +name = 'aunt/2' +slug = 'the aunt relation' + +description = '''\ +<p><code>aunt(X, Y)</code>: <code>X</code> is an aunt of <code>Y</code>.</p> +<pre> + ?- aunt(sally, X). + X = vanessa ; + X = patricia. +</pre>''' + +hint = {} diff --git a/prolog/problems/family_relations/brother_2/common.py b/prolog/problems/family_relations/brother_2/common.py new file mode 100644 index 0000000..c339644 --- /dev/null +++ b/prolog/problems/family_relations/brother_2/common.py @@ -0,0 +1,13 @@ +id = 97 +group = 'family_relations' +number = 4 +visible = True +facts = 'family_relations' + +solution = '''\ +brother(X, Y) :- + parent(P, X), + parent(P, Y), + male(X), + X \== Y. +''' diff --git a/prolog/problems/family_relations/brother_2/en.py b/prolog/problems/family_relations/brother_2/en.py new file mode 100644 index 0000000..8cae8b8 --- /dev/null +++ b/prolog/problems/family_relations/brother_2/en.py @@ -0,0 +1,13 @@ +id = 97 +name = 'brother/2' +slug = 'the brother relation' + +description = '''\ +<p><code>brother(X, Y)</code>: <code>X</code> is a brother of <code>Y</code>.</p> +<pre> + ?- brother(jeffrey, X). + X = william ; + X = sally. +</pre>''' + +hint = {} diff --git a/prolog/problems/family_relations/connected_3/common.py b/prolog/problems/family_relations/connected_3/common.py new file mode 100644 index 0000000..9a68d36 --- /dev/null +++ b/prolog/problems/family_relations/connected_3/common.py @@ -0,0 +1,16 @@ +id = 102 +group = 'family_relations' +number = 9 +visible = True +facts = 'family_relations' + +solution = '''\ +connected(X, X, _). +connected(X, Y, N) :- + N > 0, + N1 is N - 1, + ( parent(X, Z) + ; + parent(Z, X) ), + connected(Z, Y, N1). +''' diff --git a/prolog/problems/family_relations/connected_3/en.py b/prolog/problems/family_relations/connected_3/en.py new file mode 100644 index 0000000..8fe1eed --- /dev/null +++ b/prolog/problems/family_relations/connected_3/en.py @@ -0,0 +1,14 @@ +id = 102 +name = 'connected/3' +slug = 'check if two people are connected in the family tree' + +description = '''\ +<p><code>connected(X, Y, N)</code>: <code>X</code> and <code>Y</code> are connected with a series of (no more than <code>N</code>) parent/child relations.</p> +<pre> + ?- connected(ana, morty, 10). + false. + ?- connected(ana, margaret, 10). + true. +</pre>''' + +hint = {} diff --git a/prolog/problems/family_relations/cousin_2/common.py b/prolog/problems/family_relations/cousin_2/common.py new file mode 100644 index 0000000..9285a80 --- /dev/null +++ b/prolog/problems/family_relations/cousin_2/common.py @@ -0,0 +1,26 @@ +id = 99 +group = 'family_relations' +number = 6 +visible = True +facts = 'family_relations' + +solution = '''\ +sister99(X, Y) :- + parent(P, X), + parent(P, Y), + female(X), + X \== Y. + +brother99(X, Y) :- + parent(P, X), + parent(P, Y), + male(X), + X \== Y. + +cousin(X, Y) :- + parent(PX, X), + parent(PY, Y), + ( brother99(PX, PY) + ; + sister99(PX, PY) ). +''' diff --git a/prolog/problems/family_relations/cousin_2/en.py b/prolog/problems/family_relations/cousin_2/en.py new file mode 100644 index 0000000..72faa60 --- /dev/null +++ b/prolog/problems/family_relations/cousin_2/en.py @@ -0,0 +1,13 @@ +id = 99 +name = 'cousin/2' +slug = 'the cousin relation' + +description = '''\ +<p><code>cousin(X, Y)</code>: <code>X</code> is a cousin (male or female) of <code>Y</code>.</p> +<pre> + ?- cousin(andrew, X). + X = vanessa ; + X = patricia. +</pre>''' + +hint = {} diff --git a/prolog/problems/family_relations/descendant_2/common.py b/prolog/problems/family_relations/descendant_2/common.py new file mode 100644 index 0000000..408b3c7 --- /dev/null +++ b/prolog/problems/family_relations/descendant_2/common.py @@ -0,0 +1,13 @@ +id = 101 +group = 'family_relations' +number = 8 +visible = True +facts = 'family_relations' + +solution = '''\ +descendant(X, Y) :- + parent(Y, X). +descendant(X, Y) :- + parent(Y, Z), + descendant(X, Z). +''' diff --git a/prolog/problems/family_relations/descendant_2/en.py b/prolog/problems/family_relations/descendant_2/en.py new file mode 100644 index 0000000..d4ac794 --- /dev/null +++ b/prolog/problems/family_relations/descendant_2/en.py @@ -0,0 +1,14 @@ +id = 101 +name = 'descendant/2' +slug = 'the descendant relation' + +description = '''\ +<p><code>descendant(X, Y)</code>: <code>X</code> is a descendant (child, grandchild,...) of <code>Y</code>.</p> +<pre> + ?- descendant(patricia, X). + X = william ; + X = tina ; + X = thomas. +</pre>''' + +hint = {} diff --git a/prolog/problems/family_relations/grandparent_2/common.py b/prolog/problems/family_relations/grandparent_2/common.py new file mode 100644 index 0000000..12b7c0d --- /dev/null +++ b/prolog/problems/family_relations/grandparent_2/common.py @@ -0,0 +1,11 @@ +id = 95 +group = 'family_relations' +number = 2 +visible = True +facts = 'family_relations' + +solution = '''\ +grandparent(X, Y) :- + parent(X, Z), + parent(Z, Y). +''' diff --git a/prolog/problems/family_relations/grandparent_2/en.py b/prolog/problems/family_relations/grandparent_2/en.py new file mode 100644 index 0000000..cdc9cec --- /dev/null +++ b/prolog/problems/family_relations/grandparent_2/en.py @@ -0,0 +1,15 @@ +id = 95 +name = 'grandparent/2' +slug = 'the grandparent relation' + +description = '''\ +<p><code>grandparent(P, C)</code>: <code>P</code> is a grandparent of <code>C</code>.</p> +<pre> + ?- grandparent(tina, X). + X = vanessa ; + X = patricia. + ?- grandparent(tina, vanessa). + true. +</pre>''' + +hint = {} diff --git a/prolog/problems/family_relations/mother_2/common.py b/prolog/problems/family_relations/mother_2/common.py new file mode 100644 index 0000000..6c75823 --- /dev/null +++ b/prolog/problems/family_relations/mother_2/common.py @@ -0,0 +1,11 @@ +id = 94 +group = 'family_relations' +number = 1 +visible = True +facts = 'family_relations' + +solution = '''\ +mother(X, Y) :- + parent(X, Y), + female(X). +''' diff --git a/prolog/problems/family_relations/mother_2/en.py b/prolog/problems/family_relations/mother_2/en.py new file mode 100644 index 0000000..9f1c098 --- /dev/null +++ b/prolog/problems/family_relations/mother_2/en.py @@ -0,0 +1,15 @@ +id = 94 +name = 'mother/2' +slug = 'the mother-child relation' + +description = '''\ +<p><code>mother(M, C)</code>: <code>M</code> is the mother of <code>C</code>.</p> +<pre> + ?- mother(tina, william). + true. + ?- mother(nevia, X). + X = luana ; + X = daniela. +</pre>''' + +hint = {} diff --git a/prolog/problems/family_relations/sister_2/common.py b/prolog/problems/family_relations/sister_2/common.py new file mode 100644 index 0000000..75a2b62 --- /dev/null +++ b/prolog/problems/family_relations/sister_2/common.py @@ -0,0 +1,13 @@ +id = 96 +group = 'family_relations' +number = 3 +visible = True +facts = 'family_relations' + +solution = '''\ +sister(X, Y) :- + parent(P, X), + parent(P, Y), + female(X), + X \== Y. +''' diff --git a/prolog/problems/family_relations/sister_2/en.py b/prolog/problems/family_relations/sister_2/en.py new file mode 100644 index 0000000..140b76f --- /dev/null +++ b/prolog/problems/family_relations/sister_2/en.py @@ -0,0 +1,12 @@ +id = 96 +name = 'sister/2' +slug = 'the sister relation' + +description = '''\ +<p><code>sister(X, Y)</code>: <code>X</code> is a sister of <code>Y</code>.</p> +<pre> + ?- sister(vanessa, X). + X = patricia. +</pre>''' + +hint = {} diff --git a/prolog/problems/license_plates/checklicenseplate_3/common.py b/prolog/problems/license_plates/checklicenseplate_3/common.py new file mode 100644 index 0000000..f926481 --- /dev/null +++ b/prolog/problems/license_plates/checklicenseplate_3/common.py @@ -0,0 +1,52 @@ +id = 148 +group = 'license_plates' +number = 55 +visible = True +facts = None + +solution = '''\ +conc148([], L, L). +conc148([H|T], L2, [H|L]) :- + conc148(T, L2, L). + +memb148(X, [X|_]). +memb148(X, [_|T]) :- + memb148(X, T). + +getdigits148([], []). +getdigits148([X|T], [X|NT]) :- + number(X), !, + getdigits148(T, NT). +getdigits148([_|T], NT) :- + getdigits148(T, NT). + +joindigits148([X], [X]). +joindigits148([X,Y|T], NT) :- + XY is 10*X + Y, + joindigits148([XY|T], NT). +joindigits148([X,Y|T], [X|NT]) :- + joindigits148([Y|T], NT). + +genexp148([Exp], Exp). +genexp148(L, Exp) :- + conc148(Before, [N1,N2|After], L), + memb148(Op, ['+','-','*','/']), + NExp =.. [Op, N1, N2], + conc148(Before, [NExp|After], L1), + genexp148(L1, Exp). + +firstMinus148(L, L). +firstMinus148([X|T], [Y|T]) :- + Y is -X. + +checkLicensePlate(LP, E1, E2) :- + getdigits148(LP, Digs), + conc148(L1, L2, Digs), + joindigits148(L1, N1), + joindigits148(L2, N2), + firstMinus148(N1, MN1), + firstMinus148(N2, MN2), + genexp148(MN1, E1), + genexp148(MN2, E2), + E1 =:= E2. +''' diff --git a/prolog/problems/license_plates/checklicenseplate_3/en.py b/prolog/problems/license_plates/checklicenseplate_3/en.py new file mode 100644 index 0000000..1f3ea94 --- /dev/null +++ b/prolog/problems/license_plates/checklicenseplate_3/en.py @@ -0,0 +1,17 @@ +id = 148 +name = 'checkLicensePlate/3' +slug = 'check if the numbers in a license plate form an equation' + +description = '''\ +<p><code>checkLicensePlate(LP, E1, E2)</code>: the digits in the list <code>LP</code> can be combined into a valid equation <code>E1</code> = <code>E2</code>. <code>E1</code> and <code>E2</code> are arithmetic expressions, obtained from sublists of <code>Plate</code> by inserting arithmetic operators (<code>+</code>, <code>-</code>, <code>*</code> and <code>/</code>) between elements. An additional unary minus can be inserted before the leftmost number of <code>E1</code> and <code>E2</code>.</p> +<pre> + ?- checkLicensePlate([l,j,l,3,-,2,1,7], E1, E2). + E1 = 3, E2 = 21/7 ; + E1 = -3, E2 = -21/7 ; + E1 = 3*2, E2 = -1+7 ; + E1 = -3*2, E2 = 1-7 ; + E1 = 3*2+1, E2 = 7 ; + E1 = -3*2-1, E2 = -7. +</pre>''' + +hint = {} diff --git a/prolog/problems/license_plates/firstminus_2/common.py b/prolog/problems/license_plates/firstminus_2/common.py new file mode 100644 index 0000000..9e971f6 --- /dev/null +++ b/prolog/problems/license_plates/firstminus_2/common.py @@ -0,0 +1,11 @@ +id = 147 +group = 'license_plates' +number = 54 +visible = True +facts = None + +solution = '''\ +firstMinus(L, L). +firstMinus([X|T], [Y|T]) :- + Y is -X. +''' diff --git a/prolog/problems/license_plates/firstminus_2/en.py b/prolog/problems/license_plates/firstminus_2/en.py new file mode 100644 index 0000000..9fb8c69 --- /dev/null +++ b/prolog/problems/license_plates/firstminus_2/en.py @@ -0,0 +1,13 @@ +id = 147 +name = 'firstMinus/2' +slug = 'negate the first element in a list of numbers' + +description = '''\ +<p><code>firstMinus(L1, L2)</code>: the list <code>L2</code> is the same as <code>L1</code>, except for the first element that may be negated. Your code should return both solutions.</p> +<pre> + ?- firstMinus([1,2,3], L). + L = [1,2,3] ; + L = [-1,2,3]. +</pre>''' + +hint = {} diff --git a/prolog/problems/license_plates/genexp_2/common.py b/prolog/problems/license_plates/genexp_2/common.py new file mode 100644 index 0000000..a91c392 --- /dev/null +++ b/prolog/problems/license_plates/genexp_2/common.py @@ -0,0 +1,23 @@ +id = 146 +group = 'license_plates' +number = 53 +visible = True +facts = None + +solution = '''\ +memb146(X, [X|_]). +memb146(X, [_|T]) :- + memb146(X, T). + +conc146([], L, L). +conc146([H|T], L2, [H|L]) :- + conc146(T, L2, L). + +genexp([Exp], Exp). +genexp(L, Exp) :- + conc146(Before, [N1,N2|After], L), + memb146(Op, ['+','-','*','/']), + NExp =.. [Op, N1, N2], + conc146(Before, [NExp|After], L1), + genexp(L1, Exp). +''' diff --git a/prolog/problems/license_plates/genexp_2/en.py b/prolog/problems/license_plates/genexp_2/en.py new file mode 100644 index 0000000..c5c61fb --- /dev/null +++ b/prolog/problems/license_plates/genexp_2/en.py @@ -0,0 +1,18 @@ +id = 146 +name = 'genexp/2' +slug = 'generate an arithmetic expression from a list' + +description = '''\ +<p><code>genexp(L, E)</code>: the expression <code>E</code> is obtained from the list <code>L</code> by inserting arithmetic operators between list elements. Your code should generate all valid solutions.</p> +<pre> + ?- genexp([1,2,3], L). + L = 1+2+3 ; + L = 1+2-3 ; + L = (1+2)*3 ; + L = (1+2)/3 ; + L = 1-2+3 ; + L = 1-2-3 ; + ... +</pre>''' + +hint = {} diff --git a/prolog/problems/license_plates/getdigits_2/common.py b/prolog/problems/license_plates/getdigits_2/common.py new file mode 100644 index 0000000..8d6e890 --- /dev/null +++ b/prolog/problems/license_plates/getdigits_2/common.py @@ -0,0 +1,14 @@ +id = 144 +group = 'license_plates' +number = 51 +visible = True +facts = None + +solution = '''\ +getdigits([], []). +getdigits([X|T], [X|NT]) :- + number(X), !, + getdigits(T, NT). +getdigits([_|T], NT) :- + getdigits(T, NT). +''' diff --git a/prolog/problems/license_plates/getdigits_2/en.py b/prolog/problems/license_plates/getdigits_2/en.py new file mode 100644 index 0000000..06bfa22 --- /dev/null +++ b/prolog/problems/license_plates/getdigits_2/en.py @@ -0,0 +1,12 @@ +id = 144 +name = 'getdigits/2' +slug = 'remove non-numeric elements from a list' + +description = '''\ +<p><code>getdigits(L, DL)</code>: the list <code>DL</code> contains the numeric elements of <code>L</code>, in the same order as in the original list.</p> +<pre> + ?- getdigits([2,3,e,-,4,b], DL). + DL = [2,3,4]. +</pre>''' + +hint = {} diff --git a/prolog/problems/license_plates/joindigits_2/common.py b/prolog/problems/license_plates/joindigits_2/common.py new file mode 100644 index 0000000..dc3e4a5 --- /dev/null +++ b/prolog/problems/license_plates/joindigits_2/common.py @@ -0,0 +1,14 @@ +id = 145 +group = 'license_plates' +number = 52 +visible = True +facts = None + +solution = '''\ +joindigits([X], [X]). +joindigits([X,Y|T], NT) :- + XY is 10*X + Y, + joindigits([XY|T], NT). +joindigits([X,Y|T], [X|NT]) :- + joindigits([Y|T], NT). +''' diff --git a/prolog/problems/license_plates/joindigits_2/en.py b/prolog/problems/license_plates/joindigits_2/en.py new file mode 100644 index 0000000..19623d7 --- /dev/null +++ b/prolog/problems/license_plates/joindigits_2/en.py @@ -0,0 +1,15 @@ +id = 145 +name = 'joindigits/2' +slug = 'join adjacent numbers in a list' + +description = '''\ +<p><code>joindigits(L, NL)</code>: the list <code>NL</code> is obtained from <code>L</code> by arbitrarily joining neighboring digits. Your code should generate all valid solutions.</p> +<pre> + ?- joindigits([3,2,4], NL). + NL = [324] ; + NL = [32,4] ; + NL = [3,24] ; + NL = [3,2,4]. +</pre>''' + +hint = {} diff --git a/prolog/problems/lists/conc_3/common.py b/prolog/problems/lists/conc_3/common.py new file mode 100644 index 0000000..29a3919 --- /dev/null +++ b/prolog/problems/lists/conc_3/common.py @@ -0,0 +1,11 @@ +id = 104 +group = 'lists' +number = 12 +visible = True +facts = None + +solution = '''\ +conc([], L, L). +conc([H|T], L2, [H|L]) :- + conc(T, L2, L). +''' diff --git a/prolog/problems/lists/conc_3/en.py b/prolog/problems/lists/conc_3/en.py new file mode 100644 index 0000000..3e127c0 --- /dev/null +++ b/prolog/problems/lists/conc_3/en.py @@ -0,0 +1,14 @@ +id = 104 +name = 'conc/3' +slug = 'concatenate two lists' + +description = '''\ +<p><code>conc(L1, L2, L)</code>: the list <code>L</code> is obtained by appending the elements of <code>L2</code> to <code>L1</code>.</p> +<pre> + ?- conc([1,2], [3,4], X). + X = [1,2,3,4]. + ?- conc(X, [], [1,2,3]). + X = [1,2,3]. +</pre>''' + +hint = {} diff --git a/prolog/problems/lists/count_3/common.py b/prolog/problems/lists/count_3/common.py new file mode 100644 index 0000000..583ad6b --- /dev/null +++ b/prolog/problems/lists/count_3/common.py @@ -0,0 +1,15 @@ +id = 120 +group = 'lists' +number = 27 +visible = True +facts = None + +solution = '''\ +count(_, [], 0). +count(X, [X|T], N) :- + count(X, T, NT), + N is NT + 1. +count(X, [Y|T], NT) :- + X \== Y, + count(X, T, NT). +''' diff --git a/prolog/problems/lists/count_3/en.py b/prolog/problems/lists/count_3/en.py new file mode 100644 index 0000000..799594e --- /dev/null +++ b/prolog/problems/lists/count_3/en.py @@ -0,0 +1,12 @@ +id = 120 +name = 'count/3' +slug = 'find the number of occurrences of an element in list' + +description = '''\ +<p><code>count(X, L, N)</code>: <code>N</code> is the number of times the element <code>X</code> appears in the list <code>L</code>.</p> +<pre> + ?- count(1, [1,2,1,3,1], N). + N = 3. +</pre>''' + +hint = {} diff --git a/prolog/problems/lists/del_3/common.py b/prolog/problems/lists/del_3/common.py new file mode 100644 index 0000000..1e99959 --- /dev/null +++ b/prolog/problems/lists/del_3/common.py @@ -0,0 +1,11 @@ +id = 105 +group = 'lists' +number = 11 +visible = True +facts = None + +solution = '''\ +del(X, [X|T], T). +del(X, [Y|T], [Y|L]) :- + del(X, T, L). +''' diff --git a/prolog/problems/lists/del_3/en.py b/prolog/problems/lists/del_3/en.py new file mode 100644 index 0000000..a0f0cd3 --- /dev/null +++ b/prolog/problems/lists/del_3/en.py @@ -0,0 +1,19 @@ +id = 105 +name = 'del/3' +slug = 'delete an element from list' + +description = '''\ +<p><code>del(X, L1, L2)</code>: the list <code>L2</code> is obtained from <code>L1</code> by deleting element <code>X</code>.</p> +<pre> + ?- del(1, [1,2,3], L). + L = [2,3]. + ?- del(2, [1,2,3,2,5], L). + L = [1,3,2,5] ; + L = [1,2,3,5]. + ?- del(X, [1,2,3], L). + X = 1, L = [2,3] ; + X = 2, L = [1,3] ; + X = 3, L = [1,2]. +</pre>''' + +hint = {} diff --git a/prolog/problems/lists/divide_3/common.py b/prolog/problems/lists/divide_3/common.py new file mode 100644 index 0000000..901d2f4 --- /dev/null +++ b/prolog/problems/lists/divide_3/common.py @@ -0,0 +1,12 @@ +id = 115 +group = 'lists' +number = 22 +visible = True +facts = None + +solution = '''\ +divide([], [], []). +divide([X], [X], []). +divide([H1,H2|T], [H1|L1], [H2|L2]) :- + divide(T, L1, L2). +''' diff --git a/prolog/problems/lists/divide_3/en.py b/prolog/problems/lists/divide_3/en.py new file mode 100644 index 0000000..1a8d94e --- /dev/null +++ b/prolog/problems/lists/divide_3/en.py @@ -0,0 +1,14 @@ +id = 115 +name = 'divide/3' +slug = 'split a list into parts of roughly equal length' + +description = '''\ +<p><code>divide(L, L1, L2)</code>: the list <code>L1</code> contains elements at odd positions in <code>L</code>, and the list <code>L2</code> contains the elements at even positions in <code>L</code>.</p> +<pre> + ?- divide([a,b,c,d,e,f,g], X, Y). + X = [a,c,e,g], Y = [b,d,f]. + ?- divide([a,b,c,d,e,f], X, Y). + X = [a,c,e], Y = [b,d,f]. +</pre>''' + +hint = {} diff --git a/prolog/problems/lists/dup_2/common.py b/prolog/problems/lists/dup_2/common.py new file mode 100644 index 0000000..37a0842 --- /dev/null +++ b/prolog/problems/lists/dup_2/common.py @@ -0,0 +1,11 @@ +id = 110 +group = 'lists' +number = 17 +visible = True +facts = None + +solution = '''\ +dup([], []). +dup([H|T], [H,H|TT]) :- + dup(T, TT). +''' diff --git a/prolog/problems/lists/dup_2/en.py b/prolog/problems/lists/dup_2/en.py new file mode 100644 index 0000000..d6aef71 --- /dev/null +++ b/prolog/problems/lists/dup_2/en.py @@ -0,0 +1,14 @@ +id = 110 +name = 'dup/2' +slug = 'duplicate the elements of a list' + +description = '''\ +<p><code>dup(L1, L2)</code>: the list <code>L2</code> is obtained from <code>L1</code> by duplicating every element.</p> +<pre> + ?- dup([1,2], X). + X = [1,1,2,2]. + ?- dup([1,2,3], X). + X = [1,1,2,2,3,3]. +</pre>''' + +hint = {} diff --git a/prolog/problems/lists/evenlen_1_+_oddlen_1/common.py b/prolog/problems/lists/evenlen_1_+_oddlen_1/common.py new file mode 100644 index 0000000..2735965 --- /dev/null +++ b/prolog/problems/lists/evenlen_1_+_oddlen_1/common.py @@ -0,0 +1,15 @@ +id = 116 +group = 'lists' +number = 23 +visible = True +facts = None + +solution = '''\ +evenlen([]). +evenlen([_,_|T]) :- + evenlen(T). + +oddlen([_]). +oddlen([_,_|T]) :- + oddlen(T). +''' diff --git a/prolog/problems/lists/evenlen_1_+_oddlen_1/en.py b/prolog/problems/lists/evenlen_1_+_oddlen_1/en.py new file mode 100644 index 0000000..d1957d1 --- /dev/null +++ b/prolog/problems/lists/evenlen_1_+_oddlen_1/en.py @@ -0,0 +1,17 @@ +id = 116 +name = 'evenlen/1 + oddlen/1' +slug = 'check if the length of a list is even or odd' + +description = '''\ +<p><code>evenlen(L)</code>: the list <code>L</code> has an even number of elements.<br /> +<code>oddlen(L)</code>: the list <code>L</code> has an odd number of elements.</p> +<pre> + ?- oddlen([1,2,3,4,5]). + true. + ?- oddlen([1,2,3,4]). + false. + ?- evenlen([1,2,3,4]). + true. +</pre>''' + +hint = {} diff --git a/prolog/problems/lists/insert_3/common.py b/prolog/problems/lists/insert_3/common.py new file mode 100644 index 0000000..fa3a937 --- /dev/null +++ b/prolog/problems/lists/insert_3/common.py @@ -0,0 +1,13 @@ +id = 106 +group = 'lists' +number = 13 +visible = True +facts = None + +solution = '''\ +del106(X, [X|T], T). +del106(X, [Y|T], [Y|L]) :- + del106(X, T, L). +insert(X, List, BigList) :- + del106(X, BigList, List). +''' diff --git a/prolog/problems/lists/insert_3/en.py b/prolog/problems/lists/insert_3/en.py new file mode 100644 index 0000000..a4a1128 --- /dev/null +++ b/prolog/problems/lists/insert_3/en.py @@ -0,0 +1,14 @@ +id = 106 +name = 'insert/3' +slug = 'insert an element into list' + +description = '''\ +<p><code>insert(X, L1, L2)</code>: the list <code>L2</code> is obtained from <code>L1</code> by inserting the element <code>X</code> at arbitrary position.</p> +<pre> + ?- insert(1, [2,3], L). + L = [1,2,3] ; + L = [2,1,3] ; + L = [2,3,1]. +</pre>''' + +hint = {} diff --git a/prolog/problems/lists/len_2/common.py b/prolog/problems/lists/len_2/common.py new file mode 100644 index 0000000..62be9cc --- /dev/null +++ b/prolog/problems/lists/len_2/common.py @@ -0,0 +1,12 @@ +id = 119 +group = 'lists' +number = 26 +visible = True +facts = None + +solution = '''\ +len([], 0). +len([_|T], Len) :- + len(T, LenT), + Len is LenT + 1. +''' diff --git a/prolog/problems/lists/len_2/en.py b/prolog/problems/lists/len_2/en.py new file mode 100644 index 0000000..b3e277c --- /dev/null +++ b/prolog/problems/lists/len_2/en.py @@ -0,0 +1,12 @@ +id = 119 +name = 'len/2' +slug = 'find the length of a list' + +description = '''\ +<p><code>len(L, Len)</code>: <code>Len</code> is the length of the list <code>L</code>.</p> +<pre> + ?- len([1,2,3], Len). + Len = 3. +</pre>''' + +hint = {} diff --git a/prolog/problems/lists/max_2/common.py b/prolog/problems/lists/max_2/common.py new file mode 100644 index 0000000..65e5a70 --- /dev/null +++ b/prolog/problems/lists/max_2/common.py @@ -0,0 +1,14 @@ +id = 109 +group = 'lists' +number = 16 +visible = True +facts = None + +solution = '''\ +max([X], X). +max([H|T], Max):- + max(T, Max1), + ( H > Max1, Max is H + ; + H =< Max1, Max is Max1 ). +''' diff --git a/prolog/problems/lists/max_2/en.py b/prolog/problems/lists/max_2/en.py new file mode 100644 index 0000000..dfb4d60 --- /dev/null +++ b/prolog/problems/lists/max_2/en.py @@ -0,0 +1,14 @@ +id = 109 +name = 'max/2' +slug = 'find the largest element in list' + +description = '''\ +<p><code>max(L, Max)</code>: <code>Max</code> is the largest value in the list <code>L</code>.</p> +<pre> + ?- max([5,4,1,6], M). + M = 6. + ?- max([3,2,2], M). + M = 3. +</pre>''' + +hint = {} diff --git a/prolog/problems/lists/memb_2/common.py b/prolog/problems/lists/memb_2/common.py new file mode 100644 index 0000000..32d9125 --- /dev/null +++ b/prolog/problems/lists/memb_2/common.py @@ -0,0 +1,11 @@ +id = 103 +group = 'lists' +number = 10 +visible = True +facts = None + +solution = '''\ +memb(X, [X|_]). +memb(X, [_|T]) :- + memb(X, T). +''' diff --git a/prolog/problems/lists/memb_2/en.py b/prolog/problems/lists/memb_2/en.py new file mode 100644 index 0000000..fca82b7 --- /dev/null +++ b/prolog/problems/lists/memb_2/en.py @@ -0,0 +1,16 @@ +id = 103 +name = 'memb/2' +slug = 'find elements in list' + +description = '''\ +<p><code>memb(M, L)</code>: <code>M</code> is an element of list <code>L</code>.</p> +<pre> + ?- memb(X, [1,2,3]). + X = 1 ; + X = 2 ; + X = 3. + ?- memb(1, [3,2,X]). + X = 1. +</pre>''' + +hint = {} diff --git a/prolog/problems/lists/min_2/common.py b/prolog/problems/lists/min_2/common.py new file mode 100644 index 0000000..7e9a0bc --- /dev/null +++ b/prolog/problems/lists/min_2/common.py @@ -0,0 +1,14 @@ +id = 108 +group = 'lists' +number = 15 +visible = True +facts = None + +solution = '''\ +min([X], X). +min([H|T], Min):- + min(T, Min1), + ( H < Min1, Min is H + ; + H >= Min1, Min is Min1 ). +''' diff --git a/prolog/problems/lists/min_2/en.py b/prolog/problems/lists/min_2/en.py new file mode 100644 index 0000000..a0a8e74 --- /dev/null +++ b/prolog/problems/lists/min_2/en.py @@ -0,0 +1,14 @@ +id = 108 +name = 'min/2' +slug = 'find the smallest element' + +description = '''\ +<p><code>min(L, Min)</code>: <code>Min</code> is the smallest value in the list <code>L</code>.</p> +<pre> + ?- min([5,4,1,6], M). + M = 1. + ?- min([3,2,2], M). + M = 2. +</pre>''' + +hint = {} diff --git a/prolog/problems/lists/palindrome_1/common.py b/prolog/problems/lists/palindrome_1/common.py new file mode 100644 index 0000000..8929fd9 --- /dev/null +++ b/prolog/problems/lists/palindrome_1/common.py @@ -0,0 +1,17 @@ +id = 112 +group = 'lists' +number = 19 +visible = True +facts = None + +solution = '''\ +conc112([], L, L). +conc112([H|T], L2, [H|L]) :- + conc112(T, L2, L). +rev112([], []). +rev112([H|T], R):- + rev112(T, R1), + conc112(R1, [H], R). +palindrome(L) :- + rev112(L, L). +''' diff --git a/prolog/problems/lists/palindrome_1/en.py b/prolog/problems/lists/palindrome_1/en.py new file mode 100644 index 0000000..c1b8971 --- /dev/null +++ b/prolog/problems/lists/palindrome_1/en.py @@ -0,0 +1,14 @@ +id = 112 +name = 'palindrome/1' +slug = 'check if list is a palindrome' + +description = '''\ +<p><code>palindrome(L)</code>: the elements of list <code>L</code> are the same when read from the front or back of the list.</p> +<pre> + ?- palindrome([1,2,3,2,1]). + true. + ?- palindrome([1,2,3]). + false. +</pre>''' + +hint = {} diff --git a/prolog/problems/lists/permute_2/common.py b/prolog/problems/lists/permute_2/common.py new file mode 100644 index 0000000..8e0386c --- /dev/null +++ b/prolog/problems/lists/permute_2/common.py @@ -0,0 +1,15 @@ +id = 107 +group = 'lists' +number = 14 +visible = True +facts = None + +solution = '''\ +del107(X, [X|T], T). +del107(X, [Y|T], [Y|L]) :- + del107(X, T, L). +permute([], []). +permute(L, [X|P]) :- + del107(X, L, L1), + permute(L1, P). +''' diff --git a/prolog/problems/lists/permute_2/en.py b/prolog/problems/lists/permute_2/en.py new file mode 100644 index 0000000..8898c83 --- /dev/null +++ b/prolog/problems/lists/permute_2/en.py @@ -0,0 +1,17 @@ +id = 107 +name = 'permute/2' +slug = 'generate permutations of a list' + +description = '''\ +<p><code>permute(L1, L2)</code>: the list <code>L2</code> is a permutation of the elements of the list <code>L1</code>.</p> +<pre> + ?- permute([1,2,3], L). + L = [1,2,3] ; + L = [1,3,2] ; + L = [2,1,3] ; + L = [2,3,1] ; + L = [3,1,2] ; + L = [3,2,1]. +</pre>''' + +hint = {} diff --git a/prolog/problems/lists/rev_2/common.py b/prolog/problems/lists/rev_2/common.py new file mode 100644 index 0000000..79c5fca --- /dev/null +++ b/prolog/problems/lists/rev_2/common.py @@ -0,0 +1,15 @@ +id = 111 +group = 'lists' +number = 18 +visible = True +facts = None + +solution = '''\ +conc111([], L, L). +conc111([H|T], L2, [H|L]) :- + conc111(T, L2, L). +rev([], []). +rev([H|T], R):- + rev(T, R1), + conc111(R1, [H], R). +''' diff --git a/prolog/problems/lists/rev_2/en.py b/prolog/problems/lists/rev_2/en.py new file mode 100644 index 0000000..9cacc95 --- /dev/null +++ b/prolog/problems/lists/rev_2/en.py @@ -0,0 +1,14 @@ +id = 111 +name = 'rev/2' +slug = 'reverse a list' + +description = '''\ +<p><code>rev(L1, L2)</code>: the list <code>L2</code> is obtained from <code>L1</code> by reversing the order of the elements.</p> +<pre> + ?- rev([], X). + X = []. + ?- rev([1,2,3], X). + X = [3,2,1]. +</pre>''' + +hint = {} diff --git a/prolog/problems/lists/shiftleft_2/common.py b/prolog/problems/lists/shiftleft_2/common.py new file mode 100644 index 0000000..a8d56a7 --- /dev/null +++ b/prolog/problems/lists/shiftleft_2/common.py @@ -0,0 +1,13 @@ +id = 113 +group = 'lists' +number = 20 +visible = True +facts = None + +solution = '''\ +conc113([], L, L). +conc113([H|T], L2, [H|L]) :- + conc113(T, L2, L). +shiftleft([H|T], L2) :- + conc113(T, [H], L2). +''' diff --git a/prolog/problems/lists/shiftleft_2/en.py b/prolog/problems/lists/shiftleft_2/en.py new file mode 100644 index 0000000..0f4b807 --- /dev/null +++ b/prolog/problems/lists/shiftleft_2/en.py @@ -0,0 +1,12 @@ +id = 113 +name = 'shiftleft/2' +slug = 'shift a list left' + +description = '''\ +<p><code>shiftleft(L1, L2)</code>: the list <code>L2</code> is obtained from L1 by shifting elements to the left by one (circular shift).</p> +<pre> + ?- shiftleft([1,2,3,4,5], X). + X = [2,3,4,5,1]. +</pre>''' + +hint = {} diff --git a/prolog/problems/lists/shiftright_2/common.py b/prolog/problems/lists/shiftright_2/common.py new file mode 100644 index 0000000..3d5c3a5 --- /dev/null +++ b/prolog/problems/lists/shiftright_2/common.py @@ -0,0 +1,13 @@ +id = 114 +group = 'lists' +number = 21 +visible = True +facts = None + +solution = '''\ +conc114([], L, L). +conc114([H|T], L2, [H|L]) :- + conc114(T, L2, L). +shiftright(L1, [H|T]) :- + conc114(T, [H], L1). +''' diff --git a/prolog/problems/lists/shiftright_2/en.py b/prolog/problems/lists/shiftright_2/en.py new file mode 100644 index 0000000..8e2a57c --- /dev/null +++ b/prolog/problems/lists/shiftright_2/en.py @@ -0,0 +1,12 @@ +id = 114 +name = 'shiftright/2' +slug = 'shift a list right' + +description = '''\ +<p><code>shiftright(L1, L2)</code>: the list <code>L2</code> is obtained from L1 by shifting elements to the right by one (circular shift).</p> +<pre> + ?- shiftright([1,2,3,4,5], X). + X = [5,1,2,3,4]. +</pre>''' + +hint = {} diff --git a/prolog/problems/lists/sublist_2/common.py b/prolog/problems/lists/sublist_2/common.py new file mode 100644 index 0000000..84c0bc8 --- /dev/null +++ b/prolog/problems/lists/sublist_2/common.py @@ -0,0 +1,14 @@ +id = 117 +group = 'lists' +number = 24 +visible = True +facts = None + +solution = '''\ +conc117([], L, L). +conc117([H|T], L2, [H|L]) :- + conc117(T, L2, L). +sublist(L, S) :- + conc117(_, T, L), + conc117(S, _, T). +''' diff --git a/prolog/problems/lists/sublist_2/en.py b/prolog/problems/lists/sublist_2/en.py new file mode 100644 index 0000000..5b6808b --- /dev/null +++ b/prolog/problems/lists/sublist_2/en.py @@ -0,0 +1,18 @@ +id = 117 +name = 'sublist/2' +slug = 'generate sublists of a list' + +description = '''\ +<p><code>sublist(L, SL)</code>: <code>SL</code> is a continuous sublist of the list <code>L</code>.</p> +<pre> + ?- sublist([1,2,3], X). + X = [] ; + X = [1] ; + X = [1,2] ; + X = [1,2,3] ; + X = [2] ; + X = [2,3] ; + X = [3]. +</pre>''' + +hint = {} diff --git a/prolog/problems/lists/sum_2/common.py b/prolog/problems/lists/sum_2/common.py new file mode 100644 index 0000000..14b0614 --- /dev/null +++ b/prolog/problems/lists/sum_2/common.py @@ -0,0 +1,12 @@ +id = 118 +group = 'lists' +number = 25 +visible = True +facts = None + +solution = '''\ +sum([], 0). +sum([H|T], Sum) :- + sum(T, SumT), + Sum is SumT + H. +''' diff --git a/prolog/problems/lists/sum_2/en.py b/prolog/problems/lists/sum_2/en.py new file mode 100644 index 0000000..8db0e67 --- /dev/null +++ b/prolog/problems/lists/sum_2/en.py @@ -0,0 +1,12 @@ +id = 118 +name = 'sum/2' +slug = 'find the sum of all elements in list' + +description = '''\ +<p><code>sum(L, Sum)</code>: <code>Sum</code> is the sum of all elements in the list <code>L</code>.</p> +<pre> + ?- sum([1,2,3], Sum). + Sum = 6. +</pre>''' + +hint = {} diff --git a/prolog/problems/old_exams/pascal_3/common.py b/prolog/problems/old_exams/pascal_3/common.py new file mode 100644 index 0000000..7fcb55e --- /dev/null +++ b/prolog/problems/old_exams/pascal_3/common.py @@ -0,0 +1,16 @@ +id = 179 +group = 'old_exams' +number = 86 +visible = False +facts = None + +solution = '''\ +pascal(_, 0, 1) :- !. +pascal(I, I, 1) :- !. +pascal(I, J, N) :- + I1 is I - 1, + J1 is J - 1, + pascal(I1, J, N1), + pascal(I1, J1, N2), + N is N1 + N2. +''' diff --git a/prolog/problems/old_exams/pascal_3/en.py b/prolog/problems/old_exams/pascal_3/en.py new file mode 100644 index 0000000..31a0d47 --- /dev/null +++ b/prolog/problems/old_exams/pascal_3/en.py @@ -0,0 +1,26 @@ +id = 179 +name = 'pascal/3' +slug = 'pascal's triangle' + +description = '''\ +<p>The first five rows of the Pascal's triangle look like this:</p> +<pre> + 1 + 1 1 + 1 2 1 + 1 3 3 1 + 1 4 6 4 1 +</pre> +<p> +Each row begins and ends with 1. Every other element can be obtained as a sum of the two values above it. Write the predicate <code>pascal(I,J,N)</code> that returns the <code>J</code>-th value in the <code>I</code>-th column of the Pascal's triangle. Your solution should return exactly one answer for any input (the <code>I</code> and <code>J</code> arguments start counting with 0; you can assume that 0 ≤ <code>J</code> ≤ <code>I</code>). + +<pre> + ?- pascal(0, 0, N). + N = 1. + ?- pascal(2, 1, N). + N = 2. + ?- pascal(4, 3, N). + N = 4. +</pre>''' + +hint = {} diff --git a/prolog/problems/other/genlist_4/common.py b/prolog/problems/other/genlist_4/common.py new file mode 100644 index 0000000..388c041 --- /dev/null +++ b/prolog/problems/other/genlist_4/common.py @@ -0,0 +1,14 @@ +id = 127 +group = 'other' +number = 34 +visible = False +facts = None + +solution = '''\ +genlist([], 0, _, _). +genlist([H|T], N, Min, Max):- + N > 0, + N1 is N - 1, + genlist(T, N1, Min, Max), + random(Min, Max, H). +''' diff --git a/prolog/problems/other/genlist_4/en.py b/prolog/problems/other/genlist_4/en.py new file mode 100644 index 0000000..488ccf2 --- /dev/null +++ b/prolog/problems/other/genlist_4/en.py @@ -0,0 +1,12 @@ +id = 127 +name = 'genlist/4' +slug = 'generate a list of random numbers' + +description = '''\ +<p><code>genlist(L, N, Min, Max)</code>: the list <code>L</code> contains <code>N</code> random numbers from the interval [<code>Min</code>,<code>Max</code>).</p> +<pre> + ?- genlist(L, 5, 10, 100). + L = [12,99,81,24]. +</pre>''' + +hint = {} diff --git a/prolog/problems/sets/diff_3/common.py b/prolog/problems/sets/diff_3/common.py new file mode 100644 index 0000000..76b88ed --- /dev/null +++ b/prolog/problems/sets/diff_3/common.py @@ -0,0 +1,19 @@ +id = 130 +group = 'sets' +number = 37 +visible = True +facts = None + +solution = '''\ +memb130(X, [X|_]). +memb130(X, [_|T]) :- + memb130(X, T). + +diff([], _, []). +diff([H|T], S2, [H|D]) :- + \+ memb130(H, S2), + diff(T, S2, D). +diff([H|T], S2, D) :- + memb130(H, S2), + diff(T, S2, D). +''' diff --git a/prolog/problems/sets/diff_3/en.py b/prolog/problems/sets/diff_3/en.py new file mode 100644 index 0000000..a2fc55d --- /dev/null +++ b/prolog/problems/sets/diff_3/en.py @@ -0,0 +1,12 @@ +id = 130 +name = 'diff/3' +slug = 'find the difference of two sets' + +description = '''\ +<p><code>diff(S1, S2, D)</code>: the list <code>D</code> contains all elements of <code>S1</code> that don't appear in <code>S2</code>, with no duplicates.</p> +<pre> + ?- diff([2,3,5,1,7,9], [3,7,4,5,6], D). + D = [2,1,9]. +</pre>''' + +hint = {} diff --git a/prolog/problems/sets/intersect_3/common.py b/prolog/problems/sets/intersect_3/common.py new file mode 100644 index 0000000..ffa4f89 --- /dev/null +++ b/prolog/problems/sets/intersect_3/common.py @@ -0,0 +1,18 @@ +id = 129 +group = 'sets' +number = 36 +visible = True +facts = None + +solution = '''\ +memb129(X, [X|_]). +memb129(X, [_|T]) :- + memb129(X, T). + +intersect([], _, []). +intersect([H|T], S2, [H|I]) :- + memb129(H, S2), !, + intersect(T, S2, I). +intersect([_|T], S2, I):- + intersect(T, S2, I). +''' diff --git a/prolog/problems/sets/intersect_3/en.py b/prolog/problems/sets/intersect_3/en.py new file mode 100644 index 0000000..b4296e4 --- /dev/null +++ b/prolog/problems/sets/intersect_3/en.py @@ -0,0 +1,12 @@ +id = 129 +name = 'intersect/3' +slug = 'find the intersection of two sets' + +description = '''\ +<p><code>intersect(S1, S2, I)</code>: the list <code>I</code> contains every element that appears in both <code>S1</code> and <code>S2</code>, with no duplicates.</p> +<pre> + ?- intersect([1,5,6,3,4,2], [8,1,5,9,4,3], I). + I = [1,5,3,4]. +</pre>''' + +hint = {} diff --git a/prolog/problems/sets/is_subset_2/common.py b/prolog/problems/sets/is_subset_2/common.py new file mode 100644 index 0000000..5b365ee --- /dev/null +++ b/prolog/problems/sets/is_subset_2/common.py @@ -0,0 +1,16 @@ +id = 132 +group = 'sets' +number = 39 +visible = True +facts = None + +solution = '''\ +memb132(X, [X|_]). +memb132(X, [_|T]) :- + memb132(X, T). + +is_subset([], _). +is_subset([H|T], S2) :- + memb132(H, S2), + is_subset(T, S2). +''' diff --git a/prolog/problems/sets/is_subset_2/en.py b/prolog/problems/sets/is_subset_2/en.py new file mode 100644 index 0000000..ae2c113 --- /dev/null +++ b/prolog/problems/sets/is_subset_2/en.py @@ -0,0 +1,14 @@ +id = 132 +name = 'is_subset/2' +slug = 'check if one set is a subset of another' + +description = '''\ +<p><code>is_subset(S1, S2)</code>: the set <code>S1</code> is a subset of <code>S2</code>.</p> +<pre> + ?- is_subset([2,1,3,5,0], [3,2,1,4,5,9]). + false. + ?- is_subset([2,1,3,5], [3,2,1,4,5,9]). + true. +</pre>''' + +hint = {} diff --git a/prolog/problems/sets/is_superset_2/common.py b/prolog/problems/sets/is_superset_2/common.py new file mode 100644 index 0000000..364c513 --- /dev/null +++ b/prolog/problems/sets/is_superset_2/common.py @@ -0,0 +1,16 @@ +id = 131 +group = 'sets' +number = 38 +visible = True +facts = None + +solution = '''\ +memb131(X, [X|_]). +memb131(X, [_|T]) :- + memb131(X, T). + +is_superset(_, []). +is_superset(S1, [H|T]) :- + memb131(H, S1), + is_superset(S1, T). +''' diff --git a/prolog/problems/sets/is_superset_2/en.py b/prolog/problems/sets/is_superset_2/en.py new file mode 100644 index 0000000..218c0c8 --- /dev/null +++ b/prolog/problems/sets/is_superset_2/en.py @@ -0,0 +1,14 @@ +id = 131 +name = 'is_superset/2' +slug = 'check if one set is a superset of the other' + +description = '''\ +<p><code>is_superset(S1, S2)</code>: the set <code>S1</code> is a superset (contains all elements) of <code>S2</code>.</p> +<pre> + ?- is_superset([3,2,1,4,5,9], [2,1,3,5]). + true. + ?- is_superset([3,2,1,4,5,9], [2,1,3,5,0]). + false. +</pre>''' + +hint = {} diff --git a/prolog/problems/sets/powerset_2/common.py b/prolog/problems/sets/powerset_2/common.py new file mode 100644 index 0000000..8f3b70e --- /dev/null +++ b/prolog/problems/sets/powerset_2/common.py @@ -0,0 +1,16 @@ +id = 134 +group = 'sets' +number = 41 +visible = True +facts = None + +solution = '''\ +subset134([], []). +subset134([H|T], [H|T1]) :- + subset134(T, T1). +subset134([_|T], T1) :- + subset134(T, T1). + +powerset(Set, PowerSet) :- + findall(S, subset134(Set, S), PowerSet). +''' diff --git a/prolog/problems/sets/powerset_2/en.py b/prolog/problems/sets/powerset_2/en.py new file mode 100644 index 0000000..6471469 --- /dev/null +++ b/prolog/problems/sets/powerset_2/en.py @@ -0,0 +1,12 @@ +id = 134 +name = 'powerset/2' +slug = 'find all subsets of a set' + +description = '''\ +<p><code>powerset(Set, Powerset)</code>: the list <code>Powerset</code> contains all subsets of <code>Set</code>.</p> +<pre> + ?- powerset([1,2,3], L). + L = [[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]. +</pre>''' + +hint = {} diff --git a/prolog/problems/sets/subset_2/common.py b/prolog/problems/sets/subset_2/common.py new file mode 100644 index 0000000..7fbbf49 --- /dev/null +++ b/prolog/problems/sets/subset_2/common.py @@ -0,0 +1,13 @@ +id = 133 +group = 'sets' +number = 40 +visible = True +facts = None + +solution = '''\ +subset([], []). +subset([H|T], [H|T1]) :- + subset(T, T1). +subset([_|T], T1) :- + subset(T, T1). +''' diff --git a/prolog/problems/sets/subset_2/en.py b/prolog/problems/sets/subset_2/en.py new file mode 100644 index 0000000..9d9132b --- /dev/null +++ b/prolog/problems/sets/subset_2/en.py @@ -0,0 +1,19 @@ +id = 133 +name = 'subset/2' +slug = 'generate all subsets of a set' + +description = '''\ +<p><code>subset(Set, Subset)</code>: the set <code>Subset</code> is a subset of <code>Set</code>. This predicate should generate all valid solutions, one by one.</p> +<pre> + ?- subset([1,2,3], SS). + SS = [1,2,3] ; + SS = [1,2] ; + SS = [1,3] ; + SS = [1] ; + SS = [2,3] ; + SS = [2] ; + SS = [3] ; + SS = []. +</pre>''' + +hint = {} diff --git a/prolog/problems/sets/union_3/common.py b/prolog/problems/sets/union_3/common.py new file mode 100644 index 0000000..a219673 --- /dev/null +++ b/prolog/problems/sets/union_3/common.py @@ -0,0 +1,19 @@ +id = 128 +group = 'sets' +number = 35 +visible = True +facts = None + +solution = '''\ +memb128(X, [X|_]). +memb128(X, [_|T]) :- + memb128(X, T). + +union([], S2, S2). +union([H|T], S2, [H|U]) :- + \+ memb128(H, S2), + union(T, S2, U). +union([H|T], S2, U) :- + memb128(H, S2), + union(T, S2, U). +''' diff --git a/prolog/problems/sets/union_3/en.py b/prolog/problems/sets/union_3/en.py new file mode 100644 index 0000000..8257415 --- /dev/null +++ b/prolog/problems/sets/union_3/en.py @@ -0,0 +1,12 @@ +id = 128 +name = 'union/3' +slug = 'find the union of two sets' + +description = '''\ +<p><code>union(S1, S2, U)</code>: the list <code>U</code> contains all elements of <code>S1</code> and <code>S2</code>, with no duplicates.</p> +<pre> + ?- union([1,5,2,3], [3,4,8,2], U). + U = [1,5,3,4,8,2]. +</pre>''' + +hint = {} diff --git a/prolog/problems/sorting/is_sorted_1/common.py b/prolog/problems/sorting/is_sorted_1/common.py new file mode 100644 index 0000000..2feb134 --- /dev/null +++ b/prolog/problems/sorting/is_sorted_1/common.py @@ -0,0 +1,13 @@ +id = 121 +group = 'sorting' +number = 28 +visible = True +facts = None + +solution = '''\ +is_sorted([]). +is_sorted([_]). +is_sorted([H1,H2|T]) :- + H1 =< H2, + is_sorted([H2|T]). +''' diff --git a/prolog/problems/sorting/is_sorted_1/en.py b/prolog/problems/sorting/is_sorted_1/en.py new file mode 100644 index 0000000..c4bd025 --- /dev/null +++ b/prolog/problems/sorting/is_sorted_1/en.py @@ -0,0 +1,14 @@ +id = 121 +name = 'is_sorted/1' +slug = 'check if list is sorted' + +description = '''\ +<p><code>is_sorted(L)</code>: the elements of list <code>L</code> are sorted in non-decreasing order.</p> +<pre> + ?- is_sorted([2,3,6,8,12]). + true. + ?- is_sorted([2,3,1,6,5]). + false. +</pre>''' + +hint = {} diff --git a/prolog/problems/sorting/isort_2/common.py b/prolog/problems/sorting/isort_2/common.py new file mode 100644 index 0000000..0b1aa47 --- /dev/null +++ b/prolog/problems/sorting/isort_2/common.py @@ -0,0 +1,18 @@ +id = 123 +group = 'sorting' +number = 30 +visible = True +facts = None + +solution = '''\ +sins123(X, [], [X]). +sins123(X, [Y|T], [X,Y|T]) :- + X =< Y. +sins123(X, [Y|T], [Y|L]) :- + X > Y, + sins123(X, T, L). +isort([], []). +isort([H|T], SL) :- + isort(T, ST), + sins123(H, ST, SL). +''' diff --git a/prolog/problems/sorting/isort_2/en.py b/prolog/problems/sorting/isort_2/en.py new file mode 100644 index 0000000..3a3dea0 --- /dev/null +++ b/prolog/problems/sorting/isort_2/en.py @@ -0,0 +1,12 @@ +id = 123 +name = 'isort/2' +slug = 'sort a list using insertion sort' + +description = '''\ +<p><code>isort(L, SL)</code>: the list <code>SL</code> contains the elements of <code>L</code> sorted in non-decreasing order. Use the predicate <code>sins/3</code> to implement insertion sort.</p> +<pre> + ?- isort([2,3,1,5,4], L). + L = [1,2,3,4,5]. +</pre>''' + +hint = {} diff --git a/prolog/problems/sorting/pivoting_4/common.py b/prolog/problems/sorting/pivoting_4/common.py new file mode 100644 index 0000000..278f694 --- /dev/null +++ b/prolog/problems/sorting/pivoting_4/common.py @@ -0,0 +1,15 @@ +id = 124 +group = 'sorting' +number = 31 +visible = True +facts = None + +solution = '''\ +pivoting(_, [], [], []). +pivoting(P, [H|T], [H|S], G) :- + H =< P, + pivoting(P, T, S, G). +pivoting(P, [H|T], S, [H|G]) :- + H > P, + pivoting(P, T, S, G). +''' diff --git a/prolog/problems/sorting/pivoting_4/en.py b/prolog/problems/sorting/pivoting_4/en.py new file mode 100644 index 0000000..4a1ab8c --- /dev/null +++ b/prolog/problems/sorting/pivoting_4/en.py @@ -0,0 +1,12 @@ +id = 124 +name = 'pivoting/4' +slug = 'split a list according to the pivot' + +description = '''\ +<p><code>pivoting(P, L, S, G)</code>: the list <code>S</code> contains the elements of <code>L</code> <em>smaller or equal to</em> <code>P</code>, and the list <code>G</code> contains the elements of <code>L</code> <em>greater than</em> <code>P</code>. The order of elements in <code>S</code> and <code>G</code> should be the same as in <code>L</code>.</p> +<pre> + ?- pivoting(4, [1,4,5,8,6,4,2], S, G). + S = [1,4,4,2], G = [5,8,6]. +</pre>''' + +hint = {} diff --git a/prolog/problems/sorting/quick_sort_2/common.py b/prolog/problems/sorting/quick_sort_2/common.py new file mode 100644 index 0000000..5eff940 --- /dev/null +++ b/prolog/problems/sorting/quick_sort_2/common.py @@ -0,0 +1,24 @@ +id = 125 +group = 'sorting' +number = 32 +visible = True +facts = None + +solution = '''\ +conc125([], L, L). +conc125([H|T], L2, [H|L]) :- + conc125(T, L2, L). +pivoting125(_, [], [], []). +pivoting125(P, [H|T], [H|S], G) :- + H =< P, + pivoting125(P, T, S, G). +pivoting125(P, [H|T], S, [H|G]) :- + H > P, + pivoting125(P, T, S, G). +quick_sort([], []). +quick_sort([Pivot|T], Sorted) :- + pivoting125(Pivot, T, Smaller, Greater), + quick_sort(Smaller, SortedSmaller), + quick_sort(Greater, SortedGreater), + conc125(SortedSmaller, [Pivot|SortedGreater], Sorted). +''' diff --git a/prolog/problems/sorting/quick_sort_2/en.py b/prolog/problems/sorting/quick_sort_2/en.py new file mode 100644 index 0000000..b0d4ce1 --- /dev/null +++ b/prolog/problems/sorting/quick_sort_2/en.py @@ -0,0 +1,12 @@ +id = 125 +name = 'quick_sort/2' +slug = 'sort a list using quicksort' + +description = '''\ +<p><code>quick_sort(L, SL)</code>: the list <code>SL</code> contains the elements of <code>L</code> sorted in non-decreasing order. Use the predicate <code>pivoting/4</code> to implement quicksort.</p> +<pre> + ?- quick_sort([2,3,1,5,4], L). + L = [1,2,3,4,5]. +</pre>''' + +hint = {} diff --git a/prolog/problems/sorting/sins_3/common.py b/prolog/problems/sorting/sins_3/common.py new file mode 100644 index 0000000..8ebfee4 --- /dev/null +++ b/prolog/problems/sorting/sins_3/common.py @@ -0,0 +1,14 @@ +id = 122 +group = 'sorting' +number = 29 +visible = True +facts = None + +solution = '''\ +sins(X, [], [X]). +sins(X, [Y|T], [X,Y|T]) :- + X =< Y. +sins(X, [Y|T], [Y|L]) :- + X > Y, + sins(X, T, L). +''' diff --git a/prolog/problems/sorting/sins_3/en.py b/prolog/problems/sorting/sins_3/en.py new file mode 100644 index 0000000..684a619 --- /dev/null +++ b/prolog/problems/sorting/sins_3/en.py @@ -0,0 +1,14 @@ +id = 122 +name = 'sins/3' +slug = 'insert an element at correct position into a sorted list' + +description = '''\ +<p><code>sins(X, SortedList, NewList)</code>: the list <code>NewList</code> is obtained by inserting <code>X</code> into <code>SortedList</code> at the correct position to preserve the non-decreasing order of elements.</p> +<pre> + ?- sins(4, [1,2,3,5], L). + L = [1,2,3,4,5]. + ?- sins(3, [1,2,3,4], L). + L = [1,2,3,3,4]. +</pre>''' + +hint = {} diff --git a/prolog/problems/sorting/slowest_sort_ever_2/common.py b/prolog/problems/sorting/slowest_sort_ever_2/common.py new file mode 100644 index 0000000..5f4c283 --- /dev/null +++ b/prolog/problems/sorting/slowest_sort_ever_2/common.py @@ -0,0 +1,25 @@ +id = 126 +group = 'sorting' +number = 33 +visible = True +facts = None + +solution = '''\ +del126(X, [X|T], T). +del126(X, [Y|T], [Y|L]) :- + del126(X, T, L). + +permute126([], []). +permute126(L, [X|P]) :- + del126(X, L, L1), + permute126(L1, P). + +is_sorted126([_]). +is_sorted126([H1,H2|T]) :- + H1 =< H2, + is_sorted126([H2|T]). + +slowest_sort_ever(L, S) :- + permute126(L, S), + is_sorted126(S). +''' diff --git a/prolog/problems/sorting/slowest_sort_ever_2/en.py b/prolog/problems/sorting/slowest_sort_ever_2/en.py new file mode 100644 index 0000000..3018ec6 --- /dev/null +++ b/prolog/problems/sorting/slowest_sort_ever_2/en.py @@ -0,0 +1,12 @@ +id = 126 +name = 'slowest_sort_ever/2' +slug = 'sort a list by randomly permuting elements' + +description = '''\ +<p><code>slowest_sort_ever(L, SL)</code>: the list <code>SL</code> contains the elements of <code>L</code> sorted in non-decreasing order. Average and worst case running time is O(n * n!).</p> +<pre> + ?- slowest_sort_ever([2,3,1,5,4], L). + L = [1,2,3,4,5]. +</pre>''' + +hint = {} 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 = {} |