From ca743bffb497dea794950bf2bbda45e3bb4c936b Mon Sep 17 00:00:00 2001 From: Aleksander Sadikov Date: Sat, 27 Aug 2016 03:31:18 +0200 Subject: English translation for conc/3 added. --- prolog/problems/lists/conc_3/en.py | 112 ++++++++++++++++++++++++++++++++++++- prolog/problems/lists/conc_3/sl.py | 10 ++-- 2 files changed, 116 insertions(+), 6 deletions(-) (limited to 'prolog/problems/lists') diff --git a/prolog/problems/lists/conc_3/en.py b/prolog/problems/lists/conc_3/en.py index e25ae32..2e74e5e 100644 --- a/prolog/problems/lists/conc_3/en.py +++ b/prolog/problems/lists/conc_3/en.py @@ -10,4 +10,114 @@ description = '''\ X = [1,2,3]. ''' -hint = {} +plan = ['''\ +

+''', '''\ +

Let's start with an easy question. What do I get if I concatenate an empty list and a list L2?

+''', '''\ +

Now, assume that the first list has exactly one element. Let's temporarily take it out which leaves us +with an empty list. But wait! Isn't this situation now similar to the one we dealt with before? Of course, we just +reduced the problem into a smaller one (by one element smaller). Let recursion solve this smaller problem. Just don't +forget to expand the recursion's result with the element you have taken out at the beginning...

+''', '''\ +

Declarative/logic reasoning: Assume the first list L1 has head H and tail +T. If the recursive result of concatenating T and L2 is some list +L3, and if we add element H at the beginning of list L3, what do we get? +A concatenation of L1 and L2!

+'''] + +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). Perhaps by using = +you can make the predicate rev/2 more general (e.g. able to work with output arguments becoming inputs).

+

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? What is the simplest possible case? +What's the answer if, for example, the first list is empty? (Just the first list should be empty, +the second one can be arbitrary.)

+''', + + 'base_case_arbitrary': '''\ +

How can the result of concatenating two lists be an arbitrary list (a variable without an assigned value)?

+

If your base case is similar to conc([], L, _), +then you should rethink it: what is the result of the concatenation, what do you return as the result? +The base case always fully specifies the result, usually there are no unknowns (_ +or variables without assigned values) in what is being returned as the result.

+''', + + '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 an empty list [] is equal to a list with +exactly three elements [A,B,C], +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? +Are you maybe reducing the first list, but your base case stops with an empty second list (or vice versa)?

+''', + + 'second_list_iteration': '''\ +

It seems you're processing (reducing) the second list. The mechanism at work is correct, however, +the final ordering of the elements is not. It's better to process the first list in this way and +leave the second one as is.

+

There's another reason to process the first list: in this way the solution of this essential exercise +will be the same for everyone, and we'll be able to use conc/3 in a standardised way. This +will be very important later on.

+''', + + 'insertion_into_second_list': ''' +

Is your recursive call of the form conc(T, [H|L2], ...)? +Don't insert the first list's head into the second list as this will result in the wrong ordering +of the elements. Let the recursion alone take care of concatenating the first list's tail +T with the second list L2, and then, when returning the complete result, +add the first list's head H into its proper place.

+''', + + 'two_heads': '''\ +

Do you really need two list heads? Are you trying to reduce both lists? This is not a good idea, it is +difficult to solve the exercise in this way. Rather simply reduce the first list only, and leave the +other list as is.

+''', + + 'two_heads_markup': '''\ +

Do you really need two list heads?

+''', + + 'forcing_result_onto_recursion': ''' +

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.

+

Is your recursive call of the form conc(T, L2, [H|...])? This forces the recursive call to +return the head at the start of the concatenated list. But it doesn't know of this head, because you just +took it away! Inserting the head into the result, returned by the recursive call, is your job. To put it shortly, +insert H outside of the recursive call.

+''', + + 'final_hint': '''\ +

Predicate conc/3 will be useful for much more than just concatenating two lists. +Among other things it can be used "in the other direction" -- for dividing a list into two parts. Try the +following queries:

+

?- conc(L1, L2, [a,b,c,d]).

+

?- conc([X,Y], L2, [a,b,c,d,e,f]).

+

Did you notice that the second query returned the first two elements from the list [a,b,c,d,e,f]?

+

Furthermore, conc/3 is useful to search for patterns in a list, e.g.:

+

?- conc(_, [X,X|_], [a,b,c,c,d,e,f,f,g,h,h]).

+

Right, this query finds all possibilities where two identical elements appear one after the other in a list +(pattern X,X). Basically the query said that "there are some elements (possibly zero) in front, then follow two +identical elements, and then again some elements (possibly zero) at the end."

+

There are many other usages of conc/3, you will discover them along the way.

+''', +} diff --git a/prolog/problems/lists/conc_3/sl.py b/prolog/problems/lists/conc_3/sl.py index be2590e..5b0a639 100644 --- a/prolog/problems/lists/conc_3/sl.py +++ b/prolog/problems/lists/conc_3/sl.py @@ -92,8 +92,8 @@ res težko prišel do pravilne rešitve. Raje zmanjšuj samo prvi seznam in pust 'forcing_result_onto_recursion': '''

Ne vsiljuj rekurziji kaj naj vrne, prepusti se ji. To je tisti del, ko narediš predpostavko, če je ta izpolnjena, potem bo tvoje pravilo delovalo za večji primer.

-

Je tvoj rekurzivni klic oblike conc(T, L2 [H|...])? S tem vsiljuješ rekurziji -da mora vrniti tudi glavo, ki si jo prej že dal začasno stran. Glavo moraš na koncu na primerno mesto +

Je tvoj rekurzivni klic oblike conc(T, L2, [H|...])? S tem vsiljuješ rekurziji +da mora vrniti tudi glavo, ki si jo prej že dal začasno stran. Glavo moraš na koncu na primerno mesto vstaviti ti. Skratka, glavo H dodaj izven rekurzivnega klica.

''', @@ -105,9 +105,9 @@ Med drugim je uporaben "v obratni smeri" za delitev seznama na dva dela, poskusi

