diff options
author | Timotej Lazar <timotej.lazar@fri.uni-lj.si> | 2016-04-03 18:11:08 +0200 |
---|---|---|
committer | Timotej Lazar <timotej.lazar@fri.uni-lj.si> | 2016-04-03 18:11:08 +0200 |
commit | 732b8f42029eced5e53debbff367131c2ea366ee (patch) | |
tree | 72affc8fd74958dad4a268a117682f76bc0b9600 /prolog/problems/sets | |
parent | dc8aea8bc8bc9fccda142312d0fa32413531d423 (diff) |
Prolog: add introduction for the sets group and make it visible
Diffstat (limited to 'prolog/problems/sets')
-rw-r--r-- | prolog/problems/sets/count_3/common.py | 96 | ||||
-rw-r--r-- | prolog/problems/sets/count_3/en.py | 11 | ||||
-rw-r--r-- | prolog/problems/sets/count_3/sl.py | 45 | ||||
-rw-r--r-- | prolog/problems/sets/diff_3/common.py | 4 | ||||
-rw-r--r-- | prolog/problems/sets/famrel.svg | 343 | ||||
-rw-r--r-- | prolog/problems/sets/intersect_3/common.py | 4 | ||||
-rw-r--r-- | prolog/problems/sets/intro_sl.html | 281 | ||||
-rw-r--r-- | prolog/problems/sets/is_subset_2/common.py | 4 | ||||
-rw-r--r-- | prolog/problems/sets/is_superset_2/common.py | 4 | ||||
-rw-r--r-- | prolog/problems/sets/powerset_2/common.py | 4 | ||||
-rw-r--r-- | prolog/problems/sets/sl.py | 8 | ||||
-rw-r--r-- | prolog/problems/sets/subset_2/common.py | 4 | ||||
-rw-r--r-- | prolog/problems/sets/union_3/common.py | 4 |
13 files changed, 797 insertions, 15 deletions
diff --git a/prolog/problems/sets/count_3/common.py b/prolog/problems/sets/count_3/common.py new file mode 100644 index 0000000..e770eaa --- /dev/null +++ b/prolog/problems/sets/count_3/common.py @@ -0,0 +1,96 @@ +from operator import itemgetter +import socket + +import prolog.engine +import prolog.util +from server.hints import Hint, HintPopup + +id = 120 +number = 10 +visible = True +facts = None + +solution = '''\ +count(_, [], 0). +count(X, [X|T], N) :- + count(X, T, NT), + N is NT + 1. +count(X, [Y|T], NT) :- + X \== Y, + count(X, T, NT). +''' + +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'), +} + +test_cases = [ + ('count(a, [], X)', + [{'X': '0'}]), + ('count(r, [a, r, b, c, r], X)', + [{'X': '2'}]), + ('count(l, [l, l, l, 1, 2, 3], X)', + [{'X': '3'}]), + ('count(z, [a, b, c, z, z], X)', + [{'X': '2'}]), +] + +def test(code, aux_code): + n_correct = 0 + engine_id = None + try: + engine_id, output = prolog.engine.create(code=code+aux_code, timeout=1.0) + if engine_id is not None and 'error' not in map(itemgetter(0), output): + # Engine successfully created, and no syntax error in program. + for query, answers in test_cases: + if prolog.engine.check_answers(engine_id, query=query, answers=answers, timeout=1.0): + n_correct += 1 + except socket.timeout: + pass + finally: + if engine_id: + prolog.engine.destroy(engine_id) + + hints = [{'id': 'test_results', 'args': {'passed': n_correct, 'total': len(test_cases)}}] + return n_correct, len(test_cases), hints + +def hint(code, aux_code): + 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'}] + + # missing/failed base case + if not prolog.engine.ask_truthTO(engine_id, 'count(42, [], 0)'): + return [{'id': 'base_case'}] + + # target predicate seems to always be false + if not prolog.engine.ask_truthTO(engine_id, 'count(_, _, _)'): + return [{'id': 'predicate_always_false'}] + + # base case works, 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, 'count(42, [2, 41, 42, -22, 42], 2)'): + 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/sets/count_3/en.py b/prolog/problems/sets/count_3/en.py new file mode 100644 index 0000000..481fd1c --- /dev/null +++ b/prolog/problems/sets/count_3/en.py @@ -0,0 +1,11 @@ +name = 'count/3' +slug = 'find the number of occurrences of an element in list' + +description = '''\ +<p><code>count(X, L, N)</code>: <code>N</code> is the number of times the element <code>X</code> appears in the list <code>L</code>.</p> +<pre> +?- count(1, [1,2,1,3,1], N). + N = 3. +</pre>''' + +hint = {} diff --git a/prolog/problems/sets/count_3/sl.py b/prolog/problems/sets/count_3/sl.py new file mode 100644 index 0000000..1e3f5d2 --- /dev/null +++ b/prolog/problems/sets/count_3/sl.py @@ -0,0 +1,45 @@ +name = 'count/3' +slug = 'Preštej kolikokrat se element pojavi v seznamu' + +description = '''\ +<p><code>count(X, L, N)</code>: <code>N</code> je število kolikokrat se element <code>X</code> pojavi v seznamu <code>L</code>.</p> +<pre> +?- count(1, [1,2,1,3,1], N). + N = 3. +</pre>''' + +hint = { + 'eq_instead_of_equ': '''\ +<p>Operator <code>==</code> je strožji od operatorja <code>=</code> v smislu, da je za slednjega dovolj, +da elementa lahko naredi enaka (unifikacija). Morda z uporabo <code>=</code> narediš predikat +<code>memb/2</code> delujoč tudi v kakšni drugi smeri.</p> +<p>Seveda pa lahko nalogo rešiš brez obeh omenjenih operatorjev, spomni se, da lahko unifikacijo narediš +implicitno že kar v argumentih predikata (glavi stavka).</p> +''', + + 'eq_instead_of_equ_markup': '''\ +<p>Morda bi bil bolj primeren operator za unifikacijo (=)?</p> +''', + + 'base_case': '''\ +<p>Si pomislil na robni pogoj? Kaj je najbolj enostaven primer, ko je element v seznamu? +Do katerega elementa najlažje prideš?</p> +''', + + 'recursive_case': '''\ +<p>Robni primer deluje. Kaj pa rekurzivni, splošni, primer?</p> +''', + + 'predicate_always_false': '''\ +<p>Vse kaže, da tvoj predikat vedno vrne "false". Si mu dal pravilno ime, si se morda pri imenu zatipkal?</p> +<p>Č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?</p> +<p>Možno je seveda tudi, da so tvoji pogoji prestrogi ali celo nemogoči (kot bi bila npr. zahteva, +da je <code>X</code> hkrati starš in sestra od <code>Y</code> ali kaj podobno zlobnega).</p> +''', + + 'timeout': '''\ +<p>Je morda na delu potencialno neskončna rekurzija? Kako se bo ustavila?</p> +<p>Morda pa je kriv tudi manjkajoč, neustrezen ali preprosto nekompatibilen (s splošnim primerom) robni pogoj?</p> +''', +} diff --git a/prolog/problems/sets/diff_3/common.py b/prolog/problems/sets/diff_3/common.py index 1f00d5c..578d203 100644 --- a/prolog/problems/sets/diff_3/common.py +++ b/prolog/problems/sets/diff_3/common.py @@ -5,8 +5,8 @@ import prolog.engine import server.problems id = 130 -number = 37 -visible = False +number = 40 +visible = True facts = None solution = '''\ diff --git a/prolog/problems/sets/famrel.svg b/prolog/problems/sets/famrel.svg new file mode 100644 index 0000000..bff500c --- /dev/null +++ b/prolog/problems/sets/famrel.svg @@ -0,0 +1,343 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" + "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<!-- Generated by graphviz version 2.38.0 (20140413.2041) + --> +<!-- Title: famrel Pages: 1 --> +<svg width="1170pt" height="332pt" + viewBox="0.00 0.00 1170.27 332.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"> +<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 328)"> +<title>famrel</title> +<polygon fill="white" stroke="none" points="-4,4 -4,-328 1166.27,-328 1166.27,4 -4,4"/> +<!-- tina --> +<g id="node1" class="node"><title>tina</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="241.169" cy="-306" rx="28.8653" ry="18"/> +<text text-anchor="middle" x="241.169" y="-302.3" font-family="noto sans" font-size="14.00">  tina♀</text> +</g> +<!-- william --> +<g id="node19" class="node"><title>william</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="241.169" cy="-234" rx="42.451" ry="18"/> +<text text-anchor="middle" x="241.169" y="-230.3" font-family="noto sans" font-size="14.00">  william♂</text> +</g> +<!-- tina->william --> +<g id="edge1" class="edge"><title>tina->william</title> +<path fill="none" stroke="black" d="M241.169,-287.697C241.169,-279.983 241.169,-270.712 241.169,-262.112"/> +<polygon fill="black" stroke="black" points="244.669,-262.104 241.169,-252.104 237.669,-262.104 244.669,-262.104"/> +</g> +<!-- sally --> +<g id="node2" class="node"><title>sally</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="342.169" cy="-234" rx="31.2902" ry="18"/> +<text text-anchor="middle" x="342.169" y="-230.3" font-family="noto sans" font-size="14.00">  sally♀</text> +</g> +<!-- melanie --> +<g id="node3" class="node"><title>melanie</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="342.169" cy="-162" rx="46.3387" ry="18"/> +<text text-anchor="middle" x="342.169" y="-158.3" font-family="noto sans" font-size="14.00">  melanie♀</text> +</g> +<!-- sally->melanie --> +<g id="edge6" class="edge"><title>sally->melanie</title> +<path fill="none" stroke="black" d="M342.169,-215.697C342.169,-207.983 342.169,-198.712 342.169,-190.112"/> +<polygon fill="black" stroke="black" points="345.669,-190.104 342.169,-180.104 338.669,-190.104 345.669,-190.104"/> +</g> +<!-- andrew --> +<g id="node22" class="node"><title>andrew</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="443.169" cy="-162" rx="44.1452" ry="18"/> +<text text-anchor="middle" x="443.169" y="-158.3" font-family="noto sans" font-size="14.00">  andrew♂</text> +</g> +<!-- sally->andrew --> +<g id="edge5" class="edge"><title>sally->andrew</title> +<path fill="none" stroke="black" d="M361.643,-219.503C376.287,-209.354 396.615,-195.265 413.308,-183.696"/> +<polygon fill="black" stroke="black" points="415.432,-186.482 421.657,-177.909 411.444,-180.729 415.432,-186.482"/> +</g> +<!-- joanne --> +<g id="node4" class="node"><title>joanne</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="484.169" cy="-90" rx="41.7203" ry="18"/> +<text text-anchor="middle" x="484.169" y="-86.3" font-family="noto sans" font-size="14.00">  joanne♀</text> +</g> +<!-- steve --> +<g id="node23" class="node"><title>steve</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="484.169" cy="-18" rx="35.1771" ry="18"/> +<text text-anchor="middle" x="484.169" y="-14.3" font-family="noto sans" font-size="14.00">  steve♂</text> +</g> +<!-- joanne->steve --> +<g id="edge9" class="edge"><title>joanne->steve</title> +<path fill="none" stroke="black" d="M484.169,-71.6966C484.169,-63.9827 484.169,-54.7125 484.169,-46.1124"/> +<polygon fill="black" stroke="black" points="487.669,-46.1043 484.169,-36.1043 480.669,-46.1044 487.669,-46.1043"/> +</g> +<!-- jill --> +<g id="node5" class="node"><title>jill</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="525.169" cy="-162" rx="27" ry="18"/> +<text text-anchor="middle" x="525.169" y="-158.3" font-family="noto sans" font-size="14.00">  jill♀</text> +</g> +<!-- jill->joanne --> +<g id="edge8" class="edge"><title>jill->joanne</title> +<path fill="none" stroke="black" d="M515.66,-144.765C510.712,-136.317 504.551,-125.799 498.995,-116.312"/> +<polygon fill="black" stroke="black" points="501.986,-114.493 493.911,-107.633 495.945,-118.031 501.986,-114.493"/> +</g> +<!-- vanessa --> +<g id="node6" class="node"><title>vanessa</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="46.169" cy="-162" rx="46.3387" ry="18"/> +<text text-anchor="middle" x="46.169" y="-158.3" font-family="noto sans" font-size="14.00">  vanessa♀</text> +</g> +<!-- susan --> +<g id="node8" class="node"><title>susan</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="95.169" cy="-90" rx="36.8706" ry="18"/> +<text text-anchor="middle" x="95.169" y="-86.3" font-family="noto sans" font-size="14.00">  susan♀</text> +</g> +<!-- vanessa->susan --> +<g id="edge12" class="edge"><title>vanessa->susan</title> +<path fill="none" stroke="black" d="M57.7813,-144.411C63.7616,-135.868 71.1741,-125.278 77.8179,-115.787"/> +<polygon fill="black" stroke="black" points="80.7727,-117.669 83.6401,-107.47 75.0381,-113.655 80.7727,-117.669"/> +</g> +<!-- patricia --> +<g id="node7" class="node"><title>patricia</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="241.169" cy="-162" rx="44.1452" ry="18"/> +<text text-anchor="middle" x="241.169" y="-158.3" font-family="noto sans" font-size="14.00">  patricia♀</text> +</g> +<!-- john --> +<g id="node25" class="node"><title>john</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="241.169" cy="-90" rx="31.2902" ry="18"/> +<text text-anchor="middle" x="241.169" y="-86.3" font-family="noto sans" font-size="14.00">  john♂</text> +</g> +<!-- patricia->john --> +<g id="edge14" class="edge"><title>patricia->john</title> +<path fill="none" stroke="black" d="M241.169,-143.697C241.169,-135.983 241.169,-126.712 241.169,-118.112"/> +<polygon fill="black" stroke="black" points="244.669,-118.104 241.169,-108.104 237.669,-118.104 244.669,-118.104"/> +</g> +<!-- michelle --> +<g id="node9" class="node"><title>michelle</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="189.169" cy="-18" rx="48.0316" ry="18"/> +<text text-anchor="middle" x="189.169" y="-14.3" font-family="noto sans" font-size="14.00">  michelle♀</text> +</g> +<!-- estelle --> +<g id="node10" class="node"><title>estelle</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="509.169" cy="-306" rx="40.0263" ry="18"/> +<text text-anchor="middle" x="509.169" y="-302.3" font-family="noto sans" font-size="14.00">  estelle♀</text> +</g> +<!-- george --> +<g id="node28" class="node"><title>george</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="584.169" cy="-234" rx="43.1824" ry="18"/> +<text text-anchor="middle" x="584.169" y="-230.3" font-family="noto sans" font-size="14.00">  george♂</text> +</g> +<!-- estelle->george --> +<g id="edge18" class="edge"><title>estelle->george</title> +<path fill="none" stroke="black" d="M525.814,-289.465C535.842,-280.105 548.788,-268.022 559.937,-257.616"/> +<polygon fill="black" stroke="black" points="562.389,-260.116 567.311,-250.734 557.613,-254.998 562.389,-260.116"/> +</g> +<!-- helen --> +<g id="node11" class="node"><title>helen</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="679.169" cy="-306" rx="36.1402" ry="18"/> +<text text-anchor="middle" x="679.169" y="-302.3" font-family="noto sans" font-size="14.00">  helen♀</text> +</g> +<!-- jerry --> +<g id="node30" class="node"><title>jerry</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="757.169" cy="-234" rx="32.0211" ry="18"/> +<text text-anchor="middle" x="757.169" y="-230.3" font-family="noto sans" font-size="14.00">  jerry♂</text> +</g> +<!-- helen->jerry --> +<g id="edge20" class="edge"><title>helen->jerry</title> +<path fill="none" stroke="black" d="M696.094,-289.811C706.973,-280.048 721.27,-267.217 733.296,-256.425"/> +<polygon fill="black" stroke="black" points="735.707,-258.964 740.812,-249.68 731.032,-253.754 735.707,-258.964"/> +</g> +<!-- elaine --> +<g id="node12" class="node"><title>elaine</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="676.169" cy="-234" rx="38.3335" ry="18"/> +<text text-anchor="middle" x="676.169" y="-230.3" font-family="noto sans" font-size="14.00">  elaine♀</text> +</g> +<!-- anna --> +<g id="node13" class="node"><title>anna</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="736.169" cy="-162" rx="33.7152" ry="18"/> +<text text-anchor="middle" x="736.169" y="-158.3" font-family="noto sans" font-size="14.00">  anna♀</text> +</g> +<!-- elaine->anna --> +<g id="edge22" class="edge"><title>elaine->anna</title> +<path fill="none" stroke="black" d="M689.784,-217.116C697.532,-208.076 707.384,-196.583 716.013,-186.515"/> +<polygon fill="black" stroke="black" points="718.757,-188.692 722.608,-178.821 713.443,-184.136 718.757,-188.692"/> +</g> +<!-- kramer --> +<g id="node31" class="node"><title>kramer</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="606.169" cy="-162" rx="43.1824" ry="18"/> +<text text-anchor="middle" x="606.169" y="-158.3" font-family="noto sans" font-size="14.00">  kramer♂</text> +</g> +<!-- elaine->kramer --> +<g id="edge23" class="edge"><title>elaine->kramer</title> +<path fill="none" stroke="black" d="M660.634,-217.465C651.429,-208.26 639.59,-196.421 629.303,-186.134"/> +<polygon fill="black" stroke="black" points="631.692,-183.573 622.146,-178.977 626.742,-188.523 631.692,-183.573"/> +</g> +<!-- margaret --> +<g id="node14" class="node"><title>margaret</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="1095.17" cy="-306" rx="52.1504" ry="18"/> +<text text-anchor="middle" x="1095.17" y="-302.3" font-family="noto sans" font-size="14.00">  margaret♀</text> +</g> +<!-- nevia --> +<g id="node16" class="node"><title>nevia</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="998.169" cy="-234" rx="35.1771" ry="18"/> +<text text-anchor="middle" x="998.169" y="-230.3" font-family="noto sans" font-size="14.00">  nevia♀</text> +</g> +<!-- margaret->nevia --> +<g id="edge25" class="edge"><title>margaret->nevia</title> +<path fill="none" stroke="black" d="M1073.64,-289.465C1059.64,-279.364 1041.25,-266.091 1026.13,-255.177"/> +<polygon fill="black" stroke="black" points="1027.82,-252.079 1017.66,-249.066 1023.72,-257.756 1027.82,-252.079"/> +</g> +<!-- alessandro --> +<g id="node33" class="node"><title>alessandro</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="1103.17" cy="-234" rx="59.1929" ry="18"/> +<text text-anchor="middle" x="1103.17" y="-230.3" font-family="noto sans" font-size="14.00">  alessandro♂</text> +</g> +<!-- margaret->alessandro --> +<g id="edge26" class="edge"><title>margaret->alessandro</title> +<path fill="none" stroke="black" d="M1097.15,-287.697C1098.03,-279.983 1099.09,-270.712 1100.07,-262.112"/> +<polygon fill="black" stroke="black" points="1103.56,-262.437 1101.21,-252.104 1096.6,-261.642 1103.56,-262.437"/> +</g> +<!-- ana --> +<g id="node15" class="node"><title>ana</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="870.169" cy="-306" rx="28.1352" ry="18"/> +<text text-anchor="middle" x="870.169" y="-302.3" font-family="noto sans" font-size="14.00">  ana♀</text> +</g> +<!-- aleksander --> +<g id="node34" class="node"><title>aleksander</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="893.169" cy="-234" rx="59.1929" ry="18"/> +<text text-anchor="middle" x="893.169" y="-230.3" font-family="noto sans" font-size="14.00">  aleksander♂</text> +</g> +<!-- ana->aleksander --> +<g id="edge27" class="edge"><title>ana->aleksander</title> +<path fill="none" stroke="black" d="M875.737,-288.055C878.325,-280.176 881.466,-270.617 884.365,-261.794"/> +<polygon fill="black" stroke="black" points="887.696,-262.868 887.493,-252.275 881.046,-260.683 887.696,-262.868"/> +</g> +<!-- luana --> +<g id="node17" class="node"><title>luana</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="900.169" cy="-162" rx="36.1402" ry="18"/> +<text text-anchor="middle" x="900.169" y="-158.3" font-family="noto sans" font-size="14.00">  luana♀</text> +</g> +<!-- nevia->luana --> +<g id="edge29" class="edge"><title>nevia->luana</title> +<path fill="none" stroke="black" d="M978.337,-218.834C963.991,-208.587 944.401,-194.594 928.421,-183.18"/> +<polygon fill="black" stroke="black" points="930.143,-180.109 919.971,-177.144 926.074,-185.805 930.143,-180.109"/> +</g> +<!-- daniela --> +<g id="node18" class="node"><title>daniela</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="994.169" cy="-162" rx="43.9143" ry="18"/> +<text text-anchor="middle" x="994.169" y="-158.3" font-family="noto sans" font-size="14.00">  daniela♀</text> +</g> +<!-- nevia->daniela --> +<g id="edge31" class="edge"><title>nevia->daniela</title> +<path fill="none" stroke="black" d="M997.18,-215.697C996.739,-207.983 996.21,-198.712 995.718,-190.112"/> +<polygon fill="black" stroke="black" points="999.211,-189.888 995.146,-180.104 992.223,-190.288 999.211,-189.888"/> +</g> +<!-- william->vanessa --> +<g id="edge10" class="edge"><title>william->vanessa</title> +<path fill="none" stroke="black" d="M209.839,-221.753C177.069,-209.99 125.417,-191.448 88.9153,-178.345"/> +<polygon fill="black" stroke="black" points="89.6445,-174.888 79.05,-174.803 87.2794,-181.476 89.6445,-174.888"/> +</g> +<!-- william->patricia --> +<g id="edge11" class="edge"><title>william->patricia</title> +<path fill="none" stroke="black" d="M241.169,-215.697C241.169,-207.983 241.169,-198.712 241.169,-190.112"/> +<polygon fill="black" stroke="black" points="244.669,-190.104 241.169,-180.104 237.669,-190.104 244.669,-190.104"/> +</g> +<!-- thomas --> +<g id="node20" class="node"><title>thomas</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="342.169" cy="-306" rx="44.1452" ry="18"/> +<text text-anchor="middle" x="342.169" y="-302.3" font-family="noto sans" font-size="14.00">  thomas♂</text> +</g> +<!-- thomas->sally --> +<g id="edge3" class="edge"><title>thomas->sally</title> +<path fill="none" stroke="black" d="M342.169,-287.697C342.169,-279.983 342.169,-270.712 342.169,-262.112"/> +<polygon fill="black" stroke="black" points="345.669,-262.104 342.169,-252.104 338.669,-262.104 345.669,-262.104"/> +</g> +<!-- thomas->william --> +<g id="edge2" class="edge"><title>thomas->william</title> +<path fill="none" stroke="black" d="M320.75,-290.155C306.288,-280.132 286.999,-266.763 271.034,-255.698"/> +<polygon fill="black" stroke="black" points="272.77,-252.644 262.558,-249.824 268.783,-258.397 272.77,-252.644"/> +</g> +<!-- jeffrey --> +<g id="node21" class="node"><title>jeffrey</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="424.169" cy="-234" rx="40.0263" ry="18"/> +<text text-anchor="middle" x="424.169" y="-230.3" font-family="noto sans" font-size="14.00">  jeffrey♂</text> +</g> +<!-- thomas->jeffrey --> +<g id="edge4" class="edge"><title>thomas->jeffrey</title> +<path fill="none" stroke="black" d="M360.367,-289.465C371.592,-279.883 386.16,-267.447 398.54,-256.878"/> +<polygon fill="black" stroke="black" points="400.97,-259.406 406.304,-250.251 396.425,-254.082 400.97,-259.406"/> +</g> +<!-- andrew->joanne --> +<g id="edge7" class="edge"><title>andrew->joanne</title> +<path fill="none" stroke="black" d="M452.885,-144.411C457.716,-136.163 463.664,-126.009 469.071,-116.777"/> +<polygon fill="black" stroke="black" points="472.204,-118.354 474.238,-107.956 466.163,-114.816 472.204,-118.354"/> +</g> +<!-- patrick --> +<g id="node24" class="node"><title>patrick</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="144.169" cy="-162" rx="41.4901" ry="18"/> +<text text-anchor="middle" x="144.169" y="-158.3" font-family="noto sans" font-size="14.00">  patrick♂</text> +</g> +<!-- patrick->susan --> +<g id="edge13" class="edge"><title>patrick->susan</title> +<path fill="none" stroke="black" d="M132.557,-144.411C126.576,-135.868 119.164,-125.278 112.52,-115.787"/> +<polygon fill="black" stroke="black" points="115.3,-113.655 106.698,-107.47 109.565,-117.669 115.3,-113.655"/> +</g> +<!-- john->michelle --> +<g id="edge16" class="edge"><title>john->michelle</title> +<path fill="none" stroke="black" d="M229.369,-73.1159C222.973,-64.5051 214.922,-53.6674 207.708,-43.9567"/> +<polygon fill="black" stroke="black" points="210.42,-41.7377 201.647,-35.7973 204.801,-45.912 210.42,-41.7377"/> +</g> +<!-- michael --> +<g id="node26" class="node"><title>michael</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="294.169" cy="-18" rx="45.6069" ry="18"/> +<text text-anchor="middle" x="294.169" y="-14.3" font-family="noto sans" font-size="14.00">  michael♂</text> +</g> +<!-- john->michael --> +<g id="edge15" class="edge"><title>john->michael</title> +<path fill="none" stroke="black" d="M253.196,-73.1159C259.715,-64.5051 267.921,-53.6674 275.273,-43.9567"/> +<polygon fill="black" stroke="black" points="278.205,-45.8827 281.451,-35.7973 272.624,-41.6572 278.205,-45.8827"/> +</g> +<!-- frank --> +<g id="node27" class="node"><title>frank</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="595.169" cy="-306" rx="35.1771" ry="18"/> +<text text-anchor="middle" x="595.169" y="-302.3" font-family="noto sans" font-size="14.00">  frank♂</text> +</g> +<!-- frank->george --> +<g id="edge17" class="edge"><title>frank->george</title> +<path fill="none" stroke="black" d="M592.45,-287.697C591.238,-279.983 589.781,-270.712 588.43,-262.112"/> +<polygon fill="black" stroke="black" points="591.867,-261.44 586.857,-252.104 584.952,-262.526 591.867,-261.44"/> +</g> +<!-- george->kramer --> +<g id="edge24" class="edge"><title>george->kramer</title> +<path fill="none" stroke="black" d="M589.495,-216.055C591.944,-208.261 594.911,-198.822 597.659,-190.079"/> +<polygon fill="black" stroke="black" points="601.08,-190.865 600.74,-180.275 594.402,-188.766 601.08,-190.865"/> +</g> +<!-- morty --> +<g id="node29" class="node"><title>morty</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="764.169" cy="-306" rx="38.3335" ry="18"/> +<text text-anchor="middle" x="764.169" y="-302.3" font-family="noto sans" font-size="14.00">  morty♂</text> +</g> +<!-- morty->jerry --> +<g id="edge19" class="edge"><title>morty->jerry</title> +<path fill="none" stroke="black" d="M762.439,-287.697C761.667,-279.983 760.74,-270.712 759.88,-262.112"/> +<polygon fill="black" stroke="black" points="763.357,-261.706 758.879,-252.104 756.392,-262.403 763.357,-261.706"/> +</g> +<!-- jerry->anna --> +<g id="edge21" class="edge"><title>jerry->anna</title> +<path fill="none" stroke="black" d="M752.086,-216.055C749.747,-208.261 746.916,-198.822 744.293,-190.079"/> +<polygon fill="black" stroke="black" points="747.578,-188.848 741.352,-180.275 740.873,-190.859 747.578,-188.848"/> +</g> +<!-- aleksandr --> +<g id="node32" class="node"><title>aleksandr</title> +<ellipse fill="none" stroke="black" stroke-width="0.75" cx="963.169" cy="-306" rx="53.6122" ry="18"/> +<text text-anchor="middle" x="963.169" y="-302.3" font-family="noto sans" font-size="14.00">  aleksandr♂</text> +</g> +<!-- aleksandr->aleksander --> +<g id="edge28" class="edge"><title>aleksandr->aleksander</title> +<path fill="none" stroke="black" d="M946.934,-288.765C938.051,-279.882 926.878,-268.709 917.023,-258.854"/> +<polygon fill="black" stroke="black" points="919.348,-256.23 909.802,-251.633 914.399,-261.179 919.348,-256.23"/> +</g> +<!-- aleksander->luana --> +<g id="edge30" class="edge"><title>aleksander->luana</title> +<path fill="none" stroke="black" d="M894.899,-215.697C895.671,-207.983 896.598,-198.712 897.458,-190.112"/> +<polygon fill="black" stroke="black" points="900.946,-190.403 898.459,-180.104 893.981,-189.706 900.946,-190.403"/> +</g> +<!-- aleksander->daniela --> +<g id="edge32" class="edge"><title>aleksander->daniela</title> +<path fill="none" stroke="black" d="M915.835,-217.291C930.165,-207.359 948.842,-194.415 964.365,-183.656"/> +<polygon fill="black" stroke="black" points="966.391,-186.511 972.616,-177.938 962.403,-180.757 966.391,-186.511"/> +</g> +</g> +</svg> diff --git a/prolog/problems/sets/intersect_3/common.py b/prolog/problems/sets/intersect_3/common.py index afece71..78cecb7 100644 --- a/prolog/problems/sets/intersect_3/common.py +++ b/prolog/problems/sets/intersect_3/common.py @@ -5,8 +5,8 @@ import prolog.engine import server.problems id = 129 -number = 36 -visible = False +number = 30 +visible = True facts = None solution = '''\ diff --git a/prolog/problems/sets/intro_sl.html b/prolog/problems/sets/intro_sl.html new file mode 100644 index 0000000..3763628 --- /dev/null +++ b/prolog/problems/sets/intro_sl.html @@ -0,0 +1,281 @@ +<!DOCTYPE html> +<html lang="sl"> +<head> + <meta charset="utf-8" /> + <title>Prolog: negacija in rez</title> + <link rel="stylesheet" type="text/css" href="../style.css" /> +</head> +<body> + +<h1>Prolog: negacija in rez</h1> +<p> +Kot ste videli, smo konjunkcijo in disjunkcijo spoznali že takoj v prvem sklopu. +Verjetno ste se že tedaj spraševali, kako je s tretjo, na nek način +komplementarno, logično operacijo, to je negacijo. Tako je, načrtno smo +zavlačevali z njeno predstavitvijo! Boste hitro videli, zakaj. No, sedaj pa je +vendarle napočil čas, da ugriznemo še v to jabolko. +</p> + +<h2>Rez (<code>!</code>)</h2> +<p> +Začnimo z rezom, saj ga bomo kasneje potrebovali za definicijo negacije. Rez v +prologu imenujemo posebej cilj, ki ga označimo s klicajem (<code>!</code>). Ta +cilj vedno uspe (v tem smislu je enak kot <code>true</code>), a ima stranski +učinek. Le-ta je, da prepreči ostale možne alternative. Poglejmo to kar na +primeru. Za hip si spet naložimo dejstva o družinskih drevesih iz prvega sklopa, +da lahko na njih naredimo nekaj demonstracij. +</p> + +<figure> + <a href="famrel.svg" target="_blank"> + <img src="famrel.svg" /> + </a> + <figcaption>Graf (gozd) družinskih relacij</figcaption> +</figure> + +<pre> +?- parent(thomas, X). +X = william ; +X = sally ; +X = jeffrey ; +no. +</pre> + +<p> +Zgornje vprašanje smo v naravnem jeziku interpretirali kot „kdo vse je otrok od +Thomasa?“ Vidimo, da ima Thomas tri otroke. Zdaj pa bomo na različne načine +našteli njegove vnuke in pri tem demonstrirali delovanje reza. +</p> +<pre> +?- parent(thomas, X), parent(X, Y). +X = william, Y = vanessa ; +X = william, Y = patricia ; +X = sally, Y = andrew ; +X = sally, Y = melanie ; +no. +</pre> + +<p> +To vprašanje našteje vse vnuke; kar poskusi. No, saj si sprogramiral to v prvem +sklopu. Vseh vnukov je… štirje so! +</p> +<p> +Kaj pa tole vprašanje? +</p> +<pre> +?- parent(thomas, X), parent(X, Y), !. +X = william, Y = vanessa ; +no. +</pre> + +<p> +Oho! Klicaj (rez) je napravil svoje. Pomislimo, kaj se je zgodilo: ko je naletel +na klicaj, je prolog zamrznil trenutno (delno) rešitev – vrednosti spremenljivk +<code>X</code> in <code>Y</code> ter ni več dovolil drugih rešitev, čeprav smo +videli, da obstajajo. To je navsezadnje njegova naloga. +</p> +<p> +Še bolj zanimiv/poučen primer: +</p> +<pre> +?- parent(thomas, X), !, parent(X, Y). +X = william, Y = vanessa ; +X = william, Y = patricia ; +no. +</pre> + +<p> +Klicaj smo sedaj postavili med oba cilja. In dobili smo… samo vnuka preko prvega +starša, torej Williama. Seveda, prolog je naletel na klicaj po tem, ko je našel +prvo rešitev za cilj <code>parent(thomas, X)</code> in je zato zamrznil rešitev +samo za spremenljivko <code>X</code>. Cilj <code>parent(X, Y)</code>, ki je +sedaj v resnici <code>parent(william, Y)</code> se izvaja normalno, v smislu, da +se generirajo (na zahtevo) vse možne rešitve za <code>Y</code>. +</p> + +<h2>Uporaba reza</h2> +<p> +Načeloma se rezu poskušamo izogibati. Seveda pa je včasih zelo koristen za +optimizacijo, ko odrežemo veje kar sami, ker vemo, da jih ne potrebujemo. +Dostikrat tudi skrajša kodo – če je to res potrebno v prologu, je veliko +vprašanje :) +</p> +<p> +Kot ste videli, rez poreže rešitve (od tu mu tudi ime). To seveda dostikrat +vpliva na prologovo „večsmernost“, ki je običajno zaželena lastnost. Rez jo +večinoma prepreči. +</p> +<p> +Glavna uporaba reza pa je pri definiciji negacije. +</p> + +<h2>Negacija v prologu</h2> +<p> +Negacija je v prologu definirana takole: poskusim dokazati, da velja cilj +(predikat) <code>P</code>. Če mi to ne uspe, potem rečem, da velja ne +<code>P</code>. Ali s primerom: +</p> +<pre> +?- parent(jeffrey, X). +no. +</pre> +<p> +Ta cilj odgovarja na vprašanje „ali je Jeffrey oče?“ Kot vidimo, prolog poskuša +to dokazati, a je odgovor „no“. Zato rečemo, da velja ravno obratno: „Jeffrey ni +oče.“ Skratka, če velja negacija v prologu, to pomeni, da prolog ni uspel +dokazati cilja, ki ga negiramo! +</p> +<p> +Natančna definicija je naslednja: +</p> +<pre> +not(P) :- + P, !, fail + ; + true. +</pre> +<p> +Kot vidiš, smo v tej definiciji uporabili rez. Preberimo logično: če velja, da +je uspel cilj <code>P</code>, potem to rešitev zamrznemo (rez!) in rečemo „no“ +– za to poskrbi cilj <code>fail</code>, ki nikoli ne uspe. +</p> +<p> +Do cilja true zaradi reza lahko pridemo samo, če <code>P</code> ne uspe in ne +naletimo na klicaj. Kar poskusi. +</p> +<p> +Še komentar o sintaksi: za negacijo lahko uporabljamo predikat <code>not</code> +(odvisno od verzije prologa), običajno pa preprosto uporabljamo operator +<code>\+</code>. Spodnje vprašanje pomeni: „ali Jeffrey ni starš?“ +</p> +<pre> +?- \+ parent(jeffrey, X). +yes. +</pre> +<p> +In še nekaj: rezultat negacije je vedno odgovor da ali ne, spremenljivkam se +vrednosti ne priredijo. Ne pozabi, da v bistvu cilj pod negacijo ne uspe. +</p> + +<h2>Primer uporabe</h2> +<p> +Sprogramirajmo predikat <code>count(X, L, N)</code>, ki prešteje koliko +elementov <code>X</code> se skriva v seznamu <code>L</code> in rezultat vrne v +<code>N</code>. +</p> +<p> +Prva, naivna implementacija je naslednja. Razmišljajmo rekurzivno. V praznem +seznamu je točno nič elementov <code>X</code>. Sicer pa imamo vsaj en element, +to je glava seznama. Pa predpostavimo, da rekurzija lepo prešteje, koliko +<code>X</code>-ov se skriva v repu (ki je krajši, torej si rekurzijo lahko +privoščimo). Sedaj pa imamo dve možnosti: ali je glava enaka <code>X</code>, ali +pa ni. V prvem primeru rezultatu rekurzije prištejemo ena, v drugem pa ne. +</p> +<pre> +count(X, [], 0). % robni pogoj: v praznem seznamu se nič ne skriva, tudi X ne ;) +count(X, [X|T], N) :- % prva možnost: glava je enaka X + count(X, T, NT), % Hej, rekurzija, koliko X-ov se skriva v repu? Aha, NT, hvala! + N is NT + 1. +count(X, [_|T], NT) :- % druga možnost: glava ni enaka X + count(X, T, NT). +</pre> +<p> +Videti je v redu, tudi logično se bere nekako smiselno. Pa poglejmo, kaj pravi +prolog. +</p> +<pre> +?- count(a, [a,b,c,a,a,b,b,a,d], N). +N = 4. +</pre> +<p> +Ha! Deluje! No no, ne tako hitro. Nismo poskusili dobiti vseh odgovorov. Zakaj +pa bi jih potrebovali, boš vprašal. Jih ne, vendar nikoli ne veš, kdaj bodo +nenadoma prišli v poštev, ko bo prolog poleg štetja počel še kaj v kombinaciji. +In navsezadnje, saj nočeš, da vračamo najprej pravilen rezultat, potem pa… +poglejmo kaj. +</p> +<pre> +?- count(a, [a,b,c,a,a,b,b,a,d], N). +N = 4 ; +N = 3 ; +N = 3 ; +N = 2 ; +… +</pre> +<p> +Hmmm. Kako, kako pa to dobimo? Hja, pomislimo. Ena možnost je, da glava enaka +<code>X</code>, druga pa, da ni enaka <code>X</code>. A tega nikoli nismo zares +povedali prologu. Druga veja je <code>count(X, [_|T], NT)</code>, ki pa pove, da +je prvi element (glava) seznama lahko karkoli. Karkoli! Torej tudi +<code>X</code>. Obe veji si torej nista disjunktni, relacija med njima je OR in +ne XOR, kot bi si želeli. Kako bi to naredili? Ena možnost je, da z rezom +preprečimo drugo vejo, kadar prva uspe. Takole. +</p> +<pre> +count(X, [], 0). % robni pogoj: v praznem seznamu se nič ne skriva, tudi X ne ;) +count(X, [X|T], N) :- !, % prva možnost: glava je enaka X + count(X, T, NT), % Hej, rekurzija, koliko X-ov se skriva v repu? Aha, NT, hvala! + N is NT + 1. +count(X, [_|T], NT) :- % druga možnost: glava ni enaka X + count(X, T, NT). +</pre> +<p> +Kot vidiš je v tem primeru rez spremenil logični pomen programa (XOR med vejama +namesto OR). Tudi zato se ga izogibamo, ker je to lahko nevarno – težje beremo +program. +</p> +<p> +Druga možnost je uporaba negacije. V drugi veji negiramo cilj, da mora glava +biti enaka <code>X</code>. +</p> +<pre> +count(X, [], 0). % robni pogoj: v praznem seznamu se nič ne skriva, tudi X ne ;) +count(X, [X|T], N) :- % prva možnost: glava je enaka X + count(X, T, NT), % Hej, rekurzija, koliko X-ov se skriva v repu? Aha, NT, hvala! + N is NT + 1. +count(X, [H|T], NT) :- % druga možnost: glava ni enaka X + \+ X = H, + count(X, T, NT). +</pre> +<p> +Seveda bi negiran cilj „<code>X</code> se ne more prilagoditi H“ lahko zapisali +z operatorjem <code>\=</code>, a smo za demonstracijo uporabili negacijo. +</p> + +<h2>Za konec</h2> +<p> +Če se da, se tudi negacije (tako kot reza) izogibamo. Ker vsebuje rez, ima enak +negativen vpliv na „večsmernost“. Seveda to vedno ne gre, zato pa jo imamo – +pravim samo, da se je izogni, če se da. Kje še lahko naletiš na probleme? V +kombinaciji negacije s spremenljivkami, ki še nimajo vrednosti. Poglej tale +primer, ki želi odgovor na vprašanje, ali ima Thomas kakšnega sina: +</p> +<pre> +?- \+ female(X), parent(thomas, X). +no. +</pre> +<p> +Kako, prosim? Prologu se je zmešalo! Saj Thomas ima kar dva sina! Ima, ima, +ampak poglejmo, kaj smo vprašali. Mislili smo povsem logično: <code>X</code> ni +ženska in je otrok od Thomasa. Vse lepo in prav. Aker je negacija definirana v +prologu kot neuspeh cilja pod negacijo, je prologovo sklepanje naslednje: ali +lahko dokažem (zadostim) cilj „<code>X</code> je ženska“? Lahko, v bazi je +veliko žensk, izberem poljubno za <code>X</code>. Zato pa je negiran cilj +seveda… napačen! Torej ne! Če bi stvari obrnili, tako da bi negiran cilj +preverjali za konkretno vrednost za <code>X</code>, bi bilo vse, kot smo si +zamislili. Takole: +</p> +<pre> +?- parent(thomas, X), \+ female(X). +X = william ; +X = jeffrey. +</pre> +<p> +Zdaj vidiš, zakaj nismo negacije uporabljali takoj od začetka. Seveda je zelo +koristna, včasih brez nje preprosto ne gre. Vendar pa je potrebno biti previden. +Če se trikov in problemov zavedaš, potem je tudi negacija povsem obvladljiva. +Seveda pa, če se da, se je je najbolje izogniti. +</p> + +</body> +</html> diff --git a/prolog/problems/sets/is_subset_2/common.py b/prolog/problems/sets/is_subset_2/common.py index 9985a9d..04daab7 100644 --- a/prolog/problems/sets/is_subset_2/common.py +++ b/prolog/problems/sets/is_subset_2/common.py @@ -5,8 +5,8 @@ import prolog.engine import server.problems id = 132 -number = 39 -visible = False +number = 60 +visible = True facts = None solution = '''\ diff --git a/prolog/problems/sets/is_superset_2/common.py b/prolog/problems/sets/is_superset_2/common.py index 7a5e373..efefd02 100644 --- a/prolog/problems/sets/is_superset_2/common.py +++ b/prolog/problems/sets/is_superset_2/common.py @@ -5,8 +5,8 @@ import prolog.engine import server.problems id = 131 -number = 38 -visible = False +number = 50 +visible = True facts = None solution = '''\ diff --git a/prolog/problems/sets/powerset_2/common.py b/prolog/problems/sets/powerset_2/common.py index 1090bfa..efcc39b 100644 --- a/prolog/problems/sets/powerset_2/common.py +++ b/prolog/problems/sets/powerset_2/common.py @@ -5,8 +5,8 @@ import prolog.engine import server.problems id = 134 -number = 41 -visible = False +number = 80 +visible = True facts = None solution = '''\ diff --git a/prolog/problems/sets/sl.py b/prolog/problems/sets/sl.py index 2d593a8..1e6a409 100644 --- a/prolog/problems/sets/sl.py +++ b/prolog/problems/sets/sl.py @@ -1,2 +1,8 @@ name = 'Množice' -description = 'Delo z množicami predstavljenimi s seznami; negacija in rez (!) v prologu.' +description = '''\ +<p> +Uporaba +<a target="_blank" href="[%@resource intro_sl.html%]">negacije in reza</a> +za implementacijo predikatov za delo z množicami. +</p> +''' diff --git a/prolog/problems/sets/subset_2/common.py b/prolog/problems/sets/subset_2/common.py index e67c4c4..33d56a2 100644 --- a/prolog/problems/sets/subset_2/common.py +++ b/prolog/problems/sets/subset_2/common.py @@ -5,8 +5,8 @@ import prolog.engine import server.problems id = 133 -number = 40 -visible = False +number = 70 +visible = True facts = None solution = '''\ diff --git a/prolog/problems/sets/union_3/common.py b/prolog/problems/sets/union_3/common.py index c955fef..f358744 100644 --- a/prolog/problems/sets/union_3/common.py +++ b/prolog/problems/sets/union_3/common.py @@ -5,8 +5,8 @@ import prolog.engine import server.problems id = 128 -number = 35 -visible = False +number = 20 +visible = True facts = None solution = '''\ |