p1 - 2021/22 - Izpit 7.1.2022
| file | link |
|---|---|
| Navodila izpita | izpit 22-01-17-15.00-1.pdf |
| Testi | test2.py |
Navodila¶
Iz dobro obveščenih virov na Facebooku se je izvedelo, kakšen je namen marsovske invazije: prišli so nam krast paradižnik! (Resno. To je povedal ugleden znanstvenik, ki je skoraj Nobelov nagrajenec za ekonomijo. Poglejte video.)
1. Uravnotežene ladje¶
Če je marsovska tovorna vesoljska ladja naložena tako, da je razlika med težo tovora na levi in desni strani večja od 10, se prevrne. Tudi v vesolju se zgodi. Zato jih natovarjajo tako, da pakete izmenično odlagajo na levo in na desno.
Vendar si tega niso najboljše zamislili: če imajo pakete [2, 10, 3, 8, 1], se ladja prevrne, ker je skupna teža paketov na levi enaka 6, na desni pa 18, kar je več kot 10 več.
Napiši funkcijo uravnotezena(tovor), ki prejme seznam paketov in vrne True, če je ladja uravnotežena in False, če ni. Zaželeno je, da funkcijo napišeš v eni vrstici.
2. Delitev paketov¶
Kako bodo delili pakete po ladjah? Za vsako ladjo je znana nosilnost. Nato jemljejo pakete po vrsti. Vsak paket dajo na tisto ladjo, ki je trenutno najmanj obremenjena in je ta paket ne bo preobremenil. (Če je najmanj obremenjenih več ladij, gre paket na tisto, ki je prej na seznamu.) Če paketa ne more sprejeti nobena ladja, ga ne naložijo. Primer v tabeli kaže razporejanje paketov s težami [6, 4, 2, 1, 5, 1, 15] na ladje z nosilnostmi [5, 20, 7].
Napiši funkcijo deli(paketi, kapacitete), ki prejme teže paketov in seznam kapacitet razpoložljivih ladij. Vrniti mora seznam, ki vsebuje skupno težo paketov na vsaki ladji.
| paket | kam gre in zakaj | stanje |
|---|---|---|
| 6 | na drugo, ker ne more na prvo | [0, 6, 0] |
| 4 | prva ima najmanj | [4, 6, 0] |
| 2 | tretja ima najmanj | [4, 6, 2] |
| 1 | tretja ima najmanj | [4, 6, 3] |
| 5 | na prvo in tretjo ne more | [4, 11, 3] |
| 1 | na tretji je najmanj | [4, 11, 4] |
| 15 | ne gre nikamor | [4, 11, 4] |
3. Kontrola načrta¶
Načrt natovarjanja je shranjen v datoteki. Vsaka vrstica vsebuje ime ladje, dvopičje, nosilnost, dvopičje in teže paketov, ki jih kanijo naložiti na to ladjo. Napiši funkcijo kontrola(ime), ki prejme ime datoteke in vrne množico imen ladij, ki so preobremenjene. Na desni sliki so preobremenjene Gugbat, Humwat Bolwat in Askeg 8.
Gubgat: 20: 10, 5, 6
Thrombaq: 5: 1
Thrombaq 2: 5: 1, 4
Humwat Bolwat: 10: 2, 2, 2, 2, 2, 2
Askeg 8: 13: 14
4. Hierarhija¶
Marsovci imajo, vemo, na glavah antene. Te so pomembne za avtoriteto: marsovec s krajšo anteno ne more ukazovati marsovcu z daljšo.
Ladjo vodi hierarhija skladiščnikov; na sliki so njihova imena in dolžine njihovih anten v marsimetrih. Primer na sliki kaže nepravilno hierarhijo, saj Hans ne more ukazovati Eriku.
Napiši funkcijo pravilna(marsovec, hierarhija, antene), ki prejme ime nekega marsovca, slovar s hierarhijo, slovar z dolžinami anten (glej primer v testih). Vrniti mora True, če je hierarhija pod podanim marsovcem pravilna in False, če ni.
5. Marsis¶
Marsovski Pravilnik o higieni živil pravi, da sme marsovska ladja tovoriti največ tri različne vrste paradižnika. Sprogramiraj razred Ladja z naslednjimi metodami: - Konstruktor nima argumentov in naredi, kar je potrebno, da delujeta preostali metodi. - nalozi(sorta, teza) preveri, ali ladja sme natovoriti (še) to sorto paradižnika. Če jo lahko, to pomeni, da ga bodo natovorili in funkcija vrne True. Če ga ne sme prevzeti, vrne False. - kolicina(sorta) vrne skupno težo vseh natovorjenih paradižnikov te sorte (0, če je nimajo).
Resitev¶
Resitev - Starc Aljaz
from typing import List, Set
from itertools import count
Tovor = List[int]
ImeMarsovca = str
ImeLadje = str
SortaParadiznika = str
TezaParadiznika = int
def parts(source: str, delimiter: str) -> List[str]:
return [ p.strip() for p in source.split(delimiter) ]
def uravnotezena(tovor: Tovor) -> True | False:
maxrazlika = 10
razlika = 0
pristej = 1
for paket, i in zip(tovor, count()):
razlika += paket if i % 2 == 0 else 0 - paket
return abs(razlika) <= maxrazlika
def deli(paketi: Tovor, kapacitete: List[int]) -> List[int]:
paketi = paketi.copy()
teze_ladij = [ 0 for _ in kapacitete ]
for paket in paketi:
od_najmanj_do_najbolj_obremenjene = sorted(zip(teze_ladij, count()), key=lambda l: l[0])
for obremenitev, iladje in od_najmanj_do_najbolj_obremenjene:
if obremenitev + paket <= kapacitete[iladje]:
teze_ladij[iladje] += paket
break
return teze_ladij
def kontrola(ime: str) -> Set[ImeLadje]:
with open(ime) as f:
lines = f.readlines()
preobremenjene = set()
for line in lines:
ime, nosilnost_str, paketi_str = parts(line, ":")
paketi = [ int(s) for s in parts(paketi_str, ",") ]
skupna_teza = sum(paketi)
if skupna_teza > int(nosilnost_str):
preobremenjene.add(ime)
return preobremenjene
def pravilna(marsovec: ImeMarsovca, hierarhija, antene) -> True | False:
for podmarsovec in hierarhija[marsovec]:
# Ce ima kateri koli od direktno-podrejenih marsovcev
# krajso anteno, vrnemo False
if antene[podmarsovec] > antene[marsovec]:
return False
# Ali ce je katera koli direktna pod-hiararhija napacna
# vrnemo False
elif not pravilna(podmarsovec, hierarhija, antene):
return False
# Ce pridemo do sem, pomeni da vse ustreza planu
return True
class Ladja:
def __init__(self):
self.maxSorte = 3
self.sorte = dict()
def nalozi(self, sorta: SortaParadiznika, teza: TezaParadiznika) -> True | False:
# Ce je maksimalna raznolikost sort dosezena,
# je nalaganje zavrnjeno
if len(self.sorte.keys()) >= self.maxSorte and sorta not in self.sorte.keys():
return False
# Sicer pa jo nalozimo
self.sorte[sorta] = self.kolicina(sorta) + teza
return True
def kolicina(self, sorta: SortaParadiznika) -> int:
return self.sorte[sorta] if sorta in self.sorte.keys() else 0