From 3ed1137118bf719eab1d3fc1d230441057cdf854 Mon Sep 17 00:00:00 2001 From: Aleksander Sadikov Date: Mon, 14 Mar 2016 17:22:11 +0100 Subject: Basics for permute/2 added. --- prolog/problems/lists/divide_3/common.py | 2 +- prolog/problems/lists/divide_3/sl.py | 10 ++-- prolog/problems/lists/permute_2/common.py | 77 ++++++++++++++++++++++++++++++- prolog/problems/lists/permute_2/sl.py | 76 +++++++++++++++++++++++++++++- 4 files changed, 158 insertions(+), 7 deletions(-) (limited to 'prolog/problems/lists') diff --git a/prolog/problems/lists/divide_3/common.py b/prolog/problems/lists/divide_3/common.py index 2d93c4c..ff42d34 100644 --- a/prolog/problems/lists/divide_3/common.py +++ b/prolog/problems/lists/divide_3/common.py @@ -105,7 +105,7 @@ def hint(code, aux_code): return [{'id': 'second_base_case_missing'}] # missing/failed base case - if not prolog.engine.ask_truthTO(engine_id, 'divide([], [], [])'): + if not prolog.engine.ask_truth(engine_id, 'divide([], [], [])'): return [{'id': 'base_case'}] # # target predicate seems to always be false diff --git a/prolog/problems/lists/divide_3/sl.py b/prolog/problems/lists/divide_3/sl.py index 3a9e5c2..bec9282 100644 --- a/prolog/problems/lists/divide_3/sl.py +++ b/prolog/problems/lists/divide_3/sl.py @@ -46,12 +46,14 @@ implicitno že kar v argumentih predikata (glavi stavka).

Kako je lahko rezultat delitve seznama poljuben seznam oz. karkoli?

Če je tvoj robni pogoj v stilu divide([], _, _) ali divide([X], [X|_], ...), ga še enkrat premisli: kaj je rezultat delitve, kaj vračaš? Robni pogoj je vedno dokončno specificirana -rešitev, tu načeloma ni neznank (_ ali neinicializiranih spremenljivk) v tem kar se vrača.

+rešitev, tu načeloma ni neznank (_ ali spremenljivk brez prirejenih vrednosti) v tem kar se vrača.

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

Rekurzija se ne konča vedno uspešno. Sta morda dva različna primera kako se lahko izteče? Saj veš, -sodo in liho ;) Je morda potreben še kakšen robni pogoj?

+sodo in liho ;) Je morda potreben še kakšen robni pogoj? Poskusi naslednja klica, eden bo uspešen, drugi pa ne:

+

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

+

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

''', 'unsuccessful_conc_use': '''\ @@ -63,8 +65,8 @@ težko boš prišel do posameznih elementov. Poskusi raje brez.

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 divide(T, [H1|...], [H2|...])? S tem vsiljuješ rekurziji -da mora vrniti tudi obe glavi, ki jih sploh ne pozna, ker si jih ti ravnokar vzel stran! To moraš -narediti ti z (obdelanimi) rezultati, ki jih rezurzija vrne. Skratka, elementa H1 in H2 +da mora vrniti tudi obe glavi, ki jih sploh ne pozna, ker si jih ravnokar vzel stran! To moraš +narediti ti z rezultati, ki jih rekurzija vrne. Skratka, elementa H1 in H2 dodaj izven rekurzivnega klica.

