summaryrefslogtreecommitdiff
path: root/prolog/problems/sorting
diff options
context:
space:
mode:
Diffstat (limited to 'prolog/problems/sorting')
-rw-r--r--prolog/problems/sorting/is_sorted_1/en.py81
-rw-r--r--prolog/problems/sorting/is_sorted_1/sl.py2
-rw-r--r--prolog/problems/sorting/isort_2/en.py55
-rw-r--r--prolog/problems/sorting/quick_sort_2/en.py59
-rw-r--r--prolog/problems/sorting/slowest_sort_ever_2/en.py44
5 files changed, 236 insertions, 5 deletions
diff --git a/prolog/problems/sorting/is_sorted_1/en.py b/prolog/problems/sorting/is_sorted_1/en.py
index 8741bc7..678494c 100644
--- a/prolog/problems/sorting/is_sorted_1/en.py
+++ b/prolog/problems/sorting/is_sorted_1/en.py
@@ -10,4 +10,83 @@ description = '''\
false.
</pre>'''
-hint = {}
+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>
+''',
+}
diff --git a/prolog/problems/sorting/is_sorted_1/sl.py b/prolog/problems/sorting/is_sorted_1/sl.py
index de52984..36ace61 100644
--- a/prolog/problems/sorting/is_sorted_1/sl.py
+++ b/prolog/problems/sorting/is_sorted_1/sl.py
@@ -77,7 +77,7 @@ glavni robni pogoj!</p>
'both_heads_omitted_from_recursion': '''\
<p>Jemlješ po dva elementa iz seznama preden greš v rekurzijo? Poskušaš malce prihraniti pri primerjavah, kajne? ;)
-Ampak žal to ne gre! Od spodnjih dveh primerov eden deluje pravilno in eden ne, ugotovi v čem je razlika. </p>
+Ampak žal to ne gre! Od spodnjih dveh primerov eden deluje pravilno in eden ne, ugotovi v čem je razlika.</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>
''',
diff --git a/prolog/problems/sorting/isort_2/en.py b/prolog/problems/sorting/isort_2/en.py
index 71b1a12..35beb62 100644
--- a/prolog/problems/sorting/isort_2/en.py
+++ b/prolog/problems/sorting/isort_2/en.py
@@ -8,4 +8,57 @@ description = '''\
L = [1,2,3,4,5].
</pre>'''
-hint = {}
+plan = ['''\
+<p>When going through the list (actually when returning from recursion) at every step insert the current element
+in its proper position.</p>
+''', '''\
+<p>When going through the list at every step take away the head (it's stored on stack), while its tail goes
+into recursion (the problem/list is shorter, so this is possible). The recursion returns the <em>sorted</em>
+tail, and all that's left for you to do is to put the previously taken away head into its proper place in the
+sorted tail. Of course you can reuse some previous exercise for this task.</p>
+''', '''\
+<p>If list <code>L</code> is composed of head <code>H</code> and tail <code>T</code> and if we assume that
+tail <code>T</code> is correctly sorted into <code>SortedTail</code> by recursion, and if head <code>H</code>
+is inserted into its proper place within <code>SortedTail</code>, then we get the whole list <code>L</code>
+properly 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 list can you sort 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>
+''',
+
+ 'min_used': '''\
+<p>Try solving this exercise without using the predicate <code>min/2</code>.</p>
+''',
+}
diff --git a/prolog/problems/sorting/quick_sort_2/en.py b/prolog/problems/sorting/quick_sort_2/en.py
index aa3eb44..a5b571b 100644
--- a/prolog/problems/sorting/quick_sort_2/en.py
+++ b/prolog/problems/sorting/quick_sort_2/en.py
@@ -8,4 +8,61 @@ description = '''\
L = [1,2,3,4,5].
</pre>'''
-hint = {}
+plan = ['''\
+<p>Divide and conquer! And use previous solutions, of course. :)</p>
+''', '''\
+<p>Take the head away, use it as a pivot, divide the tail into smaller and larger elements. Use recursion on
+so obtained sublists since both are shorter (in the worst case scenario shorter by just the head element --
+this also explains why quicksort works worst on already sorted lists). In the end simply combine the sublists.</p>
+''', '''\
+<p>If list <code>L</code> is composed of head <code>P</code> and tail <code>T</code> and if the tail is
+split into sublists containing smaller and larger elements, respectively, based on pivot <code>P</code>, and if
+we assume the recursion sorts these two sublists into lists <code>SortedSmallerElems</code> and
+<code>SortedGreaterElems</code>, and if finally we concatenate these two lists and add in between pivot/head
+<code>P</code>, then this results in correctly sorted initial list <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).</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 list can you sort 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>
+''',
+
+ 'arbitrary_base_case': '''\
+<p>How can the sorted list be anything whatsoever or a list with an arbitrary element? Did you use
+a variable without an assigned value?</p>
+''',
+
+ 'forgotten_pivot': '''\
+<p>Did you, perhaps, forgot to put the pivot element back into the list when returning from recursion?</p>
+''',
+}
diff --git a/prolog/problems/sorting/slowest_sort_ever_2/en.py b/prolog/problems/sorting/slowest_sort_ever_2/en.py
index 0e359b4..72a70bb 100644
--- a/prolog/problems/sorting/slowest_sort_ever_2/en.py
+++ b/prolog/problems/sorting/slowest_sort_ever_2/en.py
@@ -8,4 +8,46 @@ description = '''\
L = [1,2,3,4,5].
</pre>'''
-hint = {}
+plan = ['''\
+<p>This exercise is mostly for fun... all you need are two lines, i.e. two prolog goals.</p>
+''', '''\
+<p>Perhaps you can reuse some previous solutions?</p>
+''', '''\
+<p>Which of the previous solutions has time complexity of O(n!)? Use it!</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>
+''',
+
+ '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>
+''',
+
+ 'no_permute': '''\
+<p>Hmmm, which of the previous exercises has time complexity of O(n!)? How can you use it here?</p>
+''',
+
+ 'no_isSorted': '''\
+<p>You're on the right path, just a bit more to go. Perhaps you can reuse another previous exercise?</p>
+''',
+}