Ker bo jutri ravno božič (no, če smo natančni, божић, Рождество Христово), je ravno še čas za nalogo z božičkom. (Čeprav vso stvar dodatno zaplete dejstvo, da "božiček" nima popolnoma nič s pravoslavci, saj so ga izumili protestanti, ko so ukinili svetega Miklavža, saj nimajo svetnikov.)

Testi

Testi: testi-bozicek-in-parkelj.py

Ogrevalna naloga

Napiši razred Mesto.

• Konstruktor ne dobi nobenih argumentov. Kaj naredi, je tvoja stvar; narediti mora vse, kar je potrebno, da bodo delovale ostale metode.
• Metoda obdaruj(x, y), zabeleži, da je hiša na koordinatah (x, y) prejela darilo.
• Metoda je_obdarovana(x, y) vrne True, če je hiša na koordinatah (x, y) prejela darilo; False, če ga ni.
• Metoda vse_obdarovane() vrne množico koordinat vseh obdarovanih hiš.

Primer:

>>> m = Mesto()
>>> m.obdaruj(5, 1)
>>> m.obdaruj(42, 2016)
>>> m.je_obdarovana(1, 1)
False
>>> m.je_obdarovana(42, 2016)
True
>>> m.vse_obdarovane()
{(5, 1), (42, 2016)}

Rešitev

Kakšne podatke mora shranjevati Mesto? Kaj mora početi? Znati mora povedati, ali je bila določena hiša obdarovana in znati mora vrniti množico obdarovanih hiš. Očitno si mora torej zapomniti, katere hiše so bile obdarovane. In najbolj praktično bo, da to shrani v množici, katere elementi bodo koordinate (pari števk) obdarovanih hiš. Zakaj ravno množica? Malo zaradi operacije, ki jo bomo izvajali na njej - je_obdarovana bomo potem naredili tako, da bomo vprašali, ali množica vsebuje določen element in to Python naredi veliko hitreje, kot če bi vprašali, ali seznam vsebuje določen element. Malo pa zato, ker je tako bolj praktično, saj bo lahko vse_obdarovane vračala kar to množico.

class Mesto:
    def __init__(self):
        self.obdarovane = set()

    def obdaruj(self, x, y):
        self.obdarovane.add((x, y))

    def je_obdarovana(self, x, y):
        return (x, y) in self.obdarovane

    def vse_obdarovane(self):
        return self.obdarovane

Obvezna naloga

Napiši razred Bozicek.

• Konstruktor kot argument dobi mesto, ki mu bo delil darila. Božiček je v začetku na koordinatah (0, 0).
• Metoda premik(c) kot argument prejme znak v, ^, < ali > in prestavi božička za eno "polje" dol, gor, levo in desno. Koordinata y se tokrat spreminja tako, da narašča navzgor (premik ^ jo poveča in v zmanjša).
• Metoda premiki(pot) kot argument prejme niz, sestavljen iz teh znakov in premakne božička po tej poti.
• Metoda obdaruj() obdaruje hišo na koordinatah, na katerih se trenutno nahaja božiček.

Primer:

>>> kranj = Mesto()
>>> tone = Bozicek(kranj)
>>> tone.premik(">")
>>> tone.premik("^")
>>> tone.obdaruj()
>>> kranj.vse_obdarovane()
{(1, 1)}
>>> tone.premiki(">>>>>>>>vvv")
>>> tone.obdaruj()
>>> kranj.vse_obdarovane()
{(9, -2), (1, 1)}

Ne spreglej, da metoda obdaruj nima argumentov (razen self).

Poleg tega napiši razred HitriBozicek, ki je izpeljan iz razreda Bozicek. Njegov konstruktor poleg mesta prejme tudi hitrost. Hitri božiček se od navadnega razlikuje po tem, da se ne premika za eno polje temveč za toliko, kolikor je njegova hitrost, ki smo jo podali v konstruktorju.

Primer:

>>> peter = HitriBozicek(kranj, 3)
>>> kranj.vse_obdarovane()
{(9, -2), (1, 1)}
>>> peter.obdaruj()
>>> kranj.vse_obdarovane()
{(0, 0), (9, -2), (1, 1)}
>>> peter.premik(">")
>>> peter.obdaruj()
>>> kranj.vse_obdarovane()
{(3, 0), (0, 0), (9, -2), (1, 1)}
>>> peter.premiki(">^")
>>> peter.obdaruj()
>>> kranj.vse_obdarovane()
{(3, 0), (0, 0), (9, -2), (1, 1), (6, 3)}

Peter deluje v istem mestu kot Tone, zato dodaja v isto množico obdarovanih hiš. Mimogrede ne spreglej: gre za množico, zato vrstni red ni določen.

Rešitev

Ta naloga je bila koristna tudi zame, saj me je poučila o tem, kje imate težave. Kot sem napisal na forumu: Bozicek ni izpeljan iz Mesto. Če bi bil, bi to pomenilo, da je božiček neka posebna vrsta mesta. Vendar ni.

Kaj vas je zavedlo, je jasno, vendar na to pri sestavljanju naloge nisem pomislil: oba imata metodo obdaruj. Vendar je to precej drugačna metoda. Tista v Mesto zabeleži, da je določena hiša obdarovana. Tista v Bozicek "sporoči" mestu, da je določena hiša obdarovana.

Za kaj gre, bo tokrat lažje videti iz programa.

class Bozicek:
    def __init__(self, mesto):
        self.x = self.y = 0
        self.mesto = mesto

    def premik(self, c):
        self.x += (c == ">") - (c == "<")
        self.y += (c == "^") - (c == "v")

    def premiki(self, pot):
        for c in pot:
            self.premik(c)

    def obdaruj(self):
        self.mesto.obdaruj(self.x, self.y)

Kaj si mora zapomniti Bozicek? Dve stvari: koordinate, na katerih je, in mesto, ki ga obdaruje.

Koordinate in metode, povezane z njim, bi morale biti preproste, saj niso tako zelo drugačne od želve in drugih nalog, ki smo jih že delali.

No, pri premik smo se malo poigrali z logičnimi izrazi. c == ">" je True ali False, kar je isto kot 1 ali 0. K self.x bomo torej prišteli 1, če je c == ">" in odšteli 1, če je c == "<". Sicer pa bomo prišteli in odšteli 0.

Problem je (sicer čisto kratka in preprosta - potem, ko jo vidiš) metoda obdaruj. V konstruktorju si zapomnimo mesto - shranimo ga v self.mesto. Metoda obdaruj mora potem poklicati metodo obdaruj tega mesta, kot koordinate hiše pa podati lastne (božičkove) koordinate.

HitriBozicek pa je potem relativno preprosta reč. V konstruktorju si zapomni še hitrost, mesto pa prepusti podedovanemu konstruktorju.

class HitriBozicek(Bozicek):
    def __init__(self, mesto, hitrost):
        super().__init__(mesto)
        self.hitrost = hitrost

    def premik(self, c):
        self.x += self.hitrost * ((c == ">") - (c == "<"))
        self.y += self.hitrost * ((c == "^") - (c == "v"))

Pri premik smo se spet malo igrali.

Imel sem tudi genialno idejo, kako nagoljufati premik. Kot veliko mojih genialnih idej, tudi ta ne deluje. :) Pokazati jo moram, ker ne deluje na zelo poučen način.

class HitriBozicek(Bozicek):
    def __init__(self, mesto, hitrost):
        super().__init__(mesto)
        self.hitrost = hitrost

    def premik(self, c):
        self.premiki(c * self.hitrost)

Recimo, da imamo hitrega božička, katerega hitrost je 3. Recimo, da pokličemo premik("<"). Izvedemo ga lahko preprosto tako, da pokličemo premiki("<<<").

