Programiranje

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 10. 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 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.

Za oceno 8

• 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).

Za oceno 9

• 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 10

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.