summaryrefslogtreecommitdiff
path: root/prolog/problems/dcg
diff options
context:
space:
mode:
Diffstat (limited to 'prolog/problems/dcg')
-rw-r--r--prolog/problems/dcg/ab_2/common.py11
-rw-r--r--prolog/problems/dcg/ab_2/en.py10
-rw-r--r--prolog/problems/dcg/digit_2/common.py9
-rw-r--r--prolog/problems/dcg/digit_2/en.py8
-rw-r--r--prolog/problems/dcg/expr_2/common.py23
-rw-r--r--prolog/problems/dcg/expr_2/en.py10
-rw-r--r--prolog/problems/dcg/expr_3/common.py24
-rw-r--r--prolog/problems/dcg/expr_3/en.py14
-rw-r--r--prolog/problems/dcg/flower_2/common.py13
-rw-r--r--prolog/problems/dcg/flower_2/en.py10
-rw-r--r--prolog/problems/dcg/number_2/common.py12
-rw-r--r--prolog/problems/dcg/number_2/en.py9
-rw-r--r--prolog/problems/dcg/number_3/common.py30
-rw-r--r--prolog/problems/dcg/number_3/en.py13
-rw-r--r--prolog/problems/dcg/number_proper_2/common.py16
-rw-r--r--prolog/problems/dcg/number_proper_2/en.py9
-rw-r--r--prolog/problems/dcg/paren_2/common.py10
-rw-r--r--prolog/problems/dcg/paren_2/en.py10
-rw-r--r--prolog/problems/dcg/paren_3/common.py10
-rw-r--r--prolog/problems/dcg/paren_3/en.py13
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 = {}