diff options
Diffstat (limited to 'prolog/problems')
-rw-r--r-- | prolog/problems/sorting/pivoting_4/en.py | 100 |
1 files changed, 99 insertions, 1 deletions
diff --git a/prolog/problems/sorting/pivoting_4/en.py b/prolog/problems/sorting/pivoting_4/en.py index 620c8f2..77e7f71 100644 --- a/prolog/problems/sorting/pivoting_4/en.py +++ b/prolog/problems/sorting/pivoting_4/en.py @@ -8,4 +8,102 @@ description = '''\ S = [1,4,4,2], G = [5,8,6]. </pre>''' -hint = {} +plan = ['''\ +<p>A pretty standard recursive exercise: you take care of the current head, and the tail is handled by the +recursion. There are two branches, of course, as the head can be either smaller or greater than the pivot.</p> +''', '''\ +<p>Go through the list and put the current head into either the smaller elements list or the greater elements list +when <em>returning</em> from recursion.</p> +''', '''\ +<p>If head <code>H</code> of list <code>L</code> is smaller than or equal to pivot <code>P</code> and if we +assume that the recursion returns the elements in tail <code>T</code> appropriately divided into lists +<code>SmallerElems</code> and <code>GreaterElems</code> and if we insert <code>H</code> at the start of the list +<code>SmallerElems</code>, then we correctly split all the elements in <code>L</code> into smaller and greater ones. +It's analogous if head <code>H</code> is greater than pivot <code>P</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).</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 (<code>=</code>) would be better?</p> +''', + + 'base_case': '''\ +<p>Did you think of a base case? Which list can you split without any effort whatsoever?</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> +''', + + '>_and_<_mixed_up': '''\ +<p>Did you mix up the comparison? The smaller elements list contains large elements and vice versa. +I did that, too! ;)</p> +<p><code>?- pivoting(4, [1,4,5,8,6,4,2], SmallerElems, GreaterElems).</code></p> +''', + + 'duplicates_not_considered': '''\ +<p>Did you forget that some element can also be equal to the pivot? Where do you put such an element? +Currently you don't put it anywhere, that's why prolog's answer is a happy (and logical, of course)... +yes, you've guessed it... "false"!</p> +''', + + 'all_elements_in_either_S_or_G': '''\ +<p>How come <em>all</em> the elements end up in either smaller or greater element list? +A wrong comparison operator or a copy/paste error?</p> +''', + + 'arbitrary_solution': '''\ +<p>Oh, this is a nasty little mistake. You took care of one of the lists you're returning, but not of the other one. +If, for example, you put head <code>H</code> into a smaller elements list <code>[H|SmallerElems]</code> that's ok, but +don't forget to specify what happens to the greater elements list (even if it stays exactly the same as returned +from recursion).</p> +''', + + 'unprotected_branch': '''\ +<p>Did you "protect" (with a condition) both options (branches)? Be careful, if one branch doesn't have a +condition, the first solution returned will probably be correct, but it will leave the door open for other +solutions which will not be correct. The semicolon stands for logical OR, not logical XOR. This means that +prolog can still search for solutions in the other branch even if the first branch's condition is satisfied! +That's why you need both conditions.</p> +<p>Try the following query and ask for <em>more</em> solutions.</p> +<p><code>?- pivoting(4, [1,4,5,8,6,4,2], SmallerElems, GreaterElems).</code></p> +''', + + 'forcing_result_onto_recursion': ''' +<p>Don't force the result onto recursion, don't tell it what it should return. Just assume it will do its job. +If this assumption is correct, then the rule will work for a larger case.</p> +<p>Is your recursive call of the form <code>pivoting(P, T, [H|SmallerElems], GreaterElems)</code>? This forces +the recursive call to <em>return</em> also head <code>H</code> which it doesn't even know of, because you +took it away before the recursive call. Inserting the head into the result, returned by the recursive call, +is your job. To put it shortly, insert <code>H</code> outside of the recursive call.</p> +''', + + 'no_recursion_in_one_branch': '''\ +<p>This is a very typical mistake when using a semicolon. Read every OR block (branch) carefully. Don't you think +that you forgot something in one of the branches, usually the second one? Perhaps a recursive call? Do not forget: +both/all branches are independent of one another! Either one block will be executed, or the other, but never both! +And the results will not be transferred between blocks/branches; remember the scope of variables in prolog.</p> +''', +} |