Specops

Rok za oddajo: sreda, 5. januar 2022, 15.00

Izkazalo se je, da Marsovci včasih tudi koga ugrabijo. V tej nalogi bomo vadili reševanje.

Najprej celotna slika: čeprav so marsovske ladje okrogle, je smrdljivi kevder, v katerega zapirajo ugrabljene, pravokotne oblike. Vsaka soba (razen robnih) ima vrata v sosednje štiri. Vrata se vsakih deset sekund odprejo za trenutek, torej prehod skozi sobo vedno traja 10 sekund. (Ugrabljenci so omamljeni, zato kljub odpiranju vrat ne morejo nikamor.)

Vsako polno uro se marsovski stražarji teleportirajo v določene sobe in prehodijo določeno poti. Vse je vedno enako. Točne podatke bomo dobili od MOSSAD-a, primer pa je na sliki.

Kje so ugrabljenci, ne vemo zagotovo, prepričani pa smo, da v eni od sob, ki jih stražarji največkrat obiščejo. Na sliki sta dve takšni sobi, (6, 4) in (4, 5); obiskani sta po trikrat.

Reševalno operacijo bodo izvedli slovenski specialci. V istem trenutku, ko se v klet teleportirajo marsovci, se bodo tudi specialci teleportirali v sobo `(0, 0)`. Vsak bo šel po predvideni poti.

  • Če specialec sreča marsovca, ga prime za ušesa (ali antene, bogve, kaj imajo) in ga zadrži v tej sobi.
  • Če v sobi hkrati naletita na marsovca dva specialca, z njim ostane tisti specialec, ki je prej v seznamu. Ker vojska in hierarhija.
  • Na koncu (ko so vsi specialci bodisi zaposleni z marsovci bodisi so končali svoje poti) morajo biti vsi marsovci prijeti, poleg tega pa mora biti po en specialec v vsaki sobi, kjer bi lahko bil ugrabljenec. Morebitni dodatni specialci so nepomembni.

Po koncu operacije teleportiramo specialce skupaj z ugrabljenci nazaj domov, pa še marsovce mimogrede ugrabimo. Zanalašč.

Primer uspešno načrtovane akcije je na sliki.

Simulacijo boste napisali za oceno 9. Za ostale ocene boste pisali funkcije, delno povezane s scenarijem; nekatere vam lahko pomagajo, nekatere morda tudi samo zato, da si znate kaj izpisati in izrisati.

Poti v nalogah so opisane v obliki "vv^^^^>>v<", pri čemer posamični znaki pomenijo premike. Kot kaže slika, koordinata y narašča v smeri v in pada v smeri ^. Poti marsovcev na sliki so torej takšne:

poti_s_slike = [
    (0, 6, ">^^>^>>vv>^>>v>"),  # rdeči
    (2, 4, ">>vv<<^"),  # zeleni
    (5, 3, ">vv<v<^<vv>>"),  # modri
    (8, 8, "^^^^<<^^<<<<<"),  # oranžni
]

Za oceno 6

  • Napiši funkcijo koraki(x, y, pot), ki prejme začetni koordinati in pot ter vrne zaporedje koordinat polj, ki jih ta, ki gre po tej poti, obišče.

    Klic koraki(10, 80, "vv>>>^<") vrne [(10, 80), (10, 81), (10, 82), (11, 82), (12, 82), (13, 82), (13, 81), (12, 81)].

  • Napiši funkcijo cilj(x, y, pot), ki vrne polje, na katerem se pot konča.

    Klic cilj(3, 6, "<<v") vrne (1, 7)

  • Napiši funkcijo cilji(opisi), ki prejme seznam terk (x, y, pot) in vrne seznam končnih lokacij.

    Klic cilji([(3, 6, "<<v"), (2, 1, "vv"), (5, 5, "")]) vrne [(1, 7), (2, 3), (5, 5)].

  • Napiši funkcijo obiskana(x, y, pot), ki vrne množico vseh obiskanih polj.

    Klic obiskana(4, 4, "^^>vv<<") vrne {(4, 4), (4, 3), (4, 2), (5, 2), (5, 3), (5, 4), (3, 4)}.

  • Napiši funkcijo najveckrat_obiskana(opisi), ki prejme podobne argumente kot cilji in vrne množico največkrat obiskanih polj. Če isti stražar obišče isto polje večkrat, se to šteje za več obiskov.

    Klic najveckrat_obiskana(poti_s_slike), kjer so poti_s_slike poti s slike, vrne {(4, 5), (6, 4)}.