Problem je v tem, da premiki pokliče premik. Vendar premiki razreda Bozicek poklice premik. A kot smo slišali na predavanjih (žal pa jaz nisem poslušal, temveč govoril; ali pa ... no ja, človek se zmoti ;) bo premiki poklical metodo premik hitrega božička. Ta pa pokliče premiki. Ki pokliče premik. No, tole je situacija, v kateri tudi jaz ne maram rekurzije. :(

Se da to popraviti? Poskrbeti, da premiki ne bi poklicala premik? Ne zlepa.

V resnici bi morali razreda obrniti: Bozicek bi moral biti posebna vrsta HitregaBozicka. Hitri božiček se premika s poljubno hitrostjo, običajni pa je tak, pri katerem je ta hitrost vedno 1.

Dodatna naloga

Nekateri otroci niso bili pridni.

Napiši funkcijo parkelj(x, y, hise), ki prejme koordinate, na katerih se nahaja parkelj, in koordinate vseh hiš, kjer živijo otroci, ki jim je potrebno vzeti darila. Funkcija naj vrne pot, ki pelje parklja mimo vseh teh hiš. Parkelj naj obišče hiše v podanem vrstnem redu. V okviru tega pa naj prehodi najkrajšo možno pot.

>>> parkelj(5, 2, [(8, 2), (8, -4), (5, -1)])
'>>>vvvvvv<<<^^^'
>>> parkelj(5, 2, [(5, 2), (5, 5)])
'^^^'

Rešitev ni unikatna. Klic parkelj(5, 2, [(6, 3)]), recimo, lahko vrne ">^" ali "^>". Pravilno je oboje.

Pravzaprav noben otrok v mestu ni bil priden.

Napiši funkcijo hitri_parkelj(x, y, mesto), ki prejme parkljeve začetne koordinate in objekt, ki predstavlja Mesto. Funkcija naj vrne najkrajšo pot, po kateri lahko parkelj pobere vsa darila. Tudi hiše naj obiskuje v takšnem vrstnem redu, da bo njegova pot najkrajša.

Namig: poglej funkcijo itertools.permutations. Sicer pa smo podobno nalogo že enkrat reševali.

>>> n = Mesto()
>>> n.obdaruj(0, 1)
>>> n.obdaruj(2, 0)
>>> n.obdaruj(0, 10)
>>> hitri_parkelj(0, 0, n)
'>><<^^^^^^^^^^'

Pravilna rešitev je tudi '>>^<<^^^^^^^^^'. Tule je pomembno, da gre najprej v hišo (2, 0) in šele nato v (0, 1), sicer bo pot dva koraka daljša.

Rešitev

def parkelj(x, y, hise): return "".join("<" * max(x0 - x1, 0) + ">" * max(x1 - x0, 0) + "v" * max(y0 - y1, 0) + "^" * max(y1 - y0, 0) for (x0, y0), (x1, y1) in zip([(x, y)] + list(hise), hise))

Iti moramo prek vseh parov (x0, y0), (x1, y1). Namesto običajnega trika, s katerim dobimo zaporedne pare (zip(s, s[1:])), jih zdaj sestavimo tako, da na začetek enega od seznamov potisnemo začetne koordinate.

Za vsak par sestavimo niz, ki nas spravi od ene hiše do druge.

"<" * max(x0 - x1, 0) + ">" * max(x1 - x0, 0) +
"v" * max(y0 - y1, 0) + "^" * max(y1 - y0, 0)

Levo gremo tolikokrat, kolikor je x0 - x1. Če je to slučajno negativno, pa gremo levo za 0. Podobno opravimo z ostalimi. Nato jih z "".join sestavimo v en sam niz.

Hitrega parklja pa le napišimo. Razloži si ga naj, kdor hoče.

def dolzina_poti(x, y, hise):
    return sum(abs(x0 - x1) + abs(y0 - y1)
               for (x0, y0), (x1, y1) in zip([(x, y)] + list(hise), hise))

from itertools import permutations
from functools import partial
def hitri_parkelj(x, y, mesto):
    return parkelj(x, y, min(permutations(mesto.vse_obdarovane()),
                             key=partial(dolzina_poti, x, y)))