Čebela v razredu

Testi

Testi: testi-cebela-v-razredu.py

Rešitev

Tule je, za začetek, celotna rešitev, tako da si lahko pred branjem rešitev posamičnih nalog ogledate celotno sliko. Posamične naloge z rešitvami in razlagami so spodaj.

# Funkcije za oceno 8 def ccw(x1, y1, x2, y2, x3, y3): return (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1) >= 0 def se_sekata(x1, y1, x2, y2, x3, y3, x4, y4): return ccw(x1, y1, x3, y3, x4, y4) != ccw(x2, y2, x3, y3, x4, y4) and \ ccw(x1, y1, x2, y2, x3, y3) != ccw(x1, y1, x2, y2, x4, y4) # Se ena pomozna funkcija za oceno 10 (lahko bi jo dali tudi v razred, # vendar bi bilo to najboljše narediti na način, o katerem se nismo učili, # zato sem jo pustil izven razreda) def popmin(f, s): naj_i = 0 naj_x = f(s[0]) if f else s[0] for i, e in enumerate(s): ex = f(e) if f else e if ex < naj_x: naj_x, naj_i = ex, i return s.pop(naj_i) class Cebela: ### Za oceno 6 def __init__(self): self.x = self.y = 0 self.segmenti = [] self.razdalja = 0 def izracunaj_koord(self, smer, velikost): premiki = {"D": (0, 1), "U": (0, -1), "L": (-1, 0), "R": (1, 0)} dx, dy = premiki[smer] return self.x + dx * velikost, self.y + dy * velikost def premik(self, smer, velikost): x1, y1 = self.izracunaj_koord(smer, velikost) self.sekaj_do(x1, y1) def prezarci(self, x1, y1): self.x, self.y = x1, y1 def pot(self): return self.segmenti def metraza(self): return self.razdalja ### Za oceno 7 def leti_do(self, x1, y1): if x1 < self.x: self.premik("L", self.x - x1) elif x1 > self.x: self.premik("R", x1 - self.x) if y1 < self.y: self.premik("U", self.y - y1) elif y1 > self.y: self.premik("D", y1 - self.y) def sekaj_do(self, x1, y1): risar.crta(self.x, self.y, x1, y1) self.segmenti.append(((self.x, self.y), (x1, y1))) self.razdalja += sqrt((self.x - x1) ** 2 + (self.y - y1) ** 2) self.x, self.y = x1, y1 ### Za oceno 8: glej zgoraj ### Za oceno 9 def previdni_premik(self, smer, velikost): x1, y1 = self.izracunaj_koord(smer, velikost) self.previdno_sekaj(x1, y1) def previdno_sekaj(self,x1, y1): for (x2, y2), (x3, y3) in self.segmenti: if len({(self.x, self.y), (x1, y1), (x2, y2), (x3, y3)}) == 4 and \ se_sekata(self.x, self.y, x1, y1, x2, y2, x3, y3): return self.sekaj_do(x1, y1) ### Za oceno 10 def oberi(self, cvetovi): def kot_do(pt): x1, y1 = pt lnx, lny = x1 - self.x, y1 - self.y dist = sqrt(lnx ** 2 + lny ** 2) return -(dx * lnx + dy * lny) / dist, dist neobrano = cvetovi[:] nx, ny = popmin(None, neobrano) self.prezarci(nx, ny) dx, dy = 0, -1 while neobrano: nx, ny = popmin(kot_do, neobrano) dx, dy = nx - self.x, ny - self.y ld = sqrt(dx ** 2 + dy ** 2) dx, dy = dx / ld, dy / ld self.sekaj_do(nx, ny)

Naloga in rešitev

Za oceno 6: Osnovna čebela

Sprogramiraj razred Cebela z naslednjimi metodami.

• Konstruktor, ki naredi, kar pač mora narediti (glede na to, kaj mora znati Cebela, to je, kaj potrebujejo ostale metode); začetne koordinate čebele morajo biti (0, 0).

  V self.x in self.y bomo zapisali koordinate, v self.segmenti prehojeno pot, v self.razdalja pa prehojeno razdaljo.

  class Cebela: def __init__(self): self.x = self.y = 0 self.segmenti = [] self.razdalja = 0
