summaryrefslogtreecommitdiff
path: root/prolog/problems/lists_advanced/min_2/en.py
blob: 4835d9d781512b3ba351be5bbf33af32281990db (plain)
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
93
94
95
96
name = 'min/2'
slug = 'find the smallest element of a list'

description = '''\
<p><code>min(L, Min)</code>: <code>Min</code> is the smallest value in list <code>L</code>.</p>
<pre>
?- min([5,4,1,6], M).
  M = 1.
?- min([3,2,2], M).
  M = 2.
</pre>'''

plan = ['''\
<p>As usual, try to reduce the problem to a smaller one. Say you already have <em>the smallest</em> element
of the <em>tail</em>...</p>
''', '''\
<p>Compare the smallest element in the tail (list without head <code>H</code>) with the value of head <code>H</code>,
the smaller of the two wins and gets returned.</p>
''', '''\
<p>If the given list <code>L</code> is composed of head <code>H</code> and tail <code>T</code>, and if we
assume that some <code>MinT</code> is the smallest element in <code>T</code>, and if it's also true that
the value of <code>H</code> is smaller than <code>MinT</code>, then <code>H</code> is the smallest element
in <code>L</code>. <em>Or</em> it is true that <code>H</code> is greater than <code>MinT</code>, and in this
case <code>MinT</code> is the smallest element in <code>L</code>.</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). Perhaps by using <code>=</code>
you can make the predicate <code>min/2</code> more general (e.g. able to work with output arguments becoming inputs).</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? What's the shortest list with an obvious smallest element?</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>N</code> is equal to <code>N + 1</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>
''',

    'empty_list_base_case': '''\
<p>You'll be hard pressed to find the smallest element of an empty list. What if you stop
the recursion a bit earlier this time?</p>
''',

    'list_instead_of_elem_base_case': '''\
<p>You should return an element, not a list!</p>
''',

    'duplicates_not_covered': '''\
<p>The list can contain duplicate elements. Did you think of that?</p>
''',

    'args_not_instantiated': '''\
<p>The error that prolog reported means that when it encountered an arithmetic operation, not all the
values were known.</p>
<p>Did you perhaps forget that conjunction has higher precedence that disjunction and that every prolog's
sentence (branch, rule) is independent in terms of the scope of the variables? This could be the problem.
Carefully inspect both blocks of code (before and after the semicolon) or both rules.</p>
''',

    'unprotected_branch': '''\
<p>It seems you didn't "protect" one of the (conditional) branches. Both branches (of the disjunction) typically
require a condition. Don't rely that if the execution reached the second branch that the first branch is false.
The relation between them is OR and not XOR. It's your job to make them mutually exclusive. Try the following
query and check <em>all possible</em> solutions and you'll notice the problem.</p>
<p><code>?- min([1,9,3,8,6], Min).</code></p>
''',

    'one_branch_missing': '''\
<p>Maybe you forgot one of the possibilities? The head can be <em>either</em> greater <em>or</em> smaller than
the smallest element in the tail.</p>
''',
}