Dol z Marsovci!

Odprto: sobota, 27. november 2021, 00.00
Rok za oddajo: sreda, 8. december 2021, 15.00

Marsovci še kar najedajo. Zdaj so se parkirali pred Zemljo in imajo očitno slabe namene. Na srečo je Slovenska vojska pripravljena na vse: na strateških mestih ima parkirane ČNVL-je (Čisto nevidne vesoljske ladje), ki bodo uničile marsovsko floto. Manjka jim le še strateški načrt. Ta je predmet te domače naloge.

Za razumevanje naloge si najprej oglejte animacijo. Marsovske ladje so predstavljene s krogci, hrabri ČNVL pa s kvadratki.

Za oceno 6

  • Napiši funkcijo razdalja(x, y), ki prejme terki s koordinatami dveh točk in vrne evklidsko razdaljo med njimi. Da bomo pripravljeni tudi na transdimenzionalna bitja, je dimenzija točk lahko poljubna (od 1 do kolikor je treba). Razdaljo v večdimenzionalnem prostoru računamo podobno kot v dvo- ali tridimenzionalnem

    $$d(x, y) = \sqrt{\sum_{i=0}^{n-1}(x_i - y_i)^2}$$

    • Klic razdalja((5, 12), (2, 16)) vrne 5 (to je, $\sqrt{(5 - 2)^2 + (12 - 16)^2} = \sqrt{3^2 + 4^2}$).
    • Klic razdalja((5, ), (8, ) (razdalja na premici) vrne 3 (to je $\sqrt{(5 - 8)^2}$).
    • Klic razdalja((1, 7, 4, 2, 6, -7, 4), (-1, 10, 5, 2, 6, -8, 3) (razdalja v 7-dimenzionalnem prostoru) vrne 4.

  • Napiši funkcijo najblizja(marsovec, ladje), ki dobi terko s koordinatami marsovske ladje in seznam terk s položaji naših ladij, ČNVL-jev. Vrniti mora koordinate najbližjega ČNVL-a. (Ta bo zadolžen za napad na to marsovsko ladjo.)

    • Klic najblizja((1, 1), [(0, 0), (5, 2), (-8, 3)] vrne (0, 0), saj je marsovski ladji na koordinatah (1, 1) najbližji ČNVL na koordinatah (0, 0).
    • Klic najblizja((-7, 2, 5, 1), [(0, 0, 5, 2), (5, 2, 5, 2), (-8, 3, 5, 2)]) vrne (-8, 3, 5, 2).

  • Napiši funkcijo dodeli_ladje(marsovci, ladje), ki prejme seznam marsovskih in naših ladij. Vrniti mora seznam terk, ki je enako dolg kot seznam marsovci: i-ti element rezultata vsebuje koordinate ČNVL-ja, ki je najbližji i-ti marsovski ladji.

    • Klic dodeli_ladje([(1, 1), (0, 0), (-7, 2), (5, 1)], [(0, 0), (5, 2), (-8, 3)]) vrne [(0, 0), (0, 0), (-8, 3), (5, 2)], saj je prvima dvema marsovcema najbližji ČNVL na koordinatah (0, 0), tretjemu ČNVL na (-8, 3), četrtemu pa tisti na (5, 2).

  • Napiši funkcijo skupine_marsovcev(marsovci, ladje), ki vrne seznam množic terk s koordinatami marsovskih ladij. Bistvo te funkcije je grupiranje marsovskih ladij. Če bodo marsovske ladje uničevali trije ČNVL-ji, se vsaka množica nanaša na enega od njih in vsebuje tiste marsovske ladje, ki jih bo uničil ta, pripadajoči ČNVL.

    Vrstni red množic (skupin) je lahko poljuben.

    Klic

    skupine_marsovcev(
    [(0, 1), (2, 2), (51, 52), (100, 100),
     (1, 3), (4, 5), (45, 50), (103, 98)],

    [(0, 0), (50, 50), (100, 100)]))

    vrne

    [{(0, 1), (2, 2), (1, 3), (4, 5)},
 {(100, 100), (103, 98)},
 {(51, 52), (45, 50)}]

    Prva množica vsebuje koordinate marsovskih ladij, ki jih uniči NČVL na koordinatah (0, 0), druga ladje, ki jih uniči ČNVL na koordinatah (100, 100) in tretja tiste, ki jih uniči (50, 50).

    Funkcija v bistvu vrne množice koordinat marsovskih ladij, ki so iste barve.

    Namig: čeprav ni videti tako, ti bodo tu prišli prav slovarji.

Za oceno 7

  • Napiši funkcijo sredisce(s), ki prejme seznam koordinat točk in vrne terko s koordinatami njihovega središča. Koordinate te točke so izračunane kot poprečne koordinate točk v s po vsaki dimenziji posebej.

    Število točk v s je poljubno. Točke so poljubno-dimenzionalne.

    • Klic sredisce([(2, 8), (6, 10) vrne (4, 9).

  • Napiši funkcij razpostavi_ladje(skupine), ki poišče optimalno razpostavitev ladij. Funkcija prejme neko razdelitev marsovskih ladij v skupine; argument je v enaki obliki kot rezultat funkcije skupine_marsovcev. Funkcija mora vrniti seznam koordinat središč skupin.

    • Klic
    razpostavi_ladje([{(0, 1), (2, 2), (1, 3), (4, 5)},
                  {(100, 101), (103, 98)},
                  {(51, 52), (45, 50)}])

    vrne seznam, ki vsebuje

    [((0 + 2 + 1 + 4) / 4, (1 + 2 + 3 + 5) / 4),
 ((100 + 103) / 2, (101 + 98) / 2),
 ((51 + 45) / 2, (52 + 50) / 2)]

Za oceno 8

  • Napiši funkcijo optimiraj_ladje(marsovci, ladje), ki prejme položaje marsovcev in neko začetno pozicijo naših ladij. Funkcija naj izmenično ponavlja naslednja koraka:

    • določi skupine, ki pripadajo posamezni ladji, ko to počne funkcija skupine_marsovcev;
    • na podlagi teh skupin, naj izračuna boljše položaje ladij, se pravi, prestavi vsako ladjo v središče skupine, ki ji je dodeljena;
    • ker so se ladje premaknile, naj izračuna novo dodelitev marsovcev;
    • ker to spremeni skupine, naj premakne ladje v nova središča skupin;
    • ker so se ladje premaknile ...

    Prej ko slej se bodo ladje nehale premikati in skupine nehale spreminjati. Takrat naj se postopek ustavi. Funkcija naj vrne končne koordinate ladij.

    Funkcija v bistvu izvaja optimizacijo, ki jo kaže video. Video, konkretno, predstavlja štiri klice funkcije.

    Za pomoč je v testu za oceno 9 shranjen potek položajev ladij v zadnjem testu. Če ga funkcija izpisuje, mora biti (do določenega števila decimalnih mest) enak.

Za oceno 9

  • Za čim večjo učinkovitost napada morajo biti razdalje med ČNVL in marsovci čim manjše. Napiši funkcijo kvaliteta(marsovci, ladje), ki prejme seznam položajev marsovskih ladij in množico položajev ČNVL-jev. Vrne naj vsoto vseh razdalij med marsovskimi ladjami in najbližjim ČNVLjem za vsako ladjo. Z drugimi besedami, vrne skupno dolžino črt na sliki.

  • Napiši funkcijo nakljucna(marsovci, ladij), ki vrne nek naključen razpored podanega števila ladij. Funkcija mora vrniti seznam, ki vsebuje ladij terk koordinat. Koordinate so izžrebane iz koordinat marsovskih ladij. Za i-to koordinato izberemo koordinato i neke naključne marsovske ladje.

    Klic

    nakljucna([(5, 8),
           (2, 17),
           (1, 33),
           (4, 9)], 3)

    bi lahko vrnil, recimo [(1, 8), (4, 17), (2, 8)]. Vsaka prva koordinata je žrebana iz prvih koordinata in druga iz drugih.

Za oceno 10

  • Napiši funkcijo optimiraj_ladje_2(marsovci, ladje), ki je enaka funkciji optimiraj_ladje, le da namesto pozicij vrne par (kvaliteta, pozicije), pri čemer je kvaliteta izračunana s funkcijo za oceno 9.

  • Recimo, da začnemo optimizacijo z nekim naključnim položajem. Kot vidimo iz tretjega primera v videu, se lahko včasih zgodi, da imamo smolo in končamo s kakim slabim končnim razporedom. Napiši funkcijo planiraj(marsovci, ladij), ki si stokrat izmisli nek naključen razpored (s funkcijo nakljucni) in izvede celoten postopek optimiranja za podano število ladij. Dobivala bo različno kvalitetne razporede. Vrniti mora najboljši končni razpored, na katerega je naletela.

O testih

V testih so funkcije že zastavljene: imajo nekaj dokumentacije v enem od običajnih oblik, poleg tega pa so označeni tipi argumentov in rezultatov. Če tega ne razumeš, ignoriraj. Če razumeš, ti lahko služi kot dodatna dokumentacija.

Ker je vrstni red elementov seznamov, ki jih vračajo tvoje funkcije včasih poljuben, bodo testne funkcije včasih uredile rezultat tvoje funkcije in ga primerjale z urejenim pričakovanim rezultatom. Naj te to ne zmede: funkciji ni potrebno ničesar urejati.

Če tvoja funkcija vrača seznam, kjer testi pričakujejo terko, se bodo (najbrž) pritožili. Bodi pozoren na oklepaje v izpisu.

(3) ni terka temveč samo 3 v oklepaju. (3, ) je terka.

Če test pričakuje, da bo funkcija vrnila [(4 + 6) / 2, (3 + 9) / 3], seveda pričakuje [5, 4]. V tej obliki je zapisano le, da lažje razberemo, kaj mora funkcija računati.

Test zadnje funkcije deluje tako, da razpostavi naključne množice s po 20 točkami v bližini treh vnaprej izbranih točk. Nato izračuna središče vsake od teh množic. Te točke predstavljajo skupine marsovcev, ki jih mora odkriti funkcija. Pričakovati je, da bo v 100 poskusih gotovo vsaj enkrat (najbrž pa 90-krat) našla pravi razpored.

Testi