• Metoda premik(smer, razdalja), ki premakne čebelo za podano razdaljo v podano smer in to nariše; naloga je podobna enemu koraku tega, kar so morale počete funkcije v prejšnji nalogi. Tako mora klic ceb.premik("D", 50) premakniti čebelo za 50 korakov navzdol.

  Tole naredimo z mislijo na prihodnost: metoda premik bo klicala metodo sekaj_do; na ta način ji ne bo potrebno shranjevati segmentov in povečevati razdalje, saj bo to delala že sekaj_do. Za izračun koordinat, do katerih bo prišla čebela, pa napišemo posebno metodo, izracunaj_koordinate, ki nam bo prišla prav pri previdnem premiku. Za preostanek te metode poglejte rešitev sekaj_do.

  Ta "premišljenost" ni potrebna; lahko bi naredili tudi brez tega. Metoda je v vsakem primeru preprosta.

  def izracunaj_koord(self, smer, velikost): premiki = {"D": (0, 1), "U": (0, -1), "L": (-1, 0), "R": (1, 0)} dx, dy = premiki[smer] return self.x + dx * velikost, self.y + dy * velikost def premik(self, smer, velikost): x1, y1 = self.izracunaj_koord(smer, velikost) self.sekaj_do(x1, y1)
• Metoda prezarci(x, y) prestavi čebelo na podani koordinati (x, y); pot se ne riše in ne upošteva v izračunih naslednjih dveh metod. def prezarci(self, x1, y1): self.x, self.y = x1, y1
• Metoda pot() vrne vso pot, ki jo je prepotovala čebela, v obliki segmentov, sestavljenih iz terk. Če imamo čebelo ceb in jo pošljemo po poti ceb.premik("D", 50); ceb.premik("R", 15); ceb.premik("U", 10), mora ceb.pot() vrniti seznam [((0, 0), (0, 50)), ((0, 50), (15, 50)), ((15, 50), (15, 40))]. (Seznam v bistvu vsebuje koordinate narisanih črt.)
• Metoda metraza() vrne razdaljo, ki jo je preletela čebela. V gornjem primeru mora vrniti 75 (ker je preletela 50 + 15 +10).

  Vse je že pripravljeno, tidve metodi le vračata shranjeni vrednosti.

  def pot(self): return self.segmenti def metraza(self): return self.razdalja

Za oceno 7: Avtopilot

Dodajte naslednji metodi.