Ocena 7

Specialce označimo z velikimi črkami angleške abecede (A, B, C, D, E, F, G, H, I, J) in marsovce z malimi. Tako enih kot drugih je največ deset.

  • Napiši funkcijo situacija(specialci, marsovci, sirina, visina), ki prejme seznam koordinat specialcev, seznam koordinat marsovcev. Vrniti mora seznam seznamov množic ter širino in višino zemljevida. Če se seznam recimo imenuje s, bo s[y][x] množica vseh, ki se nahajajo v sobi s koordinatama (x, y).

    Klic

    situacija([(1, 0), (0, 2), (3, 1), (0, 2)],
          [(2, 2), (3, 1), (3, 1), (1, 1)], 4, 3)

    vrne

    [[set(),       {'A'},  set(),     set()          ],
 [set(),       {'d'},  set(),     {'C', 'c', 'b'}],
 [{'D', 'B'},  set(),  {'a'},     set()          ]]

  • Funkcija znak(m) prejme množico črk.

    • Če je množica prazna, funkcija vrne ".".
    • Če vsebuje en element, vrne ta element.
    • Če vsebuje več kot en element, vrne niz s številom elementov. Če je velikost množice 3, vrne "3". Predpostaviti smeš, da velikost ne bo večja od 9.

  • Funkcija izris(polozaj) prejme seznam seznamov množic, kakršnega vrne funkcija situacija in vrne niz z izpisom v naslednji obliki:

    .A..
.d.3
2.a.

    Dejanski niz, ki ga vrne funkcija, je seveda, ".A..\n.d.3\n2.a.", tole zgoraj je že njegov izpis.

  • Funkcija animacija0(x, y, pot, sirina, visina) prejme začetne koordinate in pot ter vrne seznam nizov, ki predstavljajo situacije v posameznih časovnih korakih. Akter je predstavljen z znakom A (kot da gre za specialca). Parametra sirina in visina vsebujeta dimenzija kleti.

    Klic animacija0(1, 1, "<^>>", 3, 3) vrne ['...\n.A.\n...', '...\nA..\n...', 'A..\n...\n...', '.A.\n...\n...', '..A\n...\n...'].

Za oceno 8

  • Funkcija dopolnjeno(s, n) prejme seznam s. Vrniti mora nov seznam dolžine n (pri čemer je n večji ali enak len(s)). Vrnjeni seznam vsebuje vse elemente s, ki jim sledi toliko ponovitev zadnjega elementa s, da je skupna dolžina enaka zahtevani, n.

    Klic dopolnjeno(["Ana", "Berta", "Cilka"], 5) vrne ["Ana", "Berta", "Cilka", "Cilka", "Cilka"].

  • Funkcija razporedi(specialci, marsovci) prejme dva seznama, enega za specialce enega za marsovce. Vsak seznam je sestavljen iz trojk (x, y, pot), ki opisuje gibanje enega od specialcev ali marsovcev. Funkcija vrne dva seznama enakih dolžin: njuna dolžina ustreza najdaljši poti, ki jo naredi katerikoli izmed specialcev ali marsovcev. Vsak element seznama ustreza eni časovni točki in vsebuje koordinate vseh specialcev oz. marsovcev v podanem trenutku.

    Za ilustracijo poglejmo klic

    razporedi([(0, 2, ">>>"), (3, 3, "<v"), (4, 2, "")],
          [(1, 2, "^^<>>"), (1, 1, ">>")])

    Vrniti mora

    ([[(0, 2), (3, 3), (4, 2)],
  [(1, 2), (2, 3), (4, 2)],
  [(2, 2), (2, 4), (4, 2)],
  [(3, 2), (2, 4), (4, 2)],
  [(3, 2), (2, 4), (4, 2)],
  [(3, 2), (2, 4), (4, 2)]],
 [[(1, 2), (1, 1)],
  [(1, 1), (2, 1)],
  [(1, 0), (3, 1)],
  [(0, 0), (3, 1)],
  [(1, 0), (3, 1)],
  [(2, 0), (3, 1)]])

    Najprej opazujmo prvi seznam iz para. Njegov prvi element vsebuje začetne položaje vseh specialcev, [(0, 2), (3, 3), (4, 2)]. Naslednji element vsebuje položaje specialcev po prvem koraku, [(1, 2), (2, 3), (4, 2)]: prvi se je premaknil desno, drugi levo, tretji nikamor, saj je njegova pot prazna. Tretji element vsebuje koordinate po drugem koraku in četrti element po tretjem. Peti in šesti element sta potem enaka četrtemu, saj se specialci premaknejo le trikrat (in še to le prvi); v zadnjih treh korakih se premikajo samo še marsovci.

    Drugi seznam iz para vsebuje enake podatke za marsovce.

  • Funkcija animacija(specialci, marsovci, sirina, visina) prejme enake argumente kot razporedi, poleg tega pa še dimenzije kleti. Funkcija vrne animacijo v podobni obliki kot animacija0, vendar za vse specialce in marsovce.

    Klic


    animacija([(0, 2, ">>>"), (3, 3, "<v"), (4, 2, "")],
          [(1, 2, "^^<>>"), (1, 1, ">>")], 5, 5)

    vrne seznam, ki vsebuje naslednje nize

    .....
