Vodni topovi

Imamo seznam nekaterih slovenskih krajev v nekem koordinatnem sistemu.

kraji = [
    ('Brežice', 68.66, 7.04), ('Lenart', 85.20, 78.75), ('Rateče', -65.04, 70.04),
    ('Ljutomer', 111.26, 71.82), ('Rogaška Slatina', 71.00, 42.00), ('Ribnica', 7.10, -10.50),
    ('Dutovlje', -56.80, -6.93), ('Lokve', -57.94, 19.32), ('Vinica', 43.81, -38.43),

in tako naprej.

Napiši naslednje funkcije:

• v_slovar(seznam_krajev) prejme seznam, kakršen je gornji, in ga predela v slovar, katerega ključi so imena krajev, pripadajoče vrednosti pa terke (pari števil) s koordinatami.
• razdalja_koordinat(x1, y1, x2, y2) dobi koordinate dveh točk in vrne razdaljo med njima.
• razdalja(ime1, ime2, kraji) prejme imeni dveh krajev in slovar, kakršnega vrne funkcija v_slovar. Kot rezultat vrne razdaljo med krajema.

V krajih so začeli kupoveti visokodometne vodne topove. Napiši funkcije

• v_dometu(ime_kraja, domet, kraji), ki prejme ime kraja, kamor postavimo top, domet topa ter slovar koordinat krajev. Funkcija vrne množico vseh krajev, ki jih lahko zalijemo iz tega kraja (brez kraja samega!).
• skupno_zalivanje(ime1, ime2, domet, kraji), ki vrne množico vseh krajev, ki jih je možno hkrati zalivati iz krajev ime1 in ime2, če vanju postavimo topova z dometom domet.
• naj_par(domet, kraji): če kupimo samo dva topa z dometom domet, v katera dva kraja ju je potrebno postaviti, da bomo z njima zalili čimveč drugih krajev? Funkcija naj vrne par (terko) krajev, urejeno po abecedi (('Ajdovščina', 'Ljubljana'), in ne ('Ljubljana', 'Ajdovščina').)

Rešitev

Pretvarjanje v slovar ne bi smelo delati težav: sestavimo prazen slovar, gremo čez seznam parov ime, x, y in v slovar pod ključ ime shranimo par (x, y).

def v_slovar(kraji):
    slovar = {}
    for ime, x, y in kraji:
        slovar[ime] = (x, y)
    return slovar

Naslednja funkcija je začetniška.

from math import sqrt

def razdalja_koordinat(x1, y1, x2, y2):
    return sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)

Pri merjenju razdalje med krajema, uporabimo slovar (ki smo ga pripravili s prvo funkcijo), da dobimo koordinate, in drugo funkcijo, da izračunamo razdalje med njimi.

def razdalja(ime1, ime2, kraji):
    x1, y1 = kraji[ime1]
    x2, y2 = kraji[ime2]
    return razdalja_koordinat(x1, y1, x2, y2)

Množico krajev v dometu pripravimo tako, da sestavimo prazno množico. Nato gremo prek vseh krajev v slovarju - torej prek vseh ključev, for kraj in kraji - ter za vsakega od njih izmerimo razdaljo do podanega kraja. Če je večja od 0 (kraj ne zaliva sebe) in manjša od dometa, dodamo ime kraja v množico.

def v_dometu(ime, domet, kraji):
    zaliti = set()
    for kraj in kraji:
        if 0 < razdalja(ime, kraj, kraji) <= domet:
            zaliti.add(kraj)
    return zaliti

Zdaj pa končno nekaj v zvezi z množicami: kraji, ki jih lahko zalivamo iz dveh krajev, so preprosto presek krajev, ki so v njunem dometu.

def skupno_zalivanje(ime1, ime2, domet, kraji):
    return v_dometu(ime1, domet, kraji) & v_dometu(ime2, domet, kraji)

Funkcija naj_par pa računa preseke. Funkcija bo vsebovala gnezdeni zanki, saj moramo prek vseh parov krajev. Nekaj v slogu

...
for kraj1 in kraji:
    for kraj2 in domet1:
        skupni = v_dometu(kraj1, domet, kraji) | v_dometu(kraj2, domet, kraji)
...

Vendar tole ni najbolj varčno: v_dometu(kraj1, domet, kraji) pokličemo za vsak kraj2, čeprav vedno z enakimi argumenti in, seveda, enakim rezultatom. Hitreje bo takole:

for kraj1 in kraji:
    domet1 = v_dometu(kraj1, domet, kraji)
    for kraj2 in domet1:
        skupni = domet1 | v_dometu(kraj2, domet, kraji)

Vse ostalo je samo klasično iskanje največjega elementa.

def naj_par(domet, kraji):
    naj_zalitih = 0
    for kraj1 in kraji:
        domet1 = v_dometu(kraj1, domet, kraji)
        for kraj2 in domet1:
            zaliti = v_dometu(kraj2, domet, kraji) | domet1
            if len(zaliti) >= naj_zalitih:
                naj_zalitih = len(zaliti)
                naj_kraja = kraj1, kraj2
    return tuple(sorted(naj_kraja))

Na koncu moramo vrniti urejen par. Par naj_kraja zato uredimo in ta pretvorimo nazaj v terko.