Vodni top med kraji
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),
('Brtonigla', -71.00, -47.25), ('Kanal', -71.00, 26.25), ('Črnomelj', 39.05, -27.93),
('Trbovlje', 29.61, 35.07), ('Beltinci', 114.81, 80.54), ('Domžale', -2.34, 31.50),
('Hodoš', 120.70, 105.00), ('Škofja Loka', -23.64, 35.07), ('Velike Lašče', 0.00, 0.00),
('Velenje', 33.16, 54.29), ('Šoštanj', 29.61, 57.75), ('Laško', 42.60, 33.29),
('Postojna', -29.54, -5.25), ('Ilirska Bistrica', -27.19, -27.93),
('Radenci', 100.61, 84.00), ('Črna', 15.41, 66.57), ('Radeče', 39.05, 24.57),
('Vitanje', 47.36, 57.75), ('Bled', -37.84, 56.07), ('Tolmin', -63.90, 36.75),
('Miren', -72.14, 7.04), ('Ptuj', 87.61, 61.32), ('Gornja Radgona', 97.06, 89.25),
('Plave', -73.34, 21.00), ('Novo mesto', 37.91, -3.47), ('Bovec', -76.89, 52.50),
('Nova Gorica', -69.79, 12.29), ('Krško', 60.35, 14.07), ('Cerknica', -18.89, -3.47),
('Slovenska Bistrica', 66.31, 57.75), ('Anhovo', -72.14, 22.78), ('Ormož', 107.71, 61.32),
('Škofije', -59.14, -27.93), ('Čepovan', -60.35, 22.78), ('Murska Sobota', 108.91, 87.57),
('Ljubljana', -8.24, 22.78), ('Idrija', -43.74, 17.54), ('Radlje ob Dravi', 41.46, 82.32),
('Žalec', 37.91, 43.79), ('Mojstrana', -49.70, 64.79),
('Log pod Mangartom', -73.34, 59.54), ('Podkoren', -62.69, 70.04),
('Kočevje', 16.61, -21.00), ('Soča', -69.79, 52.50), ('Ajdovščina', -53.25, 5.25),
('Bohinjska Bistrica', -48.49, 47.25), ('Tržič', -22.44, 56.07), ('Piran', -75.69, -31.50),
('Kranj', -20.09, 43.79), ('Kranjska Gora', -60.35, 68.25), ('Izola', -68.59, -31.50),
('Radovljica', -31.95, 54.29), ('Gornji Grad', 13.06, 49.03), ('Šentjur', 54.46, 40.32),
('Koper', -63.90, -29.72), ('Celje', 45.01, 42.00), ('Mislinja', 42.60, 66.57),
('Metlika', 48.56, -19.21), ('Žaga', -81.65, 49.03), ('Komen', -63.90, -1.68),
('Žužemberk', 21.30, 0.00), ('Pesnica', 74.55, 80.54), ('Vrhnika', -23.64, 14.07),
('Dravograd', 28.40, 78.75), ('Kamnik', -1.14, 40.32), ('Jesenice', -40.19, 64.79),
('Kobarid', -74.55, 43.79), ('Portorož', -73.34, -33.18), ('Muta', 37.91, 82.32),
('Sežana', -54.39, -13.96), ('Vipava', -47.29, 1.79), ('Maribor', 72.21, 75.28),
('Slovenj Gradec', 31.95, 71.82), ('Litija', 14.20, 22.78), ('Na Logu', -62.69, 57.75),
('Stara Fužina', -52.04, 47.25), ('Motovun', -56.80, -52.50), ('Pragersko', 73.41, 57.75),
('Most na Soči', -63.90, 33.29), ('Brestanica', 60.35, 15.75),
('Savudrija', -80.44, -34.96), ('Sodražica', 0.00, -6.93),
]
Ogrevalne naloge
- Izpiši imena vseh krajev.
- Izpiši imena vseh krajev in njihove razdalje od koordinatnega izhodišča.
- Izpiši razdaljo do kraja, ki je najbolj oddaljen od koordinatnega izhodišča.
- Izpiši ime kraja, ki je najbolj oddaljen od koordinatnega izhodišča.
Rešitev
Prva naloga je služila temu, da se spomnimo, kako z zanko prek seznama trojk.
for ime, x, y in kraji:
print(ime)
Druga naloga doda samo malo računanja. Toliko, da res potrebujemo x in y.
from math import *
for ime, x, y in kraji:
print(ime, sqrt(x ** 2 + y ** 2))
Tretja naloga je podobna iskanju največjega elementa v seznamu - le da ne iščemo največjega elementa temveč največjo razdaljo, naračunano iz koordinat v seznamu.
naj_razdalja = 0
for ime, x, y in kraji:
razdalja = sqrt(x ** 2 + y ** 2)
if razdalja > naj_razdalja:
naj_razdalja = razdalja
print(naj_razdalja)
Četrta je podobna tretji, vendar bi bila za začetnika kar težka, če ne bi skoraj iste naloge rešili na predavanjih in sem njeno rešitev objavil tudi na forumu. Le poleg razdalje si zapomnimo še ime kraja.
naj_razdalja = 0
for ime, x, y in kraji:
razdalja = sqrt(x ** 2 + y ** 2)
if razdalja > naj_razdalja:
naj_razdalja = razdalja
naj_kraj = ime
print(naj_kraj)
Obvezna naloga
V nekem (podanem) kraju kupijo visokodometni vodni top s podanim dometom. Napiši program, ki poišče najbolj oddaljeni kraj, ki ga še lahko zalivajo.
Točneje: program naj se začne z gornjo tabelo krajev, ki ji sledi tole:
from math import *
kraj = "Ljubljana"
domet = 30
Pod to dopiši vse, kar je potrebno, da se izpiše:
Ljubljana je na koordinatah -8.24 22.78
Iz kraja Ljubljana lahko zalijemo kraj Cerknica na razdalji 28.328166195502313
Program naj bo sestavljen tako, da lahko zamenjamo kraj in domet s čim drugim, pa dobimo ustrezen drugačen izpis. Tako mora za, na primer
kraj = "Litija"
domet = 60
izpisati
Litija je na koordinatah 14.2 22.78
Iz kraja Litija lahko zalijemo kraj Rogaška Slatina na razdalji 59.96372570146054
Rešitev
Najprej bomo poiskali koordinate kraja kraj. Naloga je bila namerno sestavljena tako, da vas prisili v to.
for ime, x0, y0 in kraji:
if ime == kraj:
break
print(kraj, "je na koordinatah", x0, y0)
Kako to deluje? Zanka se vrti, dokler ne najde kraja, katerega ime je kraj. Ko ga najde, se zanka prekine (break) in vrednosti x0 in y0 ostanejo, kakršne so bile v tistem trenutku.
Odtod gre skoraj tako kot pri zadnji ogrevalni nalogi, le da ne računamo razdalje od koordinatnega izhodišča temveč od x0, y0. Le še pogoj moramo spremeniti: razdalja mora biti večja kot naj_razdalja, a manjša ali enaka domet.
naj_razdalja = 0
for ime, x, y in kraji:
razdalja = sqrt((x - x0) ** 2 + (y - y0) ** 2)
if naj_razdalja < razdalja <= domet:
naj_razdalja = razdalja
naj_kraj = ime
print("Iz kraja", kraj, "lahko zalijemo kraj", naj_kraj, "na razdalji", naj_odd)
Dodatna naloga
Zdaj pa imamo dva kraja in en domet, recimo
kraj1 = "Ljubljana"
kraj2 = "Bled"
domet = 30
Tadva kraja se zmenita, da bosta družno zalivala nek tretji kraj. Izpiši imena vseh krajev, ki jih torej lahko družno zalivata (ker so od obeh podanih krajev oddaljeni za manj kot domet). V gornjem primeru mora izpisati
Škofja Loka
Kranj
Rešitev
Precej podobna reč - ali pa celo malo preprostejša. Najprej poiščemo koordinati obeh krajev. Nato gremo prek vseh krajev in izpišemo imena tistih, katerih razdalja do obeh krajev je manjša od domet.
kraj1 = "Ljubljana"
kraj2 = "Bled"
domet = 30
for ime, x1, y1 in kraji:
if ime == kraj1:
break
for ime, x2, y2 in kraji:
if ime == kraj2:
break
for ime, x, y in kraji:
if sqrt((x - x1) ** 2 + (y - y1) ** 2) < domet and sqrt((x - x2) ** 2 + (y - y2) ** 2) < domet:
print(ime)
Zelo dodatna naloga (za raziskovalce)
Imamo dva kraja, recimo Koper in Maribor, ter domet, na primer 30. Zanima nas, kako v najmanj korakih, manjših od 30, priti od prvega do drugega kraja. Se pravi, če imamo
kraj1 = "Koper"
kraj2 = "Maribor"
domet = 30
mora program izpisati
Koper
Dutovlje
Postojna
Sodražica
Kočevje
Novo mesto
Krško
Rogaška Slatina
Ptuj
Maribor
Za dodatni izziv: ne uporabi ničesar, česar nismo povedali na predavanjih. Ni slovarjev, ni indeksiranja, ... S seznami ne znamo početi drugega, kot spustiti prek njih zanko for in dodajati vanje z append.
Rešitev
Takoj po predavanjih je nekdo odkril, da je potrebno napisati Dijsktrin algoritem. V resnici gre za nekaj še preprostejšega: Dijkstrin algoritem, kjer so vse razdalje enake 1, kar je isto kot iskanje v globino.
Najpreprostejši algoritem je lahko takšen. Pot bomo iskali ritensko, ker jo bo tako lažje izpisati pravilno (gre tudi drugače, a za zdaj nam bo tako preprosteje). Imamo seznam kandidati - tam so kraji, ki smo jih že pogledali ali pa so dostopni iz njih v enem koraku. V začetku je to kandidati = [kraj2]. Poleg tega pripravimo seznam od_kod, v katerega si bomo zapisovali pare, od kod gremo kam.
Zdaj pa gremo čez vse kandidate. Za vsak kraj v seznamu kandidatov (imenujmo ga naslednji) ugotovimo njegove koordinate. (Način, na katerega to delamo, je strašno nadležen in od naslednjega tedna bomo znali preprosteje.) Nato gremo prek vseh ostalih krajev. Za vsakega od teh krajev (imenujmo ga naprej) preverimo, ali je dostopen iz naslednji in ali ni morda že v seznamu kandidatov. Če je dostopen in ni med kandidati, ga dodamo med kandidate in si zapomnimo, kako smo prišli vanj, tako da v od_kod dodamo (naprej, naslednji).
Ko zmanjka kandidatov, smo prehodili vse (dostopne) kraje. Zdaj sledi le še zanka, s katero prehodimo pot od začetka do konca, tako da pobiramo ustrezne pare iz od_kod.
kandidati = [kraj2]
od_kod = []
for naslednji in kandidati:
# Ugotovimo koordinate kraja `naslednji`
for ime, x0, y0 in kraji:
if ime == naslednji:
break
# Za vsak kraj, ki je dostopen iz `naslednji` preverimo
# ali je že v `kandidati`. Če ni, ga dodamo, in si zapomnimo,
# odkod smo prišli vanj
for naprej, x1, y1 in kraji:
if sqrt((x0 - x1) ** 2 + (y0 - y1) ** 2) < domet:
for videno in kandidati:
if naprej == videno:
break
else:
kandidati.append(naprej)
od_kod.append((naprej, naslednji))
# Prehodi pot iz kraj1 do kraj2
kraj = kraj1
print(kraj1)
while kraj != kraj2:
for ta, prej in od_kod:
if ta == kraj:
kraj = prej
break
print(kraj)
Program je nemarno dolg. Malo se skrajša, če si dovolimo uporabiti operator in, da preverimo, ali je naprej že v seznamu kandidati.
kandidati = [kraj2]
od_kod = []
for naslednji in kandidati:
for ime, x0, y0 in kraji:
if ime == naslednji:
break
for naprej, x1, y1 in kraji:
if sqrt((x0 - x1) ** 2 + (y0 - y1) ** 2) < domet:
if naprej not in kandidati:
od_kod.append((naprej, naslednji))
kandidati.append(naprej)
kraj = kraj1
print(kraj1)
while kraj != kraj2:
for ta, prej in od_kod:
if ta == kraj:
kraj = prej
break
print(kraj)
Še boljše pa bi bilo, če ne bi bilo potrebno iskati koordinat krajev in če bi bil izpis poti kaj preprostejši. Za to potrebujemo slovarje. Teh še ne poznamo (no, vsaj učili se še nismo o njih). Če bi jih poznali, pa bi nalogo rešili takole.
kraji = {ime: (x, y) for ime, x, y in kraji}
kandidati = [kraj2]
od_kod = {}
for kraj in kandidati:
x, y = kraji[kraj]
for naprej, (x1, y1) in kraji.items():
if naprej not in od_kod and sqrt((x - x1) ** 2 + (y - y1) ** 2) < domet:
od_kod[naprej] = kraj
kandidati.append(naprej)
kraj = kraj1
print(kraj)
while kraj != kraj2:
kraj = od_kod[kraj]
print(kraj)
Če bi šlo komu na živce, da imamo kandidati in od_kod, pa lahko uporabi urejene slovarje.
import collections
kraji = {ime: (x, y) for ime, x, y in kraji}
kandidati = collections.OrderedDict.fromkeys([kraj2])
for kraj in kandidati:
x, y = kraji[kraj]
for naprej, (x1, y1) in kraji.items():
if naprej not in od_kod and sqrt((x - x1) ** 2 + (y - y1) ** 2) < domet:
kandidati[naprej] = kraj
kraj = kraj1
print(kraj)
while kraj != kraj2:
kraj = od_kod[kraj]
print(kraj)
Zdaj je rešitev že sumljivo kratka. Da bi jo še čisto malo skrajšali, zapišimo koordinate s kompleksnimi števili.
import collections
kraji = {ime: x + 1j * y for ime, x, y in kraji}
kandidati = collections.OrderedDict.fromkeys([kraj2])
for kraj in kandidati:
for naprej, coords in kraji.items():
if naprej not in od_kod and abs(coords + kraji[kraj]) < domet:
kandidati[naprej] = kraj
kraj = kraj1
print(kraj)
while kraj != kraj2:
kraj = od_kod[kraj]
print(kraj)
Na koncu pa še stisnimo dodajanje novih kandidatov.
import collections
kraji = {ime: x + 1j * y for ime, x, y in kraji}
kandidati = collections.OrderedDict.fromkeys([kraj2])
for kraj in kandidati:
kandidati.update({naprej: kraj for naprej, coords in kraji.items()
if naprej not in od_kod and abs(coords + kraji[kraj]) < domet})
kraj = kraj1
print(kraj)
while kraj != kraj2:
kraj = od_kod[kraj]
print(kraj)
No, to je pa že izživljanje. :)
Hecno je, da imamo dve vrstici priprave, cel algoritem je v dveh vrstica, potem pa potrebujemo še pet vrstic, da reč izpišemo. :)