Si opazil, da je drugo vprašanje v bistvu vrnilo prva dva elementa iz seznama [a,b,c,d,e,f]?

Nadalje je conc/3 uporaben za iskanje vzorcev v seznamu, npr. takole:

?- conc(_, [X,X|_], [a,b,c,c,d,e,f,f,g,h,h]).

-

Tako je, to vprašanje najde vse možnosti, kjer se dva elementa ponovita drug za drugim v seznamu (vzorec X,X). +

Tako je, to vprašanje najde vse možnosti, kjer se dva enaka elementa ponovita drug za drugim v seznamu (vzorec X,X). V bistvu smo rekli "nekaj poljubnih elementov (lahko tudi nič) je spredaj, potem sta dva enaka, potem pa spet nekaj -poljubnih elementov (lahko nič) zadaj." -Še veliko drugih koristi bo od conc/3, jih boš že še sproti spoznal.

+poljubnih elementov (lahko nič) zadaj."

+

Še veliko drugih koristi bo od conc/3, jih boš že še sproti spoznal.

''', } -- cgit v1.2.1 From 918513a870273ab70e6ea60ab25344b77a44fec3 Mon Sep 17 00:00:00 2001 From: Aleksander Sadikov Date: Sun, 28 Aug 2016 23:07:01 +0200 Subject: English translation for memb/2 added. --- prolog/problems/lists/conc_3/en.py | 2 +- prolog/problems/lists/memb_2/en.py | 68 +++++++++++++++++++++++++++++++++++++- 2 files changed, 68 insertions(+), 2 deletions(-) (limited to 'prolog/problems/lists') diff --git a/prolog/problems/lists/conc_3/en.py b/prolog/problems/lists/conc_3/en.py index 2e74e5e..c384222 100644 --- a/prolog/problems/lists/conc_3/en.py +++ b/prolog/problems/lists/conc_3/en.py @@ -30,7 +30,7 @@ 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). Perhaps by using = -you can make the predicate rev/2 more general (e.g. able to work with output arguments becoming inputs).

+you can make the predicate conc/3 more general (e.g. able to work with output arguments becoming inputs).

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

''', diff --git a/prolog/problems/lists/memb_2/en.py b/prolog/problems/lists/memb_2/en.py index ae62825..681c18a 100644 --- a/prolog/problems/lists/memb_2/en.py +++ b/prolog/problems/lists/memb_2/en.py @@ -12,4 +12,70 @@ description = '''\ X = 1. ''' -hint = {} +plan = ['''\ +

Where can we find the searched for element X? Remember that the list has two parts: the head and +the tail. Therefore, there are two possibilies! ;)

+''', '''\ +

+

In prolog we can understand a list like a queue of people waiting for a bus. The driver only sees +the first person in the queue, the others are hidden in the list's tail. So the element X +can either be at the start of the queue or...

+''', '''\ +

It's easy to look at ("search for") the head of the list. But how do we search the tail? Simply, +we remove the first element and repeat the search with the smaller list (tail). If [H|T] +is our whole list, then T is this same list without the first element. +Since the new list (tail) is smaller, we reduced the problem and thus facilitated the use of recursion.

+'''] + +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). Perhaps by using = +you can make the predicate memb/2 more general (e.g. able to work with output arguments becoming inputs).