• Metodi leti_do(x, y) podamo koordinati, do katerih naj leti čebela. Čebela naj leti do teh koordinat v (največ) dveh korakih: najprej poskrbi za vodoravno koordinato (če je potrebno), nato za navpično (če je potrebno). Če je, čebela, recimo, na koordinatah (50, 80) in pokličemo leti_do(30, 90) bo letela najprej za 20 korakov levo, na (30, 80), nato pa za 10 dol, na (30, 90).

  Pot, ki jo ob tem naredi čebela, mora biti narisana in zabeležena (v gornjem primeru se k segmentom, ki jih vrne metoda pot(), doda ((50, 80), (30, 80)), ((30, 80), (30, 90)), razdalja, ki jo preleti, pa se poveča za 30.

  Namig: metoda leti_do naj kliče metodo premik.

  Če je x prevelik, gremo levo, če premajhen, desno; če je ravno pravšnji, ne gremo nikamor. Za y pa enako. Ta metoda kliče metodo premik, metoda premik pa, kot smo videli zgoraj, kliče sekaj_do.

  def leti_do(self, x1, y1): if x1 < self.x: self.premik("L", self.x - x1) elif x1 > self.x: self.premik("R", x1 - self.x) if y1 < self.y: self.premik("U", self.y - y1) elif y1 > self.y: self.premik("D", y1 - self.y)
• Metodo sekaj_do(x, y), ki je podobna gornji, le da leti čebela naravnost do podanih koordinat. Če je na koordinatah (50, 80) in pokličemo sekaj_do(30, 90), doda (in nariše) le segment ((50, 80), (30, 90)). Preletena pot se seveda upošteva tudi v razdalji, ki jo poroča metoda metraza().

  Reševanje smo zastavili tako na koncu vsi pokličejo sekaj_do: to je edina metoda, ki v resnici riše, dodaja segmente in povečuje razdaljo.

  def sekaj_do(self, x1, y1): risar.crta(self.x, self.y, x1, y1) self.segmenti.append(((self.x, self.y), (x1, y1))) self.razdalja += sqrt((self.x - x1) ** 2 + (self.y - y1) ** 2) self.x, self.y = x1, y1

Za oceno 8: Nekaj čisto drugega

Za oceno 8 boste napisali dve funkciji (ne metodi), ki sta nepovezani s čebelo, vendar ju bomo potrebovali v nalogah za oceno 9 in 10.

Če imam tri točke in se sprehodim od prve do druge in naprej do tretje, lahko teče ta pot v smeri urinega kazalca ali v nasprotni smeri. Napiši funkcijo ccw(x1, y1, x2, y2, x3, y3), ki dobi (nerodno podane) koordinate treh točk in vrne True, če je smer nasprotna smeri urinega kazalca in False, če ni. Če so točke kolinearne, vrni True.

Kako se to izračuna, smeš poiskati na spletu. Tam boš pravzaprav našla/našel kar celo funkcijo (gre samo za formulo; potrebno je samo izračunati vektorski produkt). Funkcijo smeš prepisati, vendar se potrudi, da jo boš razumel.

Pozor: funkcija naj bo napisana tako, da uporablja "matematične", ne "računalniških" koordinat: y naj narašča navzgor, ne navzdol. (Razlog je preprost: na spletu boste našli formulo v tej obliki; sicer jo je trivialno obrniti, vendar jo raje pustimo v običajni obliki.)

Poleg tega napiši funkcijo se_sekata(x1, y1, x2, y2, x3, y3, x4, y4). Podani argumenti opisujejo dve daljici, prva gre od (x1, y1) do (x2, y2) in druga od (x3, y3) do (x4, y4). Funkcija naj vrne True, če se daljici sekata.

Pri programiranju druge funkcije uporabi prvo. Posurfaj. Funkcija je spet povsem preprosta, zato je vaša naloga tokrat predvsem, da poiščete, kako se to dela, jo razumete (narišite na list štiri točke in poglejte, kako deluje trik - saj je preprosto!) in jo primerno uporabite.

Prva funkcija temelji na predznaku kartezičnega produkta. Druga opazuje orientacijo trikotnikov. Kako to deluje ... razmislite, posurfajte.

def ccw(x1, y1, x2, y2, x3, y3): return (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1) >= 0 def se_sekata(x1, y1, x2, y2, x3, y3, x4, y4): return ccw(x1, y1, x3, y3, x4, y4) != ccw(x2, y2, x3, y3, x4, y4) and \ ccw(x1, y1, x2, y2, x3, y3) != ccw(x1, y1, x2, y2, x4, y4)

Za oceno 9: Spet neko vraževerje

Napiši metodi previdni_premik(smer, razdalja) in previdno_sekaj(x, y), ki sta podobni metodama premik in sekaj_do, vendar čebela, preden naredi karkoli, preveri, ali bi s takšnim premikanjem oz. sekanjem prečkala kako pot, ki jo je že preletela (torej, ali bi novi segment sekal katerega od starih). V tem primeru ukaz ignorira - zahtevana pot se ne opravi, ne nariše, ne zapomni in ne upošteva v preleteni razdalji.

Metoda previdni_premik bo najprej izračunala koordinate cilja (ker mora taisto reč delati tudi običajni premik smo dali ta skupni del v ločeno funkcijo izracunaj_koord, potem pa pokliče kar previdno_sekaj.

Metoda previdno_sekaj gre prek vseh preteklih segmentov in če najde kakega, s katerim se novi segment seka, se vrne (return), ne da bi kaj risala in kam šla. Sicer pa kliče sekaj_do, da se premakne, kamor je treba, ter zabeleži novi segment in poveča razdaljo.

Popaziti je potrebno še na tole malenkost: če si segmenta delita kako točko, bomo rekli, da se ne sekata. Ali si delita kako točko, izvemo tako, da zložimo vse štiri točke v množico; če ima ta štiri elemente, skupnih točk ni in preverjamo sekanje.

Mimogrede omenimo, da je to, kar počnemo v tej nalogi, del širše znanosti, ki ji pravimo računska geometrija. V tej nalogi (in tej rešitvi) smo spregledali marsikateri pomemben detajl, situacijo, na katero bi morali, če bi šlo zares popaziti. Vendar to ne sodi v Programiranje 1...

def previdni_premik(self, smer, velikost): x1, y1 = self.izracunaj_koord(smer, velikost) self.previdno_sekaj(x1, y1) def previdno_sekaj(self,x1, y1): for (x2, y2), (x3, y3) in self.segmenti: if len({(self.x, self.y), (x1, y1), (x2, y2), (x3, y3)}) == 4 and \ se_sekata(self.x, self.y, x1, y1, x2, y2, x3, y3): return self.sekaj_do(x1, y1)

Za oceno 10: Pokvarjena čebela

Napiši metodo oberi(cvetovi). Metoda dobi seznam cvetov, ki jih je potrebno obrati. Podani so s seznamom, ki vsebuje terke (x, y). Čebela se najprej prežarči do enega od cvetov (do katerega, lahko izbereš sam), nato pa leta od enega do drugega (z metodo sekaj_do.

Problem je tule: čebela mora obrati vse cvetove, pri čemer naredi en korak manj, kolikor je cvetov (če je potrebno obrati 10 cvetov, se prežarči do prvega, nato pa v devetih korakih obere naslednjih devet cvetov). Vendar ima čebela pokvarjen volan in ne more nikoli nikoli zavijati levo. To ne pomeni, da ne more leteti na levo - lahko, le zavija lahko samo na desno. Da bi letela levo, mora dovoljkrat zaviti desno.

Namig: cvetove bo obrala v (nekakšni) spirali. Vendar ne glej razdalj od (nekakšnega) središča, saj ti to ne bo veliko pomagalo. Nemara pa bo pomagala literatura v zvezi s konveksnimi ovojnicami, konkretno, Grahamovo skeniranje. Ampak ne točno to, saj ne iščemo ravno konveksne ovojnice. Pač pa v vsakem koraku iščemo cvet, ki je najbolj na levi od vseh cvetov, ki so še ostali - ne najbolj na levi v absolutnih koordinatah, temveč najbolj na levi glede na to, kam je trenutno obrnjena čebela.

V dodatnih domačih nalogah in teh za višje ocene se letos pogosto pozabavamo s kakim bolj algoritmičnim problemom. Ta je že ena takšnih. Rešitev je v bistvu preprosta: v vsakem koraku moramo zaviti čim manj desno. Začnemo pri točki, ki je najbolj levo in gremo navzgor. Med ostalimi točkami poiščemo tisto, ki je (glede na trenutno smer!) najbolj leva (saj bomo v tem primeru zavili najmanj desno) in gremo proti njej. Ko prispemo do nje, med ostalimi spet poiščemo najbolj levo ... Vsakič, ko obiščemo točko, jo odstranimo s seznama. Reč ponavljamo, dokler točk ne zmanjka.

Katera točka je najbolj leva, glede na trenutno smer, nam pove skalarni produkt med trenutno smerjo in smerjo do nove točke.

Najprej pripravimo funkcijo popmin, ki kot argument dobi funkcijo in seznam. Med elementi seznama poišče tistega, pri katerem vrne podana funkcija najmanjšo vrednost. Ta element pobriše s seznama in ga vrne. Če ji namesto funkcije podamo None, vrne najmanjši element seznama.

def popmin(f, s): naj_i = 0 naj_x = f(s[0]) if f else s[0] for i, e in enumerate(s): ex = f(e) if f else e if ex < naj_x: naj_x, naj_i = ex, i return s.pop(naj_i)

Preostanek je funkcija, ki izvaja algoritem, ki smo ga opisali zgoraj. Funkcija kot_do vrne kot med prejšnjim in potencialnim novim segmentom; uporabimo jo zato, da jo podamo popminu.

def oberi(self, cvetovi): def kot_do(pt): x1, y1 = pt lnx, lny = x1 - self.x, y1 - self.y dist = sqrt(lnx ** 2 + lny ** 2) return -(dx * lnx + dy * lny) / dist, dist neobrano = cvetovi[:] nx, ny = popmin(None, neobrano) self.prezarci(nx, ny) dx, dy = 0, -1 while neobrano: nx, ny = popmin(kot_do, neobrano) dx, dy = nx - self.x, ny - self.y ld = sqrt(dx ** 2 + dy ** 2) dx, dy = dx / ld, dy / ld self.sekaj_do(nx, ny)

Razmisli, zakaj je funkcija kot_do definirana znotraj metode oberi! Kaj bi se zgodilo, če bi jo postavili ven iz nje? Tole je v resnici zelo zanimiva reč...