1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
|
# coding=utf-8
name = 'pivoting/4'
slug = 'Razdeli seznam na dva dela glede na podani element (pivot)'
description = '''\
<p><code>pivoting(P, L, S, G)</code>: seznam <code>S</code> vsebuje elemente iz <code>L</code> <em>manjše ali enake</em> <code>P</code>, seznam <code>G</code> pa elemente iz <code>L</code> <em>večje od</em> <code>P</code>. Vrstni red elementov v <code>S</code> in <code>G</code> naj bo enak kot v <code>L</code>.</p>
<pre>
?- pivoting(4, [1,4,5,8,6,4,2], S, G).
S = [1,4,4,2], G = [5,8,6].
</pre>'''
plan = ['''\
<p>Precej klasična rekurzivna rešitev, za glavo seznama poskrbiš ti sam, za rep pa poskrbi rekurzija. Sta pa dve veji,
seveda, ker je glava seznama lahko večja ali manjša od pivota.</p>
''', '''\
<p>Sprehodi se po seznamu in trenutno glavo <em>ob sestopanju</em> iz rekurzije vrži ali v seznam z večjimi ali
pa v seznam z manjšimi elementi.</p>
''', '''\
<p>Če je glava <code>H</code> seznama <code>L</code> manjša ali enaka pivotu <code>P</code> in če predpostavimo, da
rekurzija vrne pravilno razdeljene elemenente repa <code>T</code> med seznama <code>SmallerElems</code> in
<code>GreaterElems</code> in če vstavimo <code>H</code> na začetek seznama <code>SmallerElems</code>, potem smo
pravilno razdelili vse elemente seznama <code>L</code> na manjše in večje. Podobno velja za drugo možnost, ko je
glava seznama <code>H</code> večja od pivota <code>P</code>.</p>
''']
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).</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 (<code>=</code>)?</p>
''',
'base_case': '''\
<p>Si pomislil na robni pogoj? Kateri seznam lahko razdelim praktično brez dela?</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> <em>hkrati</em> večji in manjši od <code>Y</code> ali kaj podobno logično sumljivega).</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>
''',
'>_and_<_mixed_up': '''\
<p>Si zamešal pogoja? V seznamu manjših elementov so pristali večji in obratno. Tudi meni je to uspelo! ;)</p>
<p><code>?- pivoting(4, [1,4,5,8,6,4,2], SmallerElems, GreaterElems).</code></p>
''',
'duplicates_not_considered': '''\
<p>Si pozabil, da je lahko kakšen element v seznamu tudi enak pivotu? Kam ga daš v tem primeru? Ta hip nikamor,
zato je prologov vesel (in žal logičen) odgovor seveda... da, uganil si, "false"!</p>
''',
'all_elements_in_either_S_or_G': '''\
<p>Kako to, da prav <em>vsi</em> elementi seznama pristanejo ali med večjimi ali med manjšimi elementi?
Napačen pogoj ali morda copy/paste napaka?</p>
''',
'arbitrary_solution': '''\
<p>To je pa zlobna napaka. Za en seznam, ki ga vračaš, si lepo poskrbel, za drugega pa nisi. Če recimo glavo
<code>H</code> vstaviš v seznam manjših elementov <code>[H|SmallerElems]</code> je to v redu, a ne pozabi povedati
še kaj je s seznamom večjih elementov (pa četudi je povsem enak kot ga vrne rekurzija).</p>
''',
'unprotected_branch': '''\
<p>Si "zaščitil" (s pogojem) obe možnosti (veji)? Pazi, če ena nima pogoja, bo prva rešitev verjetno pravilna, vendar
pa bodo možne še druge rešitve, ki ne bodo. Podpičje pomeni logični OR in ne logični XOR. Kar pomeni, da lahko prolog
poišče alternative v drugi veji, čeprav je pogoj v prvi veji izpolnjen! Zato sta potrebna oba pogoja.</p>
<p>Poskusi spodnje vprašanje in zahtevaj <em>več</em> rešitev.</p>
<p><code>?- pivoting(4, [1,4,5,8,6,4,2], SmallerElems, GreaterElems).</code></p>
''',
'forcing_result_onto_recursion': '''
<p>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.</p>
<p>Je tvoj rekurzivni klic oblike <code>pivoting(P, T, [H|SmallerElems], GreaterElems)</code>? S tem vsiljuješ rekurziji
da mora <emph>vrniti</emph> tudi glavo <code>H</code>, ki je sploh ne pozna, ker si jo ravnokar vzel stran! To moraš
narediti ti z rezultatom, ki ti ga rekurzija vrne. Skratka, element <code>H</code> vstavi izven rekurzivnega klica.</p>
''',
'no_recursion_in_one_branch': '''\
<p>To je precej tipična napaka pri uporabi podpičja. Preberi vsak ALI blok zase! Se ti ne zdi, da si v enem bloku,
največkrat drugem, pozabil nekaj? Morda rekurzijo? Ne pozabi: oba bloka sta med seboj neodvisna! Ali se izvede eno
ali pa drugo, ne bo se nikoli oboje hkrati! In rezultati se med vejami ne prenašajo, spomni se na doseg spremenljivk
v prologu.</p>
''',
}
|