+

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? What is the simplest possible case if the element is present in the list? +Which element in the list is the easiest to access?

+''', + + '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 an empty list [] is equal to a list with +exactly three elements [A,B,C], +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?

+''', + + 'final_hint': '''\ +

Predicate memb/2 is useful for much more than just checking whether a list contains +a given element or not. Actually, most of the time, it's used in "a different direction" as +"return some element X from list L". In fact you've just written yourself +a generator of elements from the list.

+

Try the following query:

+

?- memb(Coin, [1,2,5,10,20,50,100,200]).

+

or this one:

+

?- memb(Operator, [+, -, *, /]).

+

Can you form a query to ask prolog how do we get a sum of 30 cents with exactly three coins? +The operator =:= is used to check for arithmetic equality. How many solutions are there? ;)

+''', +} -- cgit v1.2.1 From 464f5fd3eebfc30fa487eebb29b24727b98276f1 Mon Sep 17 00:00:00 2001 From: Aleksander Sadikov Date: Mon, 29 Aug 2016 00:45:09 +0200 Subject: English translation for insert/3 added. --- prolog/problems/lists/insert_3/en.py | 83 +++++++++++++++++++++++++++++++++++- prolog/problems/lists/insert_3/sl.py | 2 +- 2 files changed, 83 insertions(+), 2 deletions(-) (limited to 'prolog/problems/lists') diff --git a/prolog/problems/lists/insert_3/en.py b/prolog/problems/lists/insert_3/en.py index 5553445..0de098b 100644 --- a/prolog/problems/lists/insert_3/en.py +++ b/prolog/problems/lists/insert_3/en.py @@ -10,4 +10,85 @@ description = '''\ L = [2,3,1]. ''' -hint = {} +plan = [''' +

+

Where in the list can we insert a new element X? Remember that a list has two parts: head and tail. +That means there are two possibilies. That's right, only two -- but in the tail we can again insert either as its +new head or into the tail of the tail. And so on. Recursion to the rescue!

+''', '''\ +

What is the simplest option? Insert at the beginning!

+''', '''\ +

How do I insert into the list's tail? Just divide the list into its head and tail, recursively (as +the problem is one element smaller now) insert into the tail, and at the end don't forget about the +head previously taken away.

+''', '''\ +

Recursive step: if we assume NewTail is the tail with already inserted element X, +then [H|NewTail] is the whole list with the element X inserted.

+'''] + +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). Perhaps by using = +you can make the predicate insert/3 more general (e.g. able to work with output arguments becoming inputs). +This might come in handy later on!

+

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? In which place in the list is it the easiest to insert a new element?

+''', + + '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 an empty list [] is equal to a list with +exactly three elements [A,B,C], +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?

+''', + + 'ins_results_in_empty_list': '''\ +

How can the result of the insertion be an empty list?

+

If that is your base case, rethink it! What is the result of the insertion?

+''', + + 'ins_results_in_arbitrary_result': '''\ +

How can the result of the insertion be an arbitrary list or an unassigned variable?

+

If that is your base case, rethink it! What is the result of the insertion?

+''', + + 'lost_heads': '''\ +

+

The element has been successfully inserted, but all the others before it are lost, right? +Did you forget to put the head back at the front of the list after returning from recursion?

+

Try asking prolog the following query and check all the solutions:

+

?- insert(q, [a,b,c,d], L).

+''', + + 'leading_heads_all_x': '''\ +

+

Did you forget (copy/paste?) and used [X|T] instead of the more general [H|T] +in the recursive case?

+

Of the following two queries one works and the other doesn't.

+

?- insert(d, [d,d,d,d,e,f,g], L).

+

?- insert(d, [a,b,c,d,e,f,g], L).

+''', +} diff --git a/prolog/problems/lists/insert_3/sl.py b/prolog/problems/lists/insert_3/sl.py index 17efb5b..7f62f7e 100644 --- a/prolog/problems/lists/insert_3/sl.py +++ b/prolog/problems/lists/insert_3/sl.py @@ -74,7 +74,7 @@ da je X hkrati starš in sestra od Y ali kaj podobno z