''', diff --git a/prolog/problems/lists/permute_2/common.py b/prolog/problems/lists/permute_2/common.py index e39300b..3035159 100644 --- a/prolog/problems/lists/permute_2/common.py +++ b/prolog/problems/lists/permute_2/common.py @@ -2,6 +2,9 @@ from operator import itemgetter import prolog.engine +import prolog.util +import socket +from server.hints import Hint, HintPopup import server.problems id = 107 @@ -19,6 +22,19 @@ permute(L, [X|P]) :- permute(L1, P). ''' +hint_type = { + 'eq_instead_of_equ_markup': HintPopup('eq_instead_of_equ_markup'), + 'eq_instead_of_equ': Hint('eq_instead_of_equ'), + 'predicate_always_false': Hint('predicate_always_false'), + 'base_case': Hint('base_case'), + 'recursive_case': Hint('recursive_case'), + 'timeout': Hint('timeout'), + 'base_case_arbitrary': Hint('base_case_arbitrary'), + 'second_base_case_missing': Hint('second_base_case_missing'), + 'unsuccessful_conc_use': Hint('unsuccessful_conc_use'), + 'forcing_result_onto_recursion': Hint('forcing_result_onto_recursion'), +} + test_cases = [ ('permute([], X)', [{'X': '[]'}]), @@ -48,5 +64,64 @@ def test(code, aux_code): return n_correct, len(test_cases), hints def hint(code, aux_code): - # TODO + tokens = prolog.util.tokenize(code) + + try: + engine_id, output = prolog.engine.create(code=code+aux_code, timeout=1.0) + + # strict equality testing instead of simple matching + # this is usually (but not necessarily) wrong + targets = [prolog.util.Token('EQ', '==')] + marks = [(t.pos, t.pos + len(t.val)) for t in tokens if t in targets] + if marks: + return [{'id': 'eq_instead_of_equ_markup', 'start': m[0], 'end': m[1]} for m in marks] + \ + [{'id': 'eq_instead_of_equ'}] + + # general unsuccessful use of conc (not appropriate for this exercise) + if prolog.util.Token('NAME', 'conc') in tokens: + return [{'id': 'unsuccessful_conc_use'}] + + # recursion is getting bigger and bigger + + + # forcing result onto recursion; case of divide(T, [H1|L1], [H2|L2]) + if not prolog.engine.ask_truthTO(engine_id, 'divide([a,b,c], _, _)') and \ + prolog.engine.ask_truthTO(engine_id, + 'asserta( divide([cob], [yowza,cob], [brix]) ), divide([yowza,brix,cob], [cob], []), retract( divide([cob], [yowza,cob], [brix]) )'): + return [{'id': 'forcing_result_onto_recursion'}] + + # base case succeeds with arbitrary result + if prolog.engine.ask_truthTO(engine_id, 'divide([], L1, L2), (var(L1) ; var(L2))') or \ + prolog.engine.ask_truthTO(engine_id, 'divide([q], L1, L2), (var(L1) ; var(L2))') or \ + prolog.engine.ask_truthTO(engine_id, 'divide([q], [q|L1], L2), (var(L1) ; var(L2))'): + return [{'id': 'base_case_arbitrary'}] + + # one base case ok, the other one is missing (or bad) + # only trigger when recursion also works, because that makes more sense to the student + # than immediately telling him or her that there is another base case missing + if prolog.engine.ask_truthTO(engine_id, + 'divide([a,b], [a], [b]), \+ divide([a,b,c], [a,c], [b]) ; \+ divide([a,b], [a], [b]), divide([a,b,c], [a,c], [b])'): + return [{'id': 'second_base_case_missing'}] + + # missing/failed base case + if not prolog.engine.ask_truth(engine_id, 'divide([], [], [])'): + return [{'id': 'base_case'}] + +# # target predicate seems to always be false +# if not prolog.engine.ask_truthTO(engine_id, 'divide([_,_,_,_,_], _, _)') and \ +# not prolog.engine.ask_truthTO(engine_id, 'divide([_,_,_,_,_,_], _, _)'): +# return [{'id': 'predicate_always_false'}] + + # base cases work, the recursive doesn't (but it doesn't timeout) + # this may be left as the last, most generic hint + if not prolog.engine.ask_truth(engine_id, 'divide([qa,qb,qc,qd], [qa,qc], [qb,qd])'): + return [{'id': 'recursive_case'}] + + except socket.timeout as ex: + return [{'id': 'timeout'}] + + finally: + if engine_id: + prolog.engine.destroy(engine_id) + return [] diff --git a/prolog/problems/lists/permute_2/sl.py b/prolog/problems/lists/permute_2/sl.py index 8079b90..2237a54 100644 --- a/prolog/problems/lists/permute_2/sl.py +++ b/prolog/problems/lists/permute_2/sl.py @@ -17,4 +17,78 @@ description = '''\ L = [3,2,1]. ''' -hint = {} +plan = ['''\ +

+

Saj veš kako je šlo v osnovni šoli: prvi, drugi, prvi, ...

+''', '''\ +

Znaš vzeti dva elementa z začetka seznama? Vzorec je [H1,H2|T].

+''', '''\ +

Vzameš dva elementa z začetka, preostanek rekurzivno razdeliš in to, kar vrne rekurzija, primerno +dopolniš s prej odvzetima elementoma. S tem, ko si vzel dva elementa z začetka, si problem zmanjšal.

+''', '''\ +

Če predpostavim, da rekurzija razdeli rep T na podseznama L1 in L2 +ter ob vračanju v L1 na začetek dodam H1 in v L2 na začetek +dodam H2, potem sem razdelil začetni seznam, ki je oblike [H1,H2|T].

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

Operator == je strožji od operatorja = v smislu, da je za slednjega dovolj, +da elementa lahko naredi enaka (unifikacija).

+

Seveda pa lahko nalogo rešiš brez obeh omenjenih operatorjev, spomni se, da lahko unifikacijo narediš +implicitno že kar v argumentih predikata (glavi stavka).

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

Morda bi bil bolj primeren operator za unifikacijo (=)?

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

Si pomislil na robni pogoj? Kaj je najbolj enostaven primer? Kaj, če je seznam prazen?

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

Kako je lahko rezultat delitve seznama poljuben seznam oz. karkoli?

+

Če je tvoj robni pogoj v stilu divide([], _, _) ali divide([X], [X|_], ...), +ga še enkrat premisli: kaj je rezultat delitve, kaj vračaš? Robni pogoj je vedno dokončno specificirana +rešitev, tu načeloma ni neznank (_ ali spremenljivk brez prirejenih vrednosti) v tem kar se vrača.

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

Rekurzija se ne konča vedno uspešno. Sta morda dva različna primera kako se lahko izteče? Saj veš, +sodo in liho ;) Je morda potreben še kakšen robni pogoj? Poskusi naslednja klica, eden bo uspešen, drugi pa ne:

+

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

+

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

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

Uporabljaš conc/3? Pri tej nalogi to ni najboljša ideja, ker conc/3 deli "v kosih", +težko boš prišel do posameznih elementov. Poskusi raje brez.

+''', + + '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 divide(T, [H1|...], [H2|...])? S tem vsiljuješ rekurziji +da mora vrniti tudi obe glavi, ki jih sploh ne pozna, ker si jih ravnokar vzel stran! To moraš +narediti ti z rezultati, ki jih rekurzija vrne. Skratka, elementa H1 in H2 +dodaj izven rekurzivnega klica.

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

Robni primeri delujejo. Kaj pa rekurzivni, splošni, primer?

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

Vse kaže, da tvoj predikat vedno vrne "false". Si mu dal pravilno ime, si se morda pri imenu zatipkal?

+

Če je ime pravilno, se morda splača preveriti tudi, če se nisi zatipkal kje drugje, +je morda kakšna pika namesto vejice ali obratno, morda kakšna spremenljivka z malo začetnico?

+

Možno je seveda tudi, da so tvoji pogoji prestrogi ali celo nemogoči (kot bi bila npr. zahteva, +da je X hkrati starš in sestra od Y ali kaj podobno zlobnega).

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

Je morda na delu potencialno neskončna rekurzija? Kako se bo ustavila?

+

Morda pa je kriv tudi manjkajoč, neustrezen ali preprosto nekompatibilen (s splošnim primerom) robni pogoj?

+''', +} -- cgit v1.2.1