1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
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>'''
plan = ['''\
<p>As always try to reduce the problem onto a smaller one. Do an appropriate check (comparison) at
the start of the list, and submit the tail to a recursive check.</p>
''', '''\
<p>You do know how to access the first <em>two</em> elements of the list, right? And the arithmetic comparison
operators were introduced in the previous batch of exercises.</p>
''', '''\
<p>If the given list <code>L</code> is composed of heads <code>H1</code> and <code>H2</code> and of tail
<code>T</code>, and if we assume that tail <code>T</code> along with the second head is sorted, and furthermore
<code>H1</code> is smaller or equal to <code>H2</code>, then the whole list <code>L</code> is sorted.</p>
''']
hint = {
'eq_instead_of_equ': '''\
<p>The operator <code>==</code> is "stricter" than operator <code>=</code> in the sense that
for the latter it is enough to be able to make the two operands equal (unification).</p>
<p>Of course, you can also solve the exercise without explicit use of either of these two operators, just
remember that unification is implicitly performed with the predicate's arguments (head of clause).</p>
''',
'eq_instead_of_equ_markup': '''\
<p>Perhaps the operator for unification (=) would be better?</p>
''',
'base_case': '''\
<p>Did you think of a base case? Which is one of the shortest sorted lists?</p>
''',
'recursive_case': '''\
<p>The base case is ok. However, what about the general recursive case?</p>
''',
'predicate_always_false': '''\
<p>It seems your predicate is <em>always</em> "false". Did you give it the correct name,
or is it perhaps misspelled?</p>
<p>If the name is correct, check whether something else is misspelled, perhaps there is a full stop instead of
a comma or vice versa, or maybe you typed a variable name in lowercase?</p>
<p>It is, of course, also possible that your conditions are too restrictive, or even impossible to satisfy
(as would be, for example, the condition that <code>X</code> is <em>simultaneously</em> smaller and greater than
<code>Y</code>, or something similarly impossible).</p>
''',
'timeout': '''\
<p>Is there an infinite recursion at work here? How will it ever stop?</p>
<p>Or perhaps is there a missing, faulty, or simply incompatible (with the general recursive case) base case?</p>
''',
'[]_base_case_missing': '''\
<p>For completeness, please take care of the special case, i.e. the empty list which is also sorted.
But be careful not to destroy the other solutions.</p>
''',
'duplicates_fail': '''\
<p>Did you forget about duplicate elements? The list below is also sorted!</p>
<p><code>?- is_sorted([25,25,25,25]).</code></p>
''',
'H1_instead_of_H2_sent_into_recursion': '''\
<p>Did you send the wrong of the two list heads into recursion?</p>
''',
'base_case_at_len_1_missing': '''\
<p>The recursive case in this exercise requires two elements, even though you put one back when the tail
is recursively processed. But what happens when there is just a single element left in the list? Think
about it as this will probably be the main base case.</p>
''',
'both_heads_omitted_from_recursion': '''\
<p>Are you taking two elements out of the list before initiating a recursive call? You're trying to
reduce the number of comparisons, aren't you? ;) But unfortunately this will not be possible! Of the following
two cases below one works correctly and one doesn't. What's the difference between them?</p>
<p><code>?- is_sorted([1,3,14,16,24,25]).</code></p>
<p><code>?- is_sorted([24,25,14,16,1,3]).</code></p>
''',
'min_used': '''\
<p>Try solving this exercise without using the predicate <code>min/2</code>. Your solution should have the
time complexity of O(n). By using <code>min/2</code> the complexity is typically about O(n*n).</p>
''',
}
|