Element je vstavljen, ampak vsi pred njim so se pa izgubili, kajne? Si pozabil dati glavo nazaj na začetek seznama, ko se vračaš iz rekurzije?

-

Poskusi postaviti naslednje vprašanje prologu in preglej vse rešitve:

+

Poskusi postaviti naslednje vprašanje prologu in preglej vse rešitve:

?- insert(q, [a,b,c,d], L).

''', -- cgit v1.2.1 From 185990bb4435b23e50464125ecaf84f8aeae766d Mon Sep 17 00:00:00 2001 From: Aleksander Sadikov Date: Mon, 29 Aug 2016 19:11:18 +0200 Subject: English translation for del/3 added. --- prolog/problems/lists/del_3/en.py | 93 +++++++++++++++++++++++++++++++++++- prolog/problems/lists/del_3/sl.py | 2 +- prolog/problems/lists/insert_3/en.py | 4 +- 3 files changed, 94 insertions(+), 5 deletions(-) (limited to 'prolog/problems/lists') diff --git a/prolog/problems/lists/del_3/en.py b/prolog/problems/lists/del_3/en.py index 99f87ca..d6e1e30 100644 --- a/prolog/problems/lists/del_3/en.py +++ b/prolog/problems/lists/del_3/en.py @@ -1,5 +1,5 @@ name = 'del/3' -slug = 'delete an element from list' +slug = 'delete element from list' description = '''\

del(X, L1, L2): the list L2 is obtained from L1 by deleting element X.

@@ -15,4 +15,93 @@ description = '''\ X = 3, L = [1,2]. ''' -hint = {} +plan = [''' +

+ + +

+

This exercise is very similar to the exercise memb/2, except that this time we also delete +the element we are looking for. Where in the list can element X be hiding? +Remember that a list has two parts: head and tail. Therefore there are two possibilies!

+''', '''\ +

What is the simplest option? Perhaps deleting the first element?

+''', '''\ +

How do I delete from the list's tail? Just divide the list into its head and tail, recursively (as +the problem is one element smaller now) delete from the tail, and at the end don't forget about the +head previously taken away.

+''', '''\ +

Recursive step: if we assume NewTail is the tail with element X already deleted, +then [H|NewTail] is the whole list with element X deleted.

+'''] + +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). Perhaps by using = +you can make the predicate del/3 more general (e.g. able to work with output arguments becoming inputs).

+

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? Where in the list is it the easiest to delete an element?

+''', + + '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 an empty list [] is equal to a list with +exactly three elements [A,B,C], +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?

+''', + + 'del_from_empty_list_success': '''\ +

You can't delete an element from an empty list!

+

If I delete an element from an empty list, this doesn't result in an empty list or anything else, but it +simply shouldn't succeed. You don't even have to include a rule for this as prolog by default acts like that. +You know how prolog loves to say "no"! :)

+

If that is your base case, rethink it! Where in the list is it the easiest to delete an element?

+''', + + 'lost_heads': '''\ +

+

The element has been successfully deleted, but all the others before it got deleted too, right? +Did you forget to put the head back at the front of the list after returning from recursion?

+

Try asking the following query:

+

?- del(d, [a,b,c,d,e,f,g], L).

+''', + + 'leading_heads_all_x': '''\ +

+

Did you forget (copy/paste?) and used [X|T] instead of the more general [H|T] +in the recursive case?

+

Of the following two queries one works and the other doesn't.

+

?- del(d, [d,d,d,d,e,f,g], L).

+

?- del(d, [a,b,c,d,e,f,g], L).

+''', + + 'final_hint': '''\ +

Interesting tidbit. Inserting and deleting an element into/from the list are opposite operations. +Just by playing around with the arguments you can solve del/3 using insert/3.

+

Logically the following holds: deleting element X from list BigList resulting +in list SmallList is the same as inserting element X +into list SmallList to get list BigList as a result. ;)

+''', +} diff --git a/prolog/problems/lists/del_3/sl.py b/prolog/problems/lists/del_3/sl.py index feee5e4..17df017 100644 --- a/prolog/problems/lists/del_3/sl.py +++ b/prolog/problems/lists/del_3/sl.py @@ -97,7 +97,7 @@ Si pozabil dati glavo nazaj na začetek seznama, ko se vračaš iz rekurzije?

Zanimivost: operaciji vstavljanja in brisanja iz seznama sta si ravno nasprotni. Če se malce poigraš z argumenti, lahko del/3 rešiš kar z insert/3.