.b...
Aa..C
...B.
.....

    .....
.ab..
.A..C
..B..
.....

    .a...
...b.
..A.C
.....
..B..

    a....
...b.
...AC
.....
..B..

    .a...
...b.
...AC
.....
..B..

    ..a..
...b.
...AC
.....
..B..

  • prvo_srecanje(specialec, marsovec) prejme dve trojki z začetnima koordinatama in potjo specialca in marsovca. Vrniti mora prvo polje, na katerem se srečata. Če se ne srečata nikoli, vrne None.

    Klic prvo_srecanje((2, 1, ">>"), (1, 1, ">>>>>>")) vrne (4, 1): specialec se premika pred marsovcev, potem pa ga pričaka v zasedi v (4, 1).

  • bingo(specialci, marsovec) prejme podobne argumente kot prejšnja funkcija, le da namesto opisa enega specialca prejme opise več specialcev. Funkcija vrne koordinate polja, kjer bo nek specialec ujel marsovca, oziroma None, če se bo mali zeleni izmaknil.

    Klic

    bingo([(8, 12, ">>>>>>>>"), (10, 14, ">>>>>>>>"), (9, 13, ">>>>>>>>")],
      (12, 16, "^>^>^>^>^>"))

    vrne (13, 14): marsovec bo po treh korakih na (13, 14) in ravno takrat se bo tam znašel specialec, ki začne na (10, 14) in se pomika desno.

Ocena 9

Napiši funkcijo simulacija(specialci, marsovci), ki prejme seznam poti specialcev (le nize, saj vsi specialci začnejo na (0, 0)!) in sezname s trojkami, ki opisujejo gibanje marsovcev. Vrniti mora True, če je reševalna akcija uspešna in False, če ni. Kako poteka akcija in kdaj je uspešna, je opisano v uvodu.

Ocena 10

Napiši funkcijo strategija(marsovci), ki vrne optimalno strategijo operacije. Argument so poti marsovcev. Rezultat mora biti seznam poti vseh specialcev.

  • Operacija mora biti uspešna.
  • Vsakega marsovca je potrebno zgrabiti čimprej. (Ideja: za vsakega marsovca je zadolžen en specialec in ta ga mora zgrabiti, čim je mogoče.)
  • Tudi do vseh ugrabljenih je potrebno priti čimprej.
  • Specialcev naj bo le toliko, kot jih potrebujemo.
  • Poti specialcev naj nimajo nepotrebnih repov. Pri prejšnji nalogi smo ignorirali morebitno predvideno pot specialca po tem, ko sreča marsovca in obstani z njim; v strategiji, ki jo vrne ta funkcija, naj odvečnih repov ne bo.

Testi bodo uporabljali vašo funkcijo simulacija, zato mora biti ta pravilno napisana. Ko bomo testirali vašo strategijo, pa bomo zamenjali simulacijo s svojo. Lahko se vam torej zgodi, da bodo testi poročali, da je naloga uspešno rešena za oceno 10, v resnici pa boste dobili oceno 9. (Taki situaciji se poskuašmo izogniti, a resnici na ljubo pri večini predmetov pravzaprav nikoli ob oddaji izdelka ne veste, ali je vaša rešitev res pravilna in kakšno oceno boste dobili.)