P1 2021/22 - 10 Specops - Aljaz S.¶
from typing import Dict, Set, Tuple, List
from collections import defaultdict
from functools import reduce
from itertools import count
from math import floor
Tocka = Tuple[int, int]
Opis = Tuple[int, int, str]
Opisi = List[Opis]
def room2Room(x: int, y: int, simbol):
match simbol:
case "^": return (x, y - 1)
case "v": return (x, y + 1)
case ">": return (x + 1, y)
case "<": return (x - 1, y)
def koraki(x: int, y: int, pot: str) -> List[Tocka]:
"""
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)].
"""
koraki_ = [(x, y)]
for korak in pot:
koraki_.append(room2Room(*koraki_[-1], korak))
return koraki_
def cilj(x: int, y: int, pot: str) -> Tocka:
"""
Napiši funkcijo cilj(x, y, pot), ki vrne polje, na
katerem se pot konča.
Klic cilj(3, 6, "<<v") vrne (1, 7)
"""
return koraki(x, y, pot)[-1]
def cilji(opisi: Opisi) -> List[Tocka]:
"""
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)].
"""
return [cilj(*opis) for opis in opisi]
def obiskana(x: int, y: int, pot: str) -> Set[Tocka]:
"""
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)}.
"""
return set(koraki(x, y, pot))
def najveckrat_obiskana(opisi) -> Set[Tocka]:
"""
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)}.
"""
obiskane = reduce(lambda x, y: x+y, [ koraki(*opis) for opis in opisi ])
obiskanost = defaultdict(lambda: 0)
for soba in obiskane:
obiskanost[soba] += 1
naj_obiskanost = max(obiskanost.values())
return set(soba for soba in obiskane if obiskanost[soba] == naj_obiskanost)
def situacija(specialci: List[Tocka], marsovci: List[Tocka], sirina: int, visina: int) -> List[List[Set[Tocka]]]:
"""
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() ]]
"""
final = [ [ set() for _ in range(sirina) ] for _ in range(visina) ]
for i, (x, y) in zip("ABCDEFGHIJ", specialci):
final[y][x].add(i)
for i, (x, y) in zip("abcdefghij", marsovci):
final[y][x].add(i)
return final
def znak(m: Set[Tocka]) -> str:
"""
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.
"""
match len(m):
case 0: return "."
case 1: return next(iter(m))
case _: return str(len(m))
def izris(polozaj: List[List[Set[Tocka]]]) -> str:
"""
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.
"""
return "\n".join([ "".join([ znak(x) for x in y ]) for y in polozaj ])
def animacija0(x: int, y: int, pot: str, sirina: int, visina: int) -> List[str]:
"""
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...'].
"""
return [ izris(situacija([ tocka ], [], sirina, visina)) for tocka in koraki(x, y, pot) ]
def dopolnjeno(s: List[str], n: int) -> List[str]:
"""
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"].
"""
return [ s[i] if i < len(s) else s[-1] for i in range(n) ]
def razporedi(specialci: Opisi, marsovci: Opisi) -> Tuple[List[List[Tocka]], List[List[Tocka]]]:
"""
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.
"""
maxpot_ = 1 + max([ len(pot) for _, _, pot in specialci + marsovci], default=0)
return (
[ list(x) for x in zip(*[dopolnjeno(koraki(*x), maxpot_) for x in specialci]) ],
[ list(x) for x in zip(*[dopolnjeno(koraki(*x), maxpot_) for x in marsovci]) ]
)
def animacija(specialci: Opisi, marsovci: Opisi, sirina: int, visina: int) -> List[str]:
"""
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.
"""
return [ izris(situacija(spec_, mars_, sirina, visina)) for spec_, mars_ in zip(*razporedi(specialci, marsovci)) ]
def prvo_srecanje(specialec: Opis, marsovec: Opis) -> Tocka | None:
"""
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).
"""
maxpath_ = 1 + max(len(specialec[2]), len(marsovec[2]))
for t1, t2 in zip(dopolnjeno(koraki(*specialec), maxpath_), dopolnjeno(koraki(*marsovec), maxpath_)):
if t1 == t2: return t1
else: return None
def bingo(specialci: Opisi, marsovec: Opis) -> Tocka | None:
"""
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.
"""
# pridobi prva srecanja
prva_srecanja = { prvo_srecanje(specialec, marsovec) for specialec in specialci }
# pojdi po marsovcovih korak in pridobi prvega kjer se sreca s specialcem
for korak in koraki(*marsovec):
if korak in prva_srecanja:
return korak
else:
return None
def simulacija(specialci: List[str], marsovci: Opisi) -> True | False:
"""
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.
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šč.
"""
specialci = [ (0, 0, pot) for pot in specialci ]
koraki_specialci, koraki_marsovci = razporedi(specialci, marsovci)
ujetniki = najveckrat_obiskana(marsovci)
# Ce je specialcev manj kot ujetnikov ter marsovcev skupaj,
# je misija spodletela ze preden se je zacela
if (len(specialci) < len(marsovci) + len(ujetniki)):
return False
# Vsi ujetniki morajo v koncni fazi imeti vsaj enega specialca, ki ni zaseden z marsovcem,
# v svoji sobi
for ujetnik in ujetniki:
specialcev = len([ True for x in koraki_specialci[-1] if x == ujetnik ])
marsovcev = len([ True for x in koraki_marsovci[-1] if x == ujetnik ])
# Ce je v sobi, kjer se nahaja ujetnik, premalo specialcev, misija spodleti
# Npr. v sobi imamo:
# - enega ujetnika, enega marsovca ter enega specialca - misija spodleti
# - enega ujetnika, enega marsovca ter dva specialca - misija je uspesna
# - enega ujetnika, nic marsovcev ter enega specialca - misija je uspela
if (specialcev < marsovcev + 1):
return False
# # Sestavimo dict z entitetami
# # entitete: Dict[str | int, Dict[ ]] = dict()
# for s_koraki, naziv in zip([ koraki(0, 0, s) for s in specialci], "ABCDEFGHIJKLMNOPR"):
# entitete[naziv] = dict({ "koraki": s_koraki[1:], "pozicija": s_koraki[0], "tip": "s" })
# for m_koraki, naziv in zip([ koraki(*m) for m in marsovci ], "abcdefghijklmnopr"):
# entitete[naziv] = dict({ "koraki": m_koraki[1:], "pozicija": m_koraki[0], "tip": "m" })
# for pozicija, naziv in zip(ujetniki, count()):
# entitete[naziv] = dict({ "koraki": [], "pozicija": pozicija, "tip": "u" })
# while [ True for x in entitete.keys() if len(entitete[x]["koraki"]) > 0 ]:
# dolzina lajdaljse poti
# Pobrano iz funkcije razporedi
najdaljsa_pot = 1 + max([ len(pot) for _, _, pot in specialci + marsovci], default=0)
poti_spec = [ dopolnjeno(koraki(*x), najdaljsa_pot) for x in specialci ]
poti_mars = [ dopolnjeno(koraki(*x), najdaljsa_pot) for x in marsovci ]
for korak in range(najdaljsa_pot):
odstrani_specialce = []
for spec_pot in poti_spec:
for mars_pot in poti_mars:
if spec_pot[korak] == mars_pot[korak] and mars_pot in poti_mars:
odstrani_specialce.append(spec_pot)
poti_mars.remove(mars_pot)
continue
# odstani specialce, ki so zasedeni z marsovcem
for specialec in odstrani_specialce:
poti_spec.remove(specialec)
# odstrani ujetnike, ki imajo dodeljena specialca
for spec_pot in poti_spec:
if spec_pot[-1] in ujetniki:
ujetniki.remove(spec_pot[-1])
return not ujetniki and not poti_mars
# def strat_najhitrejse_srecanje(spec_zacetek: Tocka, marsovec: List[Tocka]) -> List[Tocka]:
# for t in range(len(marsovec)):
# tocka = marsovec[t]
# dist = abs(tocka[0] - spec_zacetek[0]) + abs(tocka[1] - spec_zacetek[1])
# if (t == dist or t - 1 == dist):
# return tocka
# def strategija(marsovci: Opisi) -> List[str]:
# """
# 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.)
# """
# ujetniki = najveckrat_obiskana(marsovci)
# stevilo_specialcev = len(ujetniki) + len(marsovci)
# tocke_specialcev = [ [] for _ in range(stevilo_specialcev) ]
# poti_marsovcev = [ koraki(*x) for x in marsovci ]
import unittest
poti_s_slike = [
(0, 6, ">^^>^>>vv>^>>v>"), # rdeči
(2, 4, ">>vv<<^"), # zeleni
(5, 3, ">vv<v<^<vv>>"), # modri
(8, 8, "^^^^<<^^<<<<<"), # oranžni
]
class Test06(unittest.TestCase):
def test_01_koraki(self):
self.assertEqual(
[(0, 6), (1, 6), (1, 5), (1, 4), (2, 4), (2, 3), (3, 3), (4, 3),
(4, 4), (4, 5), (5, 5), (5, 4), (6, 4), (7, 4), (7, 5), (8, 5)],
koraki(*poti_s_slike[0])) # rdeča pot
self.assertEqual(
[(2, 4), (3, 4), (4, 4), (4, 5), (4, 6), (3, 6), (2, 6), (2, 5)],
koraki(*poti_s_slike[1])) # zelena pot
self.assertEqual(
[(5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (5, 6), (4, 6), (4, 5),
(3, 5), (3, 6), (3, 7), (4, 7), (5, 7)],
koraki(*poti_s_slike[2])) # modra pot
self.assertEqual(
[(8, 8), (8, 7), (8, 6), (8, 5), (8, 4), (7, 4), (6, 4),
(6, 3), (6, 2), (5, 2), (4, 2), (3, 2), (2, 2), (1, 2)],
koraki(*poti_s_slike[3])) # oranzna pot
self.assertEqual(
[(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (3, 2), (3, 1),
(2, 1), (3, 1), (3, 2), (3, 3), (3, 2), (2, 2)],
koraki(0, 0, "vv>>>^<>vv^<"))
self.assertEqual(
[(10, 80), (10, 81), (10, 82), (11, 82), (12, 82), (13, 82),
(13, 81), (12, 81), (13, 81), (13, 82), (13, 83), (13, 82),
(12, 82)],
koraki(10, 80, "vv>>>^<>vv^<"))
self.assertEqual([(4, 8)], koraki(4, 8, ""))
def test_02_cilj(self):
self.assertEqual((8, 5), cilj(*poti_s_slike[0]))
self.assertEqual((2, 5), cilj(*poti_s_slike[1]))
self.assertEqual((5, 7), cilj(*poti_s_slike[2]))
self.assertEqual((1, 2), cilj(*poti_s_slike[3]))
self.assertEqual((2, 2), cilj(0, 0, "vv>>>^<>vv^<"))
self.assertEqual((12, 82), cilj(10, 80, "vv>>>^<>vv^<"))
self.assertEqual((4, 8), cilj(4, 8, ""))
def test_03_cilji(self):
self.assertEqual([(8, 5), (2, 5), (5, 7), (1, 2)], cilji(poti_s_slike))
self.assertEqual(
[(2, 2), (12, 82), (4, 8)],
cilji([(0, 0, "vv>>>^<>vv^<"),
(10, 80, "vv>>>^<>vv^<"),
(4, 8, "")]))
self.assertEqual(
[(1, 7), (2, 3), (5, 5)],
cilji([(3, 6, "<<v"), (2, 1, "vv"), (5, 5, "")]))
def test_04_obiskana(self):
self.assertEqual(
{(4, 4), (4, 3), (4, 2), (5, 2), (5, 3), (5, 4), (3, 4)},
obiskana(4, 4, "^^>vv<<")
)
self.assertEqual(
{(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (3, 2), (3, 1),
(2, 1), (3, 1), (3, 3)},
obiskana(0, 0, "vv>>>^<>vv^<")
)
def test_05_najveckrat_obiskana(self):
self.assertEqual(
{(2, 2)},
najveckrat_obiskana([(0, 0, "vv>>>^<>vv^<"),
(2, 2, "^"),
(1, 1, "v>^")]))
self.assertEqual(
{(3, 2)},
najveckrat_obiskana([(0, 0, "vv>>>^<>vv^<"),
(1, 1, "v>^"),
(3, 2, "")]))
self.assertEqual(
{(0, 0), (1, 0), (2, 0), (3, 0)},
najveckrat_obiskana([(0, 0, ">>>"), (0, 0, ">>>"), (0, 0, ">>>"), (0, 0, ">>>>")]))
self.assertEqual(
{(2, 0)},
najveckrat_obiskana([(0, 0, ">>>"), (0, 0, ">>>"), (0, 0, ">>>"), (0, 0, ">>><")]))
self.assertEqual({(4, 5), (6, 4)}, najveckrat_obiskana(poti_s_slike))
def strip_ani(s):
return ["".join(v.rstrip(" ") for v in x.strip()) for x in s]
class Test07(unittest.TestCase):
def test_01_situacija(self):
e = set()
self.assertEqual([[e, e, e, e], [e, e, e, e]], situacija([], [], 4, 2))
self.assertEqual([[e, {"a"}, e, e], [{"A"}, e, e, e]],
situacija([(0, 1)], [(1, 0)], 4, 2))
self.assertEqual(
[[e, {'A'}, e, e],
[e, {'d'}, e, {'C', 'c', 'b'}],
[{'D', 'B'}, e, {'a'}, e]],
situacija([(1, 0), (0, 2), (3, 1), (0, 2)],
[(2, 2), (3, 1), (3, 1), (1, 1)], 4, 3)
)
def test_02_znak(self):
self.assertEqual(".", znak(set()))
self.assertEqual("F", znak({"F"}))
self.assertEqual("b", znak({"b"}))
self.assertEqual("3", znak({"b", "A", "t"}))
self.assertEqual("5", znak({"b", "A", "t", "r", "Z"}))
m = {"F"}
self.assertEqual("F", znak({"F"}))
self.assertEqual({"F"}, m)
def test_03_izris(self):
e = set()
self.assertEqual("""
.A..
.d.3
2.a.
""".strip(), izris([[e, {'A'}, e, e],
[e, {'d'}, e, {'C', 'c', 'b'}],
[{'D', 'B'}, e, {'a'}, e]])
)
def test_04_animacija0(self):
self.assertEqual(strip_ani([
"""
......
..A...
......
......
......
......
""",
"""
......
......
..A...
......
......
......
""",
"""
......
......
......
..A...
......
......
""",
"""
......
......
......
...A..
......
......
""",
"""
......
......
......
....A.
......
......
""",
"""
......
......
......
.....A
......
......
""",
"""
......
......
.....A
......
......
......
""",
"""
......
......
....A.
......
......
......
""",
"""
......
......
.....A
......
......
......
""",
"""
......
......
......
.....A
......
......
""",
"""
......
......
......
......
.....A
......
""",
"""
......
......
......
.....A
......
......
""",
"""
......
......
......
....A.
......
......
"""]), animacija0(2, 1, "vv>>>^<>vv^<", 6, 6))
class Test08(unittest.TestCase):
def test_01_dopolnjeno(self):
s = ["Ana", "Berta"]
self.assertEqual(["Ana"] + ["Berta"] * 20, dopolnjeno(s, 21))
self.assertEqual(["Ana", "Berta"], s)
s = [(1, 5), (1, 6), (2, 6), (3, 6)]
self.assertEqual([(1, 5), (1, 6), (2, 6), (3, 6), (3, 6), (3, 6), (3, 6)],
dopolnjeno(s, 7))
self.assertEqual([(1, 5), (1, 6), (2, 6), (3, 6)], s)
def test_02_razporedi(self):
self.assertEqual(
([[(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)]]),
razporedi([(0, 2, ">>>"), (3, 3, "<v"), (4, 2, "")],
[(1, 2, "^^<>>"), (1, 1, ">>")]))
self.assertEqual(
([[(1, 2), (1, 1)],
[(1, 1), (2, 1)],
[(1, 0), (3, 1)],
[(0, 0), (3, 1)],
[(1, 0), (3, 1)],
[(2, 0), (3, 1)]],
[[(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)]]),
razporedi([(1, 2, "^^<>>"), (1, 1, ">>")],
[(0, 2, ">>>"), (3, 3, "<v"), (4, 2, "")],
))
self.assertEqual(
([[(0, 2), (3, 3), (4, 2)],
[(1, 2), (2, 3), (4, 2)],
[(2, 2), (2, 4), (4, 2)],
[(3, 2), (2, 4), (4, 2)]],
[]),
razporedi([(0, 2, ">>>"), (3, 3, "<v"), (4, 2, "")], []))
self.assertEqual(
([],
[[(1, 2), (1, 1)],
[(1, 1), (2, 1)],
[(1, 0), (3, 1)],
[(0, 0), (3, 1)],
[(1, 0), (3, 1)],
[(2, 0), (3, 1)]]),
razporedi([], [(1, 2, "^^<>>"), (1, 1, ">>")]))
self.assertEqual(
([], [[(1, 2),]]),
razporedi([], [[1, 2, ""]]))
self.assertEqual(([], []), razporedi([], []))
def test_03_animacija(self):
self.assertEqual(strip_ani([
"""
.....
.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..
"""]),
animacija([(0, 2, ">>>"), (3, 3, "<v"), (4, 2, "")],
[(1, 2, "^^<>>"), (1, 1, ">>")], 5, 5)
)
self.assertEqual(strip_ani([
"""
.....
.b.D.
Aa..C
...B.
...c.
""",
"""
.....
.abD.
.A..C
..Bc.
.....
""",
"""
.a...
...2.
..AcC
.....
..B..
""",
"""
a....
...3.
...AC
.....
..B..
""",
"""
.a.c.
...2.
...AC
.....
..B..
""",
"""
..ac.
...2.
...AC
.....
..B..
"""]),
animacija([(0, 2, ">>>"), (3, 3, "<v"), (4, 2, ""), (3, 1, "")],
[(1, 2, "^^<>>"), (1, 1, ">>"), (3, 4, "^^^^")], 5, 5)
)
def test_04_prvo_srecanje(self):
self.assertEqual(
(3, 2),
prvo_srecanje((1, 4, "^^>>v<v<"),
(1, 2, ">^>vvv<>")))
self.assertEqual(
(3, 2),
prvo_srecanje((1, 4, "^^>>v<v<"),
(2, 2, ">")))
self.assertIsNone(
prvo_srecanje((1, 4, "^^>>v<v<"),
(5, 0, ">>>>>")))
self.assertIsNone(
prvo_srecanje((1, 1, ">>>>>"),
(2, 1, ">>>>>")))
self.assertEqual(
(4, 1),
prvo_srecanje((2, 1, ">>"),
(1, 1, ">>>>>>")))
def test_05_bingo(self):
self.assertEqual(
(13, 14),
bingo([(10, 14, ">>>>>>>>")],
(12, 16, "^>^>^>^>^>")))
self.assertEqual(
(14, 13),
bingo([(9, 13, ">>>>>>>>")],
(12, 16, "^>^>^>^>^>")))
self.assertEqual(
(15, 12),
bingo([(8, 12, ">>>>>>>>")],
(12, 16, "^>^>^>^>^>")))
self.assertEqual(
(13, 14),
bingo([(8, 12, ">>>>>>>>"), (10, 14, ">>>>>>>>"), (9, 13, ">>>>>>>>")],
(12, 16, "^>^>^>^>^>")))
class Test09(unittest.TestCase):
def test_simulacija(self):
# V tem bloku je ugrabljenec na (2, 2), marsovci pa na različnih lokacijah
# Marsovec je na (2, 2); prideta dva specialca, eden zgrabi marsovca, drugi ugrabljenca
self.assertTrue(simulacija([">>vv", ">>vv"], [(2, 2, "")]))
# Specialec pobere marsovca, manjka pa specialec, ki reši ugrabljenca
self.assertFalse(simulacija([">>vv"], [(2, 2, "")]))
# Marsovca sta na koncu na (2, 2) in (1, 2)
self.assertTrue(simulacija([">>vv", ">vv", ">>vv"], [(2, 0, "vv"), (3, 2, "<<")]))
# Marsovca sta na koncu na (2, 2) in (1, 2)
# Specialca pobereta marsovca, manjka pa specialec, ki reši ugrabljenca
self.assertFalse(simulacija([">>vv", ">vv"], [(2, 0, "vv"), (3, 2, "<<")]))
# Marsovca sta na koncu na (2, 3) in (1, 2)! Tega na (2, 3) ne ulovimo.
self.assertFalse(simulacija([">>vv", ">vv", ">>vv"], [(2, 0, "vvv"), (3, 2, "<<")]))
# Zdaj pa ga
self.assertTrue(simulacija([">>vv", ">vv", ">>vvv"], [(2, 0, "vvv"), (3, 2, "<<")]))
# En specialec preveč; nič hudega
self.assertTrue(simulacija([">>vv", ">vv", "vv", ">>vvv"], [(2, 0, "vvv"), (3, 2, "<<")]))
# Marsovca končata na (3, 2) in (1, 2)
# Ugrabljenec sta lahko na (2, 2) ali (3, 2); enega ne dobimo
self.assertFalse(simulacija([">>vv", ">vv", ">>>>v"], [(2, 0, "vv>"), (3, 2, "<<")]))
self.assertFalse(simulacija([">>>>v", ">vv", ">>>>v"], [(2, 0, "vv>"), (3, 2, "<<")]))
# Zdaj je pa v redu
self.assertTrue(simulacija([">>vv", ">vv", "vv>>>", "vv>>>"], [(2, 0, "vv>"), (3, 2, "<<")]))
# S slike
self.assertTrue(
simulacija(["vvv>>", # rdeči
">>>>>vvvv>", # desni ugrabljenec
">>>>vvvvvvv", # modri
">>vvvvv", # zeleni
">vv", # oranžni
"v>>>>vvvv" # levi ugrabljenec
],
poti_s_slike)
)
# Ta, ki je bil planiran za zelenega, prej naleti na rdečega
# pazi na vrstni red!
self.assertFalse(
simulacija([">>>>>vvvv>", # desni ugrabljenec
">>>>vvvvvvv", # modri
">>vvvvv", # zeleni
">vv", # oranžni
"vvv>>", # rdeči
"v>>>>vvvv" # levi ugrabljenec
],
poti_s_slike)
)
# Zgrešimo levega ugrabljenca
self.assertFalse(
simulacija(["vvv>>", # rdeči
">>>>>vvvv>", # desni ugrabljenec
">>>>vvvvvvv", # modri
">>vvvvv", # zeleni
">vv", # oranžni
"v>>>>vvvvv" # levi ugrabljenec
],
poti_s_slike)
)
# Zgrešimo desnega ugrabljenca
self.assertFalse(
simulacija(["vvv>>", # rdeči
">>>>>vvvv", # desni ugrabljenec
">>>>vvvvvvv", # modri
">>vvvvv", # zeleni
">vv", # oranžni
"v>>>>vvvvv" # levi ugrabljenec
],
poti_s_slike)
)
# S slike - s podaljšanimi potmi tistih, ki se v resnici
# prej primejo marsovca
self.assertTrue(
simulacija(["vvv>>>>v>>vv<", # rdeči
">>>>>vvvv>", # desni ugrabljenec
">>>>vvvvvvv>>v<<>>", # modri
">>vvvvv^^^<<", # zeleni
">vv^^v>v", # oranžni
"v>>>>vvvv" # levi ugrabljenec
],
poti_s_slike)
)
self.assertTrue(
simulacija(["v", ">", ">v", ">v", ">v"],
[(1, 0, ""), (0, 1, ""), (1, 1, ""), (1, 1, "")])
)
self.assertFalse(
simulacija([">v", ">", ">v", ">v", "v"],
[(1, 0, ""), (0, 1, ""), (1, 1, ""), (1, 1, "")])
)
self.assertTrue(
simulacija(["v", ">", "v>", "v>", "v>"],
[(1, 0, ""), (0, 1, ""), (1, 1, ""), (1, 1, "")])
)
self.assertFalse(
simulacija(["v>", ">", "v>", "v>", "v"],
[(1, 0, ""), (0, 1, ""), (1, 1, ""), (1, 1, "")])
)
class Test10(unittest.TestCase):
def test_strategija(self):
specialci = strategija(poti_s_slike)
self.assertTrue(simulacija(specialci, poti_s_slike))
self.assertEqual(10, max(len(p) for p in specialci))
marsovci = [(2, 0, "vv>>"), (3, 0, "vvv"), (0, 1, ">>>>")]
specialci = strategija(marsovci)
self.assertTrue(simulacija(specialci, marsovci))
self.assertEqual(6, len(specialci))
self.assertEqual(6, max(len(p) for p in specialci))
marsovci = [(4, 2, "<<^^"), (4, 1, "<<<<"), (3, 3, "^^^")]
specialci = strategija(marsovci)
self.assertTrue(simulacija(specialci, marsovci))
self.assertEqual(6, len(specialci))
self.assertEqual(5, max(len(p) for p in specialci))
marsovci = [(1, 2, "^^>>>"), (2, 2, "^<<vv")]
specialci = strategija(marsovci)
self.assertTrue(simulacija(specialci, marsovci))
self.assertEqual(3, len(specialci))
self.assertEqual(2, max(len(p) for p in specialci))
marsovci = [(4, 0, "<<<vv"), (0, 3, "^^>>v")]
specialci = strategija(marsovci)
self.assertTrue(simulacija(specialci, marsovci))
self.assertEqual(3, len(specialci))
self.assertEqual(2, max(len(p) for p in specialci))
marsovci = [(0, 0, "")]
self.assertEqual(["", ""], strategija(marsovci))
marsovci = [(4, 0, "<<<vv"), (0, 3, "^^>>v"), (1000, 1000, ">" * 1000)]
specialci = strategija(marsovci)
self.assertTrue(simulacija(specialci, marsovci))
self.assertEqual(4, len(specialci))
self.assertEqual(3000, max(len(p) for p in specialci))
marsovci = [(1, 0, ""), (0, 1, ""), (1, 1, ""), (1, 1, "")]
self.assertTrue(simulacija(strategija(marsovci), marsovci))
marsovci = [(1, 0, ""), (1, 1, ""), (0, 1, ""), (1, 1, "")]
self.assertTrue(simulacija(strategija(marsovci), marsovci))
marsovci = [(1, 0, ""), (1, 1, ""), (1, 1, ""), (0, 1, "")]
self.assertTrue(simulacija(strategija(marsovci), marsovci))
marsovci = [(1, 1, ""), (1, 1, ""), (1, 0, ""), (0, 1, "")]
self.assertTrue(simulacija(strategija(marsovci), marsovci))
marsovci = [(1, 1, ""), (1, 1, ""), (0, 1, ""), (1, 0, "")]
self.assertTrue(simulacija(strategija(marsovci), marsovci))
if __name__ == "__main__":
unittest.main()
Zadnja posodobitev:
May 7, 2022