Logično velja naslednje: če zbrišem X iz seznama BigList in dobim kot rezultat -seznam SmallList je isto kot če vstavim X v seznam SmallList in dobim +seznam SmallList je isto kot če vstavim X v seznam SmallList in dobim kot rezultat seznam BigList. ;)

''', } diff --git a/prolog/problems/lists/insert_3/en.py b/prolog/problems/lists/insert_3/en.py index 0de098b..d246932 100644 --- a/prolog/problems/lists/insert_3/en.py +++ b/prolog/problems/lists/insert_3/en.py @@ -23,7 +23,7 @@ the problem is one element smaller now) insert into the tail, and at the end don head previously taken away.

''', '''\

Recursive step: if we assume NewTail is the tail with already inserted element X, -then [H|NewTail] is the whole list with the element X inserted.

+then [H|NewTail] is the whole list with element X inserted.

'''] hint = { @@ -79,7 +79,7 @@ or something similarly impossible).

The element has been successfully inserted, but all the others before it are lost, right? Did you forget to put the head back at the front of the list after returning from recursion?

-

Try asking prolog the following query and check all the solutions:

+

Try asking the following query and check all the solutions:

?- insert(q, [a,b,c,d], L).

''', -- cgit v1.2.1 From ac398acf224fbb6b8d5cc201bd5d924c33c9ba51 Mon Sep 17 00:00:00 2001 From: Aleksander Sadikov Date: Mon, 29 Aug 2016 20:44:27 +0200 Subject: English translation for dup/2 added. --- prolog/problems/lists/dup_2/en.py | 75 ++++++++++++++++++++++++++++++++++++++- prolog/problems/lists/dup_2/sl.py | 2 +- 2 files changed, 75 insertions(+), 2 deletions(-) (limited to 'prolog/problems/lists') diff --git a/prolog/problems/lists/dup_2/en.py b/prolog/problems/lists/dup_2/en.py index 3639683..e944f74 100644 --- a/prolog/problems/lists/dup_2/en.py +++ b/prolog/problems/lists/dup_2/en.py @@ -10,4 +10,77 @@ description = '''\ X = [1,1,2,2,3,3]. ''' -hint = {} +plan = [''' +

+

This is an exercise in classic recursion. Let's be brave and assume that we already have +a duplicated tail of the list. Then all we need to do is to duplicate the head (H becomes H, H) and +add this at the start of the duplicated tail.

+''', '''\ +

A base case must be elementary, right? What if the list doesn't contain any elements at all, +what is the result in this case?

+''', '''\ +

If we have a duplicated tail DT and put two heads [H, H] in front of it, +then that is exactly the duplicated list.

+

And how do we get the duplicated tail? Since the tail is smaller than the whole list, +we can use recursion on 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). Perhaps by using = +you can make the predicate dup/2 more general (e.g. able to work with output arguments becoming inputs).

+

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_missing_[]': '''\ +

Your base case makes perfect sense, but it doesn't work for a very specific case: an empty list. +Tweak it a little bit. However, don't write two base cases, because that will result in a new problem: +the (albeit correct) solutions will all be repeated twice.

+''', + + 'base_case_arbitrary': '''\ +

How can the result of duplicating an empty list be an arbitrary list or an unassigned variable? +As the mathematicians would say: "Two times zero is zero and not just anything!"

+

If your base case is dup([], _)., rethink it! What is the result of +duplicating the elements of an empty list?

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

Did you think of a base case? Which list is the easiest to "duplicate"?

+''', + + '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 an empty list [] is equal to a list with +exactly three elements [A,B,C], +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?

+''', + + 'forcing_result_onto_recursion': ''' +

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.

+

Is your recursive call of the form dup(T, [H,H|...])? This forces the recursive call to +return the duplicated head at the start of the list. But it doesn't know of this head, because you just +took it away! Adding the duplicated head to the result, returned by the recursive call, is your job. +To put it shortly, add the duplicated H outside of the recursive call.

+''', +} diff --git a/prolog/problems/lists/dup_2/sl.py b/prolog/problems/lists/dup_2/sl.py index 0358726..b1492c5 100644 --- a/prolog/problems/lists/dup_2/sl.py +++ b/prolog/problems/lists/dup_2/sl.py @@ -71,7 +71,7 @@ da je X hkrati starš in sestra od Y ali kaj podobno z

Ne vsiljuj rekurziji kaj naj vrne, prepusti se ji. To je tisti del, ko narediš predpostavko, če je ta izpolnjena, potem bo tvoje pravilo delovalo za večji primer.

