name = 'sins/3'
slug = 'insert an element at correct position into a sorted list'

description = '''\
<p><code>sins(X, SortedList, NewList)</code>: the list <code>NewList</code> is obtained by inserting <code>X</code> into <code>SortedList</code> at the correct position to preserve the non-decreasing order of elements.</p>
<pre>
?- sins(4, [1,2,3,5], L).
  L = [1,2,3,4,5].
?- sins(3, [1,2,3,4], L).
  L = [1,2,3,3,4].
</pre>'''

plan = ['''\
<p>For starters, let's remember that we're inserting into a <em>sorted</em> list. Let's go through the list,
element by element, until we find a proper place for the new element.</p>
''', '''\
<p>Step by step you compare the new element with the list's current head. The heads will be increasing in
value as the list is sorted. Which means that at some point the new element will become smaller than the
current head, right?</p>
''', '''\
<p>If the new element <code>X</code> is larger than the current head <code>H</code>, then we insert it
somewhere in the tail -- this will be taken care of by the recursion, as always, right? And if it's not larger,
then we found the proper place for the new element and we insert it now <em>in front of</em> the current
head <code>H</code>! You know how to put two elements before the tail at the same time, right? (It's the
same as taking two elements out.)</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? This will probably be the case when you (finally) insert a new element
into the list.</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>
''',

    'bad_[]_case': '''\
<p>What's the result of inserting an element into an empty list? Surely not an empty list or even an
arbitrary result (a variable without an assigned value)?</p>
''',

    'returns_elem_instead_of_list': '''\
<p>You have to return a <em>list</em>, not an element.</p>
''',

    'maxEl_base_case_missing': '''\
<p>The solution is almost correct. But you probably forgot one specific case. What happens if you're trying
to insert a new largest element into the list? Try the following query.</p>
<p><code>?- sins(9, [1,2,3,4,5], L).</code></p>
''',

    'x_and_head_swapped': '''\
<p>Hmmm, what should be the ordering of the new element and the current head of the list?</p>
<p><code>?- sins(3, [1,2,4,5,6], L).</code></p>
''',

    'duplicates_incorrect': '''\
<p>Did you forget that duplicates are also allowed? The first query below works fine, the other one doesn't.</p>
<p><code>?- sins(3, [1,2,4,5,6], L).</code></p>
<p><code>?- sins(3, [1,2,3,4,5], L).</code></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>?- sins(3, [1,2,4,5,6], L).</code></p>
''',

    'forgotten_heads': '''\
<p>Did you forget to return the heads, removed before the recursion, into the list? I did that, too... ;)</p>
<p>Look what happens with the query below and you'll immediately understand the error.</p>
<p><code>?- sins(4, [1,2,3,5,6], L).</code></p>
''',
}