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 /prolog/problems/dcg |
Exported all problems from the SQLite database into the new directory structure.
Diffstat (limited to 'prolog/problems/dcg')
-rw-r--r-- | prolog/problems/dcg/ab_2/common.py | 11 | ||||
-rw-r--r-- | prolog/problems/dcg/ab_2/en.py | 10 | ||||
-rw-r--r-- | prolog/problems/dcg/digit_2/common.py | 9 | ||||
-rw-r--r-- | prolog/problems/dcg/digit_2/en.py | 8 | ||||
-rw-r--r-- | prolog/problems/dcg/expr_2/common.py | 23 | ||||
-rw-r--r-- | prolog/problems/dcg/expr_2/en.py | 10 | ||||
-rw-r--r-- | prolog/problems/dcg/expr_3/common.py | 24 | ||||
-rw-r--r-- | prolog/problems/dcg/expr_3/en.py | 14 | ||||
-rw-r--r-- | prolog/problems/dcg/flower_2/common.py | 13 | ||||
-rw-r--r-- | prolog/problems/dcg/flower_2/en.py | 10 | ||||
-rw-r--r-- | prolog/problems/dcg/number_2/common.py | 12 | ||||
-rw-r--r-- | prolog/problems/dcg/number_2/en.py | 9 | ||||
-rw-r--r-- | prolog/problems/dcg/number_3/common.py | 30 | ||||
-rw-r--r-- | prolog/problems/dcg/number_3/en.py | 13 | ||||
-rw-r--r-- | prolog/problems/dcg/number_proper_2/common.py | 16 | ||||
-rw-r--r-- | prolog/problems/dcg/number_proper_2/en.py | 9 | ||||
-rw-r--r-- | prolog/problems/dcg/paren_2/common.py | 10 | ||||
-rw-r--r-- | prolog/problems/dcg/paren_2/en.py | 10 | ||||
-rw-r--r-- | prolog/problems/dcg/paren_3/common.py | 10 | ||||
-rw-r--r-- | prolog/problems/dcg/paren_3/en.py | 13 |
20 files changed, 264 insertions, 0 deletions
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 = {} |