Je tvoj rekurzivni klic oblike dup(T, [H,H|...])? S tem vsiljuješ rekurziji -da mora vrniti tudi podvojeno glavo. To moraš narediti ti z (obdelanim) rezultatom, ki ga rezurzija vrne. +da mora vrniti tudi podvojeno glavo. To moraš narediti ti z (obdelanim) rezultatom, ki ga rezurzija vrne. Skratka, [H,H] dodaj izven rekurzivnega klica.

''', } -- cgit v1.2.1 From 0331b2ff089f33a33f66470cec305ff08f829a30 Mon Sep 17 00:00:00 2001 From: Aleksander Sadikov Date: Tue, 30 Aug 2016 02:33:37 +0200 Subject: English translation for last_elem/2 added. --- prolog/problems/lists/last_elem_2/en.py | 84 ++++++++++++++++++++++++++++++++- prolog/problems/lists/last_elem_2/sl.py | 2 +- 2 files changed, 84 insertions(+), 2 deletions(-) (limited to 'prolog/problems/lists') diff --git a/prolog/problems/lists/last_elem_2/en.py b/prolog/problems/lists/last_elem_2/en.py index 93c7c05..5eec3b8 100644 --- a/prolog/problems/lists/last_elem_2/en.py +++ b/prolog/problems/lists/last_elem_2/en.py @@ -10,4 +10,86 @@ description = '''\ X = 1. ''' -hint = {} +plan = ['''\ +

It's easy to access the first element in a list, but to get to the last element one needs to +recursively go through the whole list.

+''', '''\ +

The list can be divided into its head and tail, and the search can proceed with the tail. +The problem is now smaller (the tail is shorter than the whole list), so we can use recursion.

+''', '''\ +

If X is the last element of tail T, then X is also +the last element of the whole list that looks like [H|T].

+'''] + +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). Perhaps by using = +you can make the predicate last_elem/2 more general (e.g. able to work with output arguments becoming inputs).

+

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? What's the simplest possible case? What if the list contains only one element?

+''', + + '[]_should_not_succeed': '''\ +

How did you succeed to find a last element in an empty list? You likely need a different base case.

+''', + + 'list_returned': '''\ +

You are returning a list instead of an element.

+''', + + 'clumsy_conc_use': '''\ +

Are you using conc/3? An interesting idea. Don't forget that the second list you're +concatenating must be of length one if you want to achieve the desired effect. +So a pattern of the form [X], right?

+''', + + 'unsuccessful_conc_use': '''\ +

Are you using conc/3? An interesting idea; it is possible to solve in this way. +However, a bit of tweaking is still needed. Don't forget that conc/3 has three arguments, +and all three are lists. Think about what kind of a pattern do you need...

+''', + + '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 an empty list [] is equal to a list with +exactly three elements [A,B,C], +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?

+''', + + 'final_hint': '''\ +

Interesting fact: predicate conc/3 can be used to search for patterns in lists. The last +element in a list is also a kind of pattern. What happens if we concatenate an arbitrary list _ +and a list of length one (in this order)? A list of length one is of course written as +[Element].

+

Try asking the following query:

+

?- conc(_, [Element], [a,b,c,d,e,f,q]).

+

So, can you now fetch the list's last element using conc/3? This will be very useful in +further exercises. On the other hand, of course, accessing the last element of a list is still quite +expensive, it's done in O(n) time. Therefore, if it's not important which element of a list is to be used, +or where in a list a new element is to be added, always work with the head.

+

And what does this query do? ;)

+

?- conc([a,b,c], [q], L).

+''', +} diff --git a/prolog/problems/lists/last_elem_2/sl.py b/prolog/problems/lists/last_elem_2/sl.py index afba57a..961963c 100644 --- a/prolog/problems/lists/last_elem_2/sl.py +++ b/prolog/problems/lists/last_elem_2/sl.py @@ -47,7 +47,7 @@ implicitno že kar v argumentih predikata (glavi stavka).

'clumsy_conc_use': '''\

Uporabljaš conc/3? Zanimiva ideja. Ne pozabi, da mora drugi seznam, ki ga konkateniraš -biti dolžine ena, če hočeš doseči to kar želiš. Torej vzorec oblike [X], kajne?

+biti dolžine ena, če hočeš doseči to kar želiš. Torej vzorec oblike [X], kajne?

