name = 'pivoting/4'
slug = 'split a list according to the pivot'

description = '''\
<p><code>pivoting(P, L, S, G)</code>: the list <code>S</code> contains the elements of <code>L</code> <em>smaller or equal to</em> <code>P</code>, and the list <code>G</code> contains the elements of <code>L</code> <em>greater than</em> <code>P</code>. The order of elements in <code>S</code> and <code>G</code> should be the same as in <code>L</code>.</p>
<pre>
?- pivoting(4, [1,4,5,8,6,4,2], S, G).
  S = [1,4,4,2], G = [5,8,6].
</pre>'''

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>
''',
}