From 9e5d6dac0e32ecdce036041c878c290dc06599d9 Mon Sep 17 00:00:00 2001 From: Aleksander Sadikov Date: Wed, 21 Sep 2016 19:55:01 +0200 Subject: English translation for isort/2 added. --- prolog/problems/sorting/isort_2/en.py | 55 ++++++++++++++++++++++++++++++++++- 1 file changed, 54 insertions(+), 1 deletion(-) (limited to 'prolog/problems/sorting') 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]. ''' -hint = {} +plan = ['''\ +

When going through the list (actually when returning from recursion) at every step insert the current element +in its proper position.

+''', '''\ +

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 sorted +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.

+''', '''\ +

If list L is composed of head H and tail T and if we assume that +tail T is correctly sorted into SortedTail by recursion, and if head H +is inserted into its proper place within SortedTail, then we get the whole list L +properly sorted.

+'''] + +hint = { + 'eq_instead_of_equ': '''\ +

The operator == is "stricter" than operator = in the sense that +for the latter it is enough to be able to make the two operands equal (unification).

+

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).

+''', + + 'eq_instead_of_equ_markup': '''\ +

Perhaps the operator for unification (=) would be better?

+''', + + 'base_case': '''\ +

Did you think of a base case? Which list can you sort without any effort whatsoever?

+''', + + 'recursive_case': '''\ +

The base case is ok. However, what about the general recursive case?

+''', + + 'predicate_always_false': '''\ +

It seems your predicate is always "false". Did you give it the correct name, +or is it perhaps misspelled?

+

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?

+

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 X is simultaneously smaller and greater than +Y, or something similarly impossible).

+''', + + 'timeout': '''\ +

Is there an infinite recursion at work here? How will it ever stop?

+

Or perhaps is there a missing, faulty, or simply incompatible (with the general recursive case) base case?

+''', + + 'min_used': '''\ +

Try solving this exercise without using the predicate min/2.

+''', +} -- cgit v1.2.1 From 8cbbbe0a57068556fb8195c8c47a998a51599d8d Mon Sep 17 00:00:00 2001 From: Aleksander Sadikov Date: Wed, 21 Sep 2016 23:34:56 +0200 Subject: English translation for slowest_sort_ever/2 added. --- prolog/problems/sorting/slowest_sort_ever_2/en.py | 44 ++++++++++++++++++++++- 1 file changed, 43 insertions(+), 1 deletion(-) (limited to 'prolog/problems/sorting') 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]. ''' -hint = {} +plan = ['''\ +

This exercise is mostly for fun... all you need are two lines, i.e. two prolog goals.

+''', '''\ +

Perhaps you can reuse some previous solutions?

+''', '''\ +

Which of the previous solutions has time complexity of O(n!)? Use it!

+'''] + +hint = { + 'eq_instead_of_equ': '''\ +

The operator == is "stricter" than operator = in the sense that +for the latter it is enough to be able to make the two operands equal (unification).

+

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).

+''', + + 'eq_instead_of_equ_markup': '''\ +

Perhaps the operator for unification (=) would be better?

+''', + + 'predicate_always_false': '''\ +

It seems your predicate is always "false". Did you give it the correct name, +or is it perhaps misspelled?

+

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?

+

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 X is simultaneously smaller and greater than +Y, or something similarly impossible).

+''', + + 'timeout': '''\ +

Is there an infinite recursion at work here? How will it ever stop?

+

Or perhaps is there a missing, faulty, or simply incompatible (with the general recursive case) base case?

+''', + + 'no_permute': '''\ +

Hmmm, which of the previous exercises has time complexity of O(n!)? How can you use it here?

+''', + + 'no_isSorted': '''\ +

You're on the right path, just a bit more to go. Perhaps you can reuse another previous exercise?

+''', +} -- cgit v1.2.1 From 236500bc03d18b10f0989e052f4e829b52ad03f0 Mon Sep 17 00:00:00 2001 From: Aleksander Sadikov Date: Fri, 23 Sep 2016 18:49:19 +0200 Subject: English translation for quicksort/2 added. --- prolog/problems/sorting/quick_sort_2/en.py | 59 +++++++++++++++++++++++++++++- 1 file changed, 58 insertions(+), 1 deletion(-) (limited to 'prolog/problems/sorting') 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]. ''' -hint = {} +plan = ['''\ +

Divide and conquer! And use previous solutions, of course. :)

+''', '''\ +

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.

+''', '''\ +

If list L is composed of head P and tail T and if the tail is +split into sublists containing smaller and larger elements, respectively, based on pivot P, and if +we assume the recursion sorts these two sublists into lists SortedSmallerElems and +SortedGreaterElems, and if finally we concatenate these two lists and add in between pivot/head +P, then this results in correctly sorted initial list L.

+'''] + +hint = { + 'eq_instead_of_equ': '''\ +

The operator == is "stricter" than operator = in the sense that +for the latter it is enough to be able to make the two operands equal (unification).

+

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).

+''', + + 'eq_instead_of_equ_markup': '''\ +

Perhaps the operator for unification (=) would be better?

+''', + + 'base_case': '''\ +

Did you think of a base case? Which list can you sort without any effort whatsoever?

+''', + + 'recursive_case': '''\ +

The base case is ok. However, what about the general recursive case?

+''', + + 'predicate_always_false': '''\ +

It seems your predicate is always "false". Did you give it the correct name, +or is it perhaps misspelled?

+

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?

+

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 X is simultaneously smaller and greater than +Y, or something similarly impossible).

+''', + + 'timeout': '''\ +

Is there an infinite recursion at work here? How will it ever stop?

+

Or perhaps is there a missing, faulty, or simply incompatible (with the general recursive case) base case?

+''', + + 'arbitrary_base_case': '''\ +

How can the sorted list be anything whatsoever or a list with an arbitrary element? Did you use +a variable without an assigned value?

+''', + + 'forgotten_pivot': '''\ +

Did you, perhaps, forgot to put the pivot element back into the list when returning from recursion?

+''', +} -- cgit v1.2.1 From 3bfcb3e651980f1675807b8f82826dcb3e4e1013 Mon Sep 17 00:00:00 2001 From: Aleksander Sadikov Date: Tue, 27 Sep 2016 02:06:15 +0200 Subject: English translation for is_sorted/1 added. --- prolog/problems/sorting/is_sorted_1/en.py | 81 ++++++++++++++++++++++++++++++- prolog/problems/sorting/is_sorted_1/sl.py | 2 +- 2 files changed, 81 insertions(+), 2 deletions(-) (limited to 'prolog/problems/sorting') 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. ''' -hint = {} +plan = ['''\ +

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.

+''', '''\ +

You do know how to access the first two elements of the list, right? And the arithmetic comparison +operators were introduced in the previous batch of exercises.

+''', '''\ +

If the given list L is composed of heads H1 and H2 and of tail +T, and if we assume that tail T along with the second head is sorted, and furthermore +H1 is smaller or equal to H2, then the whole list L is sorted.

+'''] + +hint = { + 'eq_instead_of_equ': '''\ +

The operator == is "stricter" than operator = in the sense that +for the latter it is enough to be able to make the two operands equal (unification).

+

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).

+''', + + 'eq_instead_of_equ_markup': '''\ +

Perhaps the operator for unification (=) would be better?

+''', + + 'base_case': '''\ +

Did you think of a base case? Which is one of the shortest sorted lists?

+''', + + 'recursive_case': '''\ +

The base case is ok. However, what about the general recursive case?

+''', + + 'predicate_always_false': '''\ +

It seems your predicate is always "false". Did you give it the correct name, +or is it perhaps misspelled?

+

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?

+

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 X is simultaneously smaller and greater than +Y, or something similarly impossible).

+''', + + 'timeout': '''\ +

Is there an infinite recursion at work here? How will it ever stop?

+

Or perhaps is there a missing, faulty, or simply incompatible (with the general recursive case) base case?

+''', + + '[]_base_case_missing': '''\ +

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.

+''', + + 'duplicates_fail': '''\ +

Did you forget about duplicate elements? The list below is also sorted!

+

?- is_sorted([25,25,25,25]).

+''', + + 'H1_instead_of_H2_sent_into_recursion': '''\ +

Did you send the wrong of the two list heads into recursion?

+''', + + 'base_case_at_len_1_missing': '''\ +

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.

+''', + + 'both_heads_omitted_from_recursion': '''\ +

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?

+

?- is_sorted([1,3,14,16,24,25]).

+

?- is_sorted([24,25,14,16,1,3]).

+''', + + 'min_used': '''\ +

Try solving this exercise without using the predicate min/2. Your solution should have the +time complexity of O(n). By using min/2 the complexity is typically about O(n*n).

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

'both_heads_omitted_from_recursion': '''\

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.

+Ampak žal to ne gre! Od spodnjih dveh primerov eden deluje pravilno in eden ne, ugotovi v čem je razlika.

?- is_sorted([1,3,14,16,24,25]).

?- is_sorted([24,25,14,16,1,3]).

''', -- cgit v1.2.1