''', 'unsuccessful_conc_use': '''\ -- cgit v1.2.1 From ca2741f8d02d88288dfd1127c0faa9709ab83e6e Mon Sep 17 00:00:00 2001 From: Aleksander Sadikov Date: Wed, 31 Aug 2016 03:08:54 +0200 Subject: English translation for permute/2 added. --- prolog/problems/lists/permute_2/en.py | 78 ++++++++++++++++++++++++++++++++++- prolog/problems/lists/permute_2/sl.py | 2 +- 2 files changed, 78 insertions(+), 2 deletions(-) (limited to 'prolog/problems/lists') diff --git a/prolog/problems/lists/permute_2/en.py b/prolog/problems/lists/permute_2/en.py index 201d8d6..64203f4 100644 --- a/prolog/problems/lists/permute_2/en.py +++ b/prolog/problems/lists/permute_2/en.py @@ -13,4 +13,80 @@ description = '''\ L = [3,2,1]. ''' -hint = {} +plan = ['''\ +

+

Try recursively constructing one possibility, but leave prolog its freedom. It will then return +all the possibilities by itself.

+''', '''\ +

There are several options, one goes like this: if I take away the head, this reduces the problem and I can +leave it to recursion, and at the end I put the head back. Where do I put the head? I insert it in +all possible places, one solution at a time.

+''', '''\ +

If I assume the recursion permutes the tail T into the "permutated tail" +PT and then I insert head H somewhere into PT, then I will get +some permutation of the initial list [H|T].

+'''] + +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? What's the most elementary case? What if the list is empty?

+''', + + 'base_case_arbitrary': '''\ +

How can the result of permutating a list be an arbitrary list or an unassigned variable?

+

If your base case is reminiscent of permute([], _), rethink it! +What should be the result of permutating a list? +The base case always fully specifies the result, usually there are no unknowns (_ +or variables without assigned values) in what is being returned as the result.

+''', + + 'unsuccessful_conc_use': '''\ +

Are you using conc/3? It's probably not so useful to solve this exercise, +but the solution to some other previous exercise might be what is required.

+''', + + 'forcing_result_onto_recursion': ''' +

Don't force the result onto recursion, don't tell it what it should return. Just let it be and +assume it will do its job. If this assumption is correct, then the rule will work for a larger case.

+

Is your recursive call of the form permute(T, [H|...])? This forces the recursive call to +also return the head H which it doesn't know of since you previously took it away. +Inserting the head into the result, returned by the recursive call, is your job. To put it shortly, +insert H outside of the recursive call.

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

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

+''', + + 'no_insert_or_delete': '''\ +

The base case is ok. However, what about the general recursive case? Perhaps it's a good idea +to reuse some previous exercise?

+''', + + '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 an empty list [] is equal to a list with +exactly three elements [A,B,C], +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?

+''', +} diff --git a/prolog/problems/lists/permute_2/sl.py b/prolog/problems/lists/permute_2/sl.py index 8cd11e9..ccf4cd7 100644 --- a/prolog/problems/lists/permute_2/sl.py +++ b/prolog/problems/lists/permute_2/sl.py @@ -59,7 +59,7 @@ rešena naloga.

Ne vsiljuj rekurziji kaj naj vrne, prepusti se ji. To je tisti del, ko narediš predpostavko, če je ta izpolnjena, potem bo tvoje pravilo delovalo za večji primer.

Je tvoj rekurzivni klic oblike permute(T, [H|...])? S tem vsiljuješ rekurziji -da mora vrniti tudi glavo, ki je sploh ne pozna, ker si jo ravnokar vzel stran! To moraš +da mora vrniti tudi glavo, ki je sploh ne pozna, ker si jo ravnokar vzel stran! To moraš narediti ti z rezultatom, ki ga rekurzija vrne. Skratka, element H dodaj izven rekurzivnega klica.

