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.

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.

Za oceno 6

Rešitev

razdalja

Ker je število dimenzij poljubno, bomo kvadrate razlik seštevali z zanko.

from math import sqrt

def razdalja(x, y):
    r = 0
    for xi, yi in zip(x, y):
        r += (xi - yi) ** 2
    return sqrt(r)

Pravzprav pa znamo tudi preprosteje. (Ali bolj zapleteno, kakor za koga.)

def razdalja(x, y):
    return sqrt(sum((xi - yi) ** 2 for xi, yi in zip(x, y)))

najblizja

Iskanje "najboljšega" elementa po določenem kriteriju je stara naloga.

def najblizja(marsovec, ladje):
    naj_ladja = naj_razdalja = None
    for ladja in ladje:
        razd = razdalja(marsovec, ladja)
        if naj_razdalja is None or razd < naj_razdalja:
            naj_razdalja = razd
            naj_ladja = ladja
    return naj_ladja

Zanimivo je, da je precej študentov pozabljalo vrstico naj_razdalja = razd, zato so vrnili zadnjo ladjo, ki je bila bližja od prve ladje. Nerodno je, da tega niso odkrili testi za to funkcijo temveč šele testi za eno naslednjih. Pri pisanju testov je pač težko pomisliti na vse možne napake.

Kdor zna nekaj več, pa je naredil tole:

def najblizja(marsovec, ladje):
    return min(ladje, key=lambda ladja: razdalja(marsovec, ladja))

dodeli_ladje

Gremo po seznamu marsovcev in v nov seznam zlagamo pripadajoče najbližje ladje.

def dodeli_ladje(marsovci, ladje):
    dodelitev = []
    for marsovec in marsovci:
        dodelitev.append(najblizja(marsovec, ladje))
    return dodelitev

Lahko pa tudi tako.

def dodeli_ladje(marsovci, ladje):
    return [najblizja(marsovec, ladje) for marsovec in marsovci]

skupine_marsovcev

Tu se je najbolj splačalo sestaviti slovar, katerega ključi so naše ladje, pripadajoči seznami pa marsovske ladje, ki jih bo uničila ta naša ladja. Funkcija potem vrne seznam vrednosti v tem slovarju.

from collections import defaultdict


def skupine_marsovcev(marsovci, ladje):
    dodelitve = defaultdict(set)
    for marsovec, ladje in zip(marsovci, dodeli_ladje(marsovci, ladje)):
        dodelitve[ladje].add(marsovec)
    return list(dodelitve.values())

Za oceno 7

Rešitev

sredisce

Nalogo je možno rešiti na kup načinov. Tu kar takoj pokažimo enega elegantnejših.

def sredisce(s):
    p = [0] * len(s[0])
    for x in s:
        p = [pi + xi for pi, xi in zip(p, x)]
    return tuple(pi / len(s) for pi in p)

V p bomo sešteli vse elemente s po koordinatah. Najprej vanj vpišemo toliko ničel, kolikor je dimenzij. Nato gremo prek vseh točk v s in zamenjamo p s seznamom, ki vsebuje vsoto istoležnih elementov p-ja in s-ja. Na koncu vrnemo terko, ki vsebuje elemente p-ja deljene s številom ladij.

Nekoliko splošnejša rešitev je tale:

def sredisce(s):
    p = None
    for x in s:
        if p == None:
            p = x
        else:
            p = [pi + xi for pi, xi in zip(p, x)]
    return tuple(pi / len(s) for pi in p)

Namesto da p inicializiramo s samimi ničlami, ga v začetku nastavimo na None in potem zanj uporabimo prvi element. Ker ta rešitev ne zahteva elementa z indeksom 0, deluje tudi, če je s generator. Naloga tega ni zahtevala, nič pa ni narobe, če se spomnimo, kako se to naredi.

razpostavi_ladje

Tu ni kaj pametovati: vrniti moramo seznam središč skupin, torej:

def razpostavi_ladje(skupine):
    return [sredisce(v) for v in skupine]

Za oceno 8

Rešitev

Zapomnili si bomo položaje ladij in zanko izvajali, dokler je novi položaj drugačen kot stari. V zanki pa določimo (nove) skupine marsovcev in razpostavimo ladje.

def optimiraj_ladje(marsovci, ladje):
    ladje_prej = None
    while ladje != ladje_prej:
        ladje_prej = ladje
        ladje = razpostavi_ladje(skupine_marsovcev(marsovci, ladje))
    return set(ladje)

Za oceno 9

Rešitev

kvaliteta(marsovci, ladje)

Vrniti je potrebno vsoto razdalij med marsovci in ladjami, ki jim jih dodelimo, torej:

def kvaliteta(marsovci, ladje):
    return sum(razdalja(marsovec, ladja)
               for marsovec, ladja in zip(marsovci, dodeli_ladje(marsovci, ladje)))

Pravzaprav pa je celo krajše, če ne kličemo dodeli_ladje in se izognemo zip-u.

def kvaliteta(marsovci, ladje):
    return sum(razdalja(marsovec, najblizja(marsovec, ladje)) for marsovec in marsovci)

nakljucna

Je bila to najtežja funkcija? Mogoče. Rešitev brez hujših trikov je takšna.

def nakljucna(marsovci, ladij):
    moznosti = [[] for _ in marsovci[0]]
    for marsovec in marsovci:
        for i, x in enumerate(marsovec):
            moznosti[i].append(x)

    ladje = []
    for _ in range(ladij):
        nova = []
        for izbor in moznosti:
            nova.append(random.choice(izbor))
        ladje.append(tuple(nova))
    return ladje

V prvem delu funkcije sestavimo sezname seznamov: i-ti element vsebuje seznam vseh možnih i-tih koordinat.

V drugem delu v nova sestavljamo koordinate ladje tako, da gremo prek vseh dimenzij in iz vsake naključno izberemo eno.

Prvemu delu se lahko izognemo tako, da gremo prek dimenzij in za vsako dimenzijo izžrebamo nekega marsovca ter v nova dodamo ustrezno koordinato.

def nakljucna(marsovci, ladij):
    dim = len(marsovci[0])
    ladje = []
    for _ in range(ladij):
        nova = []
        for i in range(dim):
            nova.append(random.choice(marsovci)[i])
        ladje.append(tuple(nova))
    return ladje

Tole gre očitno v eno vrstico.

def nakljucna(marsovci, ladij):
    return [tuple(random.choice(marsovci)[i] for i in range(len(marsovci[0])))
            for _ in range(ladij)]

Lepše pa je s tem trikom.

def nakljucna(marsovci, ladij):
    moznosti = list(zip(*marsovci))
    return [tuple(random.choice(izbor) for izbor in moznosti) for _ in range(ladij)]

To je po zgledu prve funkcije. Prva vrstica ustreza prvemu delu, druga drugemu.

Za oceno 10

Rešitev

optimiraj_ladje_2

Tule le pokličemo funkciji, ki ju že imamo.

def optimiraj_ladje_2(marsovci, ladje):
    pozicije = optimiraj_ladje(marsovci, ladje)
    return kvaliteta(marsovci, pozicije), pozicije

planiraj

To pa je repriza funkcije najblizja_ladja, le da ne iščemo najbližje ladje temveč najboljši razpored.

Ker gre za nalogo za oceno 10, jo naredimo le po najhitrejši različici - sploh zato, ker naj je optimiraj_ladje_2 namignila, dala terke, med katerimi je potrebno poiskati najmanjšo in vrniti njen element z indeksom 1.

def planiraj(marsovci, ladij):
    return min(optimiraj_ladje_2(marsovci, nakljucna(marsovci, ladij)) for _ in range(100))[1]