summaryrefslogtreecommitdiff
path: root/prolog/problems/sorting/sins_3/sl.py
blob: 4f3920aefcb51d246addfe19e9026cbc69114daf (plain)
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
# coding=utf-8

name = 'sins/3'
slug = 'Vstavi element na ustrezno mesto v urejen seznam'

description = '''\
<p><code>sins(X, SortedList, NewList)</code>: seznam <code>NewList</code> dobiš tako, da vstaviš element <code>X</code> v <code>SortedList</code> na ustrezno mesto tako, da ohraniš urejenost elementov.</p>
<pre>
?- sins(4, [1,2,3,5], L).
  L = [1,2,3,4,5].
?- sins(3, [1,2,3,4], L).
  L = [1,2,3,3,4].
</pre>'''

plan = ['''\
<p>Za začetek se spomnimo, da vstavljamo v <em>urejen</em> seznam. Sprehodimo se po njem, dokler ne najdemo
ustreznega mesta za novi element.</p>
''', '''\
<p>Korak za korakom nov element primerjamo s trenutno glavo seznama v katerega vstavljamo. Glave bodo vedno
večje, ker je originalni seznam urejen. Kar pomeni, da bo enkrat novi element manjši od trenutne glave, kajne?</p>
''', '''\
<p>Če je nov element <code>X</code> večji od trenutne glave <code>H</code>, potem ga vstavimo nekam v rep -- za to bo,
kot vedno, poskrbela rekurzija, kajne? Sicer pa smo že našli ustrezno mesto in ga vstavimo sedaj <em>pred</em> trenutno
glavo <code>H</code>! Saj znaš pred rep postaviti dva elementa naenkrat? (Je enako, kot da bi ju vzel stran.)</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? To bo najbrž kar primer, ko (končno) vstaviš nov element v seznam.</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>
''',

    'bad_[]_case': '''\
<p>Kaj je rezultat, če vstaviš nek element v prazen seznam? Gotovo ne prazen seznam ali celo karkoli (spremenljivka
brez določene vrednosti).</p>
''',

    'returns_elem_instead_of_list': '''\
<p>Vrniti moraš <em>seznam</em>, ne element.</p>
''',

    'maxEl_base_case_missing': '''\
<p>Rešitev je skoraj pravilna. Ampak mislim, da si pozabil na en poseben primer. Kaj se zgodi, če vstavljaš v seznam
nov največji element? Poskusi spodnji klic.</p>
<p><code>?- sins(9, [1,2,3,4,5], L).</code></p>
''',

    'x_and_head_swapped': '''\
<p>Hmmm, v kakšnem vrstnem redu morata biti nov element in trenutna glava seznama?</p>
<p><code>?- sins(3, [1,2,4,5,6], L).</code></p>
''',

    'duplicates_incorrect': '''\
<p>Si pozabil, da seznam dovoljuje tudi vstavljanje duplikatov? Prvi klic spodaj deluje, drugi ne.</p>
<p><code>?- sins(3, [1,2,4,5,6], L).</code></p>
<p><code>?- sins(3, [1,2,3,4,5], L).</code></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>?- sins(3, [1,2,4,5,6], L).</code></p>
''',

    'forgotten_heads': '''\
<p>Si pozabil v seznam vrniti glave, ki si jih pred vstopom v rekurzijo dal na sklad? Tudi jaz sem jih... ;)</p>
<p>Poglej kaj se zgodi ob spodnjem vprašanju in ti bo takoj vse jasno.</p>
<p><code>?- sins(4, [1,2,3,5,6], L).</code></p>
''',
}