''', -- cgit v1.2.1 From c115ebcb77426b1983242cb095650657126a51ce Mon Sep 17 00:00:00 2001 From: Aleksander Sadikov Date: Wed, 31 Aug 2016 23:30:35 +0200 Subject: English translation for divide/3 added. --- prolog/problems/lists/conc_3/en.py | 3 +- prolog/problems/lists/divide_3/en.py | 84 ++++++++++++++++++++++++++++++++++- prolog/problems/lists/insert_3/en.py | 3 +- prolog/problems/lists/permute_2/en.py | 3 +- 4 files changed, 85 insertions(+), 8 deletions(-) (limited to 'prolog/problems/lists') diff --git a/prolog/problems/lists/conc_3/en.py b/prolog/problems/lists/conc_3/en.py index c384222..be32b7d 100644 --- a/prolog/problems/lists/conc_3/en.py +++ b/prolog/problems/lists/conc_3/en.py @@ -60,8 +60,7 @@ or is it perhaps misspelled?

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 an empty list [] is equal to a list with -exactly three elements [A,B,C], -or something similarly impossible).

+exactly three elements [A,B,C], or something similarly impossible).

''', 'timeout': '''\ diff --git a/prolog/problems/lists/divide_3/en.py b/prolog/problems/lists/divide_3/en.py index f4cfa82..f47a51b 100644 --- a/prolog/problems/lists/divide_3/en.py +++ b/prolog/problems/lists/divide_3/en.py @@ -1,5 +1,5 @@ name = 'divide/3' -slug = 'split a list into parts of roughly equal length' +slug = 'split a list into two parts of roughly equal length' description = '''\

divide(L, L1, L2): the list L1 contains elements at odd positions in L, and the list L2 contains the elements at even positions in L.

@@ -10,4 +10,84 @@ description = '''\ X = [a,c,e], Y = [b,d,f]. ''' -hint = {} +plan = ['''\ +

+

You know... first, second, first, second, ...

+''', '''\ +

Can you pick two heads from the list's beginning? The pattern is [H1,H2|T].

+''', '''\ +

You take two elements from the list's beginning, the rest is recursively split, and then you +accordingly add those two elements into the recursion's result. By taking the two elements out, +you reduce (simplify) the problem and thus enable the recursion.

+''', '''\ +

If we assume the recursion splits the tail T into lists L1 and L2, +and upon returning the result we add H1 at the start of L1 and H2 +at the start of L2, then we get the split of the initial list of the form [H1,H2|T] +into two approximately equal parts.

+'''] + +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? What's the simplest possible case? What if the list is empty?

+''', + + 'base_case_arbitrary': '''\ +

How can the result of splitting a list be an arbitrary list(s) or an unassigned variable(s)?

+

If your base case is reminiscent of divide([], _, _) or divide([X], [X|_], ...), +rethink it! What should be the result of splitting? The base case always fully specifies the result, +usually there are no unknowns (_ or variables without assigned values) in what is being +returned as the result.

+''', + + 'second_base_case_missing': '''\ +

The recursion doesn't always succeed. Are there perhaps two different cases how it could end? You know, +odd and even ;) Do you need an extra base case? Try the following two queries; one will succeed, and the +other will fail.

+

?- divide([a,b,c], L1, L2).

+

?- divide([a,b,c,d], L1, L2).

+''', + + 'unsuccessful_conc_use': '''\ +

Are you using conc/3? This is probably not a good idea here as conc/3 +splits the list in "blocks" and not on an element-by-element level. Rather try without it.

+''', + + 'forcing_result_onto_recursion': ''' +

Don't force the result onto recursion, don't tell it what it should return. Just let it be and +assume it will do its job. If this assumption is correct, then the rule will work for a larger case.

+

Is your recursive call of the form divide(T, [H1|...], [H2|...])? This forces the recursive call +to also return both heads that it doesn't know of since you previously took them away. +Adding those heads to the result, returned by the recursive call, is your job. To put it shortly, +add elements H1 and H2 outside the recursive call.

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

The base cases are 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 an empty list [] is equal to a list with +exactly three elements [A,B,C], 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?

+''', +} diff --git a/prolog/problems/lists/insert_3/en.py b/prolog/problems/lists/insert_3/en.py index d246932..f0a3e4a 100644 --- a/prolog/problems/lists/insert_3/en.py +++ b/prolog/problems/lists/insert_3/en.py @@ -56,8 +56,7 @@ or is it perhaps misspelled?

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 an empty list [] is equal to a list with -exactly three elements [A,B,C], -or something similarly impossible).

+exactly three elements [A,B,C], or something similarly impossible).

''', 'timeout': '''\ diff --git a/prolog/problems/lists/permute_2/en.py b/prolog/problems/lists/permute_2/en.py index 64203f4..ba20d67 100644 --- a/prolog/problems/lists/permute_2/en.py +++ b/prolog/problems/lists/permute_2/en.py @@ -81,8 +81,7 @@ or is it perhaps misspelled?

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 an empty list [] is equal to a list with -exactly three elements [A,B,C], -or something similarly impossible).

+exactly three elements [A,B,C], or something similarly impossible).

''', 'timeout': '''\ -- cgit v1.2.1