Boti

Testi

Testi: testi-boti.zip

Pravila

Osnova naloge prihaja z Advent of Code, Day 10, le da tam ni bilo predpisano, kako in v katerem jeziku jo je potrebno reševati. Originalni nalogi ustreza funkcija za oceno 8.

Robotki si podajajo čipe s številkami. Navodila so zapisana takole.

bot 1 gives low to output 1 and high to bot 0
value 5 goes to bot 2
bot 0 gives low to output 2 and high to output 0
bot 2 gives low to bot 1 and high to bot 0
value 3 goes to bot 1
value 2 goes to bot 2

Navodila se ne izvajajo (nujno) v takšnem vrstnem redu. Vsak robot vedno počaka, da ima dva čipa. Ko ju ima, ju bo oddal drugim robotom ali pa v eno od izhodnih škatel, tako kot velevajo navodila. Tule se zgodi tole.

• V začetku ima robot 1 čip 3, robot 2 pa čipa 2 in 5.
• Ker ima robot 2 dva čipa, odda čip z manjšo številko (2) robotu 1 in čip z večjo številko (5) robotu 0.
• Zdaj ima robot 1 dva čipa, namreč 3 in 2. Manjšega (2) da na izhod 1, večjega (3) pa robotu 0.
• In zdaj ima robot 0 dva čipa, namreč 3 in 5. Manjšega (3) da na izhod 2 in večjega (5) na izhod 0.

Vrednosti na izhodih so torej [5, 2, 3].

Shranjevanje

Trenutno stanje robotov bomo shranjevali v slovarju (navadno ga bomo imenovali bots). Da bo preprosteje, bo to defaultdict. Ključi so številke robotov, vrednosti pa seznami z 0, 1 in 2 elementoma, ki pomenijo številke čipov. Začetno stanje v gornjem primeru bi opisali z {1: [3], 2: [5, 2]} ali {1: [3], 2: [2, 5]} ali {0: [], 1: [3], 2: [5, 2]}. Vsi trije zapisi so enakovredni.

Stanje na izhodih je predstavljeno s seznamom, katerega dolžina je enaka število izhodov. Elementi seznama so None ali pa številka, ki je na izhodu. Na vsakem izhodu je lahko le eno število.

Kaj počnejo roboti, je shranjeno v slovarju, katerega ključi so številke robotov vrednosti pa par (terka) dveh parov (terk). Razložimo kar na primeru: gornja pravila bi zapisali kot

{1: (("output", 1), ("bot", 0)),
 0: (("output", 2), ("output", 0)),
 2: (("bot", 1), ("bot", 0))}

Ključi so številke robotov. Pripadajoča terka je sestavljena iz dveh elementov, ki povesta, kam gre čip z nižjo in kam čip z višjo številko. Terka je spet par.

Prva vrstica torej pravi, da robot 1 da manjšo številko na izhod 1, ("output", 1), večjo pa robotu 0 ("bot", 0).

Še en primer

V example2.txt so navodila

value 1 goes to bot 1
value 2 goes to bot 1
value 3 goes to bot 2
value 4 goes to bot 2
value 5 goes to bot 3
value 6 goes to bot 6
bot 1 gives low to bot 3 and high to bot 4
bot 2 gives low to bot 4 and high to output 0
bot 3 gives low to output 5 and high to bot 5
bot 4 gives low to bot 5 and high to bot 6
bot 5 gives low to output 1 and high to bot 7
bot 6 gives low to bot 7 and high to output 4
bot 7 gives low to output 2 and high to output 3

ki pomenijo tole

Začetno stanje predstavimo z

bots = {1: [1, 2], 2: [3, 4], 3: [5], 6: [6]}

navodila pa z

instructions = {1: (('bot', 3), ('bot', 4)),
                2: (('bot', 4), ('output', 0)),
                3: (('output', 5), ('bot', 5)),
                4: (('bot', 5), ('bot', 6)),
                5: (('output', 1), ('bot', 7)),
                6: (('bot', 7), ('output', 4)),
                7: (('output', 2), ('output', 3))}

Za oceno 6

Napiši funkcijo read_file(filename), ki prebere datoteko s podanim imenom in vrne par (terko). Prvi element te terke je začetno stanje, drugi pa navodila. Glej gornja slovarja.

Napiši funkcijo highest_output(instructions), ki prejme pravila (npr. gornji slovar) in vrne največjo število izhoda. V gornjem primeru je to 5.

Rešitev

V najpreprostejši rešitvi vrstico za vrstico beremo datoteko. Razbijemo jo glede na presledke. Če je prva beseda bot, nas zanimajo deli z indeksi 1, 6, 11, 5 in 50, saj vsebujejo številko bota, kdo dobi čip z nižjo številko (bot ali output) in njegovo številko, ter isto za čip z višjo številko. To zložimo v instructions. Sicer, torej če prva beseda ni bot, vrstica pove, kdo v začetku dobi določen čip.

def read_file(filename):
    instructions = {}
    bots = defaultdict(list)
    for line in open(filename):
        line = line.strip().split()
        if line[0] == "bot":
            bot = int(line[1])
            lowout = line[5]
            low = int(line[6])
            highout = line[10]
            high = int(line[11])
            instructions[bot] = ((lowout, low), (highout, high))
        else:
            bot = int(line[5])
            chip = int(line[1])
            bots[bot].append(chip)
    return bots, instructions

Če bi hoteli tole izvesti lepše, bi uporabili regularne izraze. O njih se pri tem predmetu nismo in ne bomo učili.

Številko največjega izhoda dobimo tako, da gremo prek vseh navodil in če določen bot kaj daje na kakšen izhod, katerega številka je največje od največje, ki smo jo našli doslej, si jo zapomnimo.

def highest_output(instructions):
    highest = 0
    for wheres in instructions.values():
        for out, whom in wheres:
            if out == "output" and whom > highest:
                highest = whom
    return highest

Opazujte, kako sta postavljeni zanki for. Prva gre čez vrednosti v slovarju, saj nas tokrat zanimajo samo te. Znotraj te gremo čez izhoda posamičnega bota. Le dva sta, a vseeno raje napišemo kar zanko namesto dveh if-ov.

Na prvi pogled se morda zdi, da je tole popolnoma nepomembno. A ni. Tudi resni programerji težko pišemo zapletene programe. Pravzaprav se dobri programerji od slabih razlikujejo po tem, da dobri pišejo preprostejše programe. Ali, da ne pretiravam: za isto nalogo bo dober programer napisal preprostejši program. Razlog, da se bo slab programer zmotil, dober pa ne, je prav v tem, da bo program, ki ga piše dobri, preprostejši. Kadar poskušam pisati programe, kakor bi jih napisal začetnik, se bom tudi sam zmotil veliko večkrat.

Zato so te stvari pomembne.

Za oceno 7

Napiši funkcijo execute(bots, outputs, bot, instructions), ki prejme trenutno stanje robotov (bots), trenutno stanje izhodov (na primer [None, None, 4, None, 3]), številko robota in slovar s pravili.

Funkcija naj najprej preveri, če ima robot dva čipa. Če ju nima, vrne False. Če ju ima, naj naredi, kar pravi pripadajoče pravilo: manjši čip da ustreznemu robotu (dodamo ga v robotov seznam v bots) oziroma na ustrezni izhod (spremeni ustrezni element outputs). Enako naredi z večjim čipom. Poleg tega "odvzame" robotu bot njegov čip. Na koncu vrne True.

Če imamo, recimo

bots = {0: [42], 1: [13, 60], 2: [61, 15], 3: [], 4: [16, 62]})
instructions = {0: (("output", 1), ("bot", 3)),
                1: (("output", 2), ("bot", 0)),
                2: (("bot", 3), ("bot", 0)),
                3: (("output", 0), ("output", 3)),
                4: (("bot", 6), ("bot", 5))}
outputs = [None, None, None, None]

in pokličemo

`execute(bots, outputs, 2, instructions)`

funkcija vrne True in spremeni bots v

{0: [42, 61], 1: [13, 60], 2: [], 3: [15], 4: [16, 62]})

saj da manjšo številko (15) robotu 3, večjo (61) pa robotu.

Če bi namesto tega poklicali

`execute(bots, outputs, 1, instructions)`

pa se bots spremeni v

{0: [42, 60], 1: [], 2: [61, 15], 3: [], 4: [16, 62]})

in outputs v

[None, None, 13, None]

saj da manjšo številko (13) na izhod 2, večjo pa robotu 0.

Rešitev

Funkcija je tako očitna, da je skoraj ni kaj komentirati. Narediti mora le, kar piše v navodilih, ki so tako ali tako veliko daljša od funkcije.

Pač pa se nam splača pogledati, kako smo jih zapisali.

def execute(bots, outputs, bot, instructions):
    if len(bots[bot]) != 2:
        return False
    (lowout, low), (highout, high) = instructions[bot]
    lower, higher = sorted(bots[bot])
    if lowout == "output":
        outputs[low] = lower
    else:
        bots[low].append(lower)
    if highout == "output":
        outputs[high] = higher
    else:
        bots[high].append(higher)
    bots[bot] = []
    return True

Navodila dobimo z instructions[bot]. Ne s kakimi nepotrebnimi zankami prek slovarja.

Da se potem ne bi hecali s kakimi indeksi, jih tako razkopljemo v lepo poimenovane spremenljivke.

    (lowout, low), (highout, high) = instructions[bot]

Prav tako shranimo manjšo številko, ki jo ima bot, v lower, večjo v higher: uredimo seznam čipov, ki jih ima (sorted(bots[bot])) in ga razpakiramo.

Ko je tako vse lepo pripravljeno, sledijo le še if-i, ki določijo, kam dodamo kaj. Na koncu z bots[bot] = [] vzamemo robotu njegove čipe.

Za oceno 8

Napiši funkcijo run(bots, instructions), ki prejme začetno stanje robotov in odigra celoten proces ter vrne stanje izhodov. Če imamo

bots = {1: [3], 2: [5, 2]}
instructions = {1: (("output", 1), ("bot", 0)),
                0: (("output", 2), ("output", 0)),
                2: (("bot", 1), ("bot", 0))}

(primer pravil z začetka naloge) bo klic run(bots, instructions) vrnil [5, 2, 3].

Funkcija run sme spreminjati bots.

Nasvet: funkcije se loti takole. Najprej odkrij, koliko izhodov boš potreboval in pripravi ustrezen seznam izhodov (outputs iz gornjih primerov). Nato se preprosto sprehodi čez vse robote (npr. čez instructions(items) in za vsakega pokliči execute. Nekateri bodo vrnili False, ker nimajo dveh čipov, nekateri pa bodo vrnili True. Nato se ponovno sprehodi čez vse robote. In ponovno. In ponovno ... In tako naprej, dokler se ne zgodi, da čisto vsi roboti vrnejo False. Takrat si končal in lahko vrneš stanje izhodov.

Rešitev

Tole se da narediti na kup načinov. Eden je tale.

def run(bots, instructions):
    outputs = [None] * (highest_output(instructions) + 1)
    changes = True
    while changes:
        changes = False
        for bot in instructions:
            changes = changes or execute(bots, outputs, bot, instructions)
    return outputs

Brati ga začnimo pri jedru.

        changes = False
        for bot in instructions:
            changes = changes or execute(bots, outputs, bot, instructions)

Gremo prek vseh botov in si zapomnimo, ali je kdo kaj naredil.

Razširimo pogled za dve vrstici.

    changes = True
    while changes:
        changes = False
        for bot in instructions:
            changes = changes or execute(bots, outputs, bot, instructions)

Ono "jedro" ponavljamo in ponavljamo, dokler vsaj en bot kar naredi.

Preostane samo še to, da sestavimo in vrnemo outputs.

Gre tudi krajše, če se spomnimo generatorjev in funkcije any. Funkcija za oceno 8 je tako dolga štiri vrstice, od katerih ena ne naredi ničesar!

def run(bots, instructions):
    outputs = [None] * (highest_output(instructions) + 1)
    while any(execute(bots, outputs, bot, instructions) for bot in instructions):
        pass
    return outputs

Če je to videti čudno (prazna zanka! vse njeno meso je v pogoju!), lahko obrnemo v neskončno zanko.

def run(bots, instructions):
    outputs = [None] * (highest_output(instructions) + 1)
    while True:
        if not any(execute(bots, outputs, bot, instructions) for bot in instructions):
            return outputs

Pa še na mnogo drugih načinov bi se dalo igrati s tem. :)

Za oceno 9

Napiši funkcijo count_paths(bot, instructions), ki vrne število poti, po katerih gre lahko številka od bota s številko bot do kateregakoli izhoda.

V primeru example2.txt (gornja slika) obstajajo tri poti od 5 do izhoda (5-1, 5-7-2, 5-7-3). Različnih poti od 4 do izhoda je 6 (4-5-1, 4-5-7-2, 4-5-7-3, 4-6-7-2, 4-6-7-3, 4-6-4).

Funkcija bo testirana le na manjših vhodih (example.txt, example2.txt) in ne na velikem. Seveda pa se lahko potrudiš in jo poskusiš napisati tako, da bo delovala tudi na input.txt. Poti od bota 97 do raznih izhodov je 24 milijard (točneje, 24466267020).

Rešitev

Najprej nekoliko daljša rešitev. Gremo prek vseh izhodov bota, for out, where in instructions[bot]. Če vodi izhod v output (out == "output"), to prispeva eno pot (paths += 1). Če vodi k drugemu botu, je to toliko poti, kolikor jih gre od tega bota (paths += count_paths(where, instructions)).

def count_paths(bot, instructions):
    paths = 0
    for out, where in instructions[bot]:
        if out == "output":
            paths += 1
        else:
            paths += count_paths(where, instructions)
    return paths

Če vedmo, da je True isto kot 1 in da se logični izrazi računajo le, dokler je to potrebno in da je rezultat logičnega izraza tisto, kar se je izračunalo, v trenutku, ko je njegova vrednost postala znana, lahko napišemo

def count_paths(bot, instructions):
    paths = 0
    for out, where in instructions[bot]:
        paths += out == "output" or count_paths(where, instructions)
    return paths

To pa je isto kot

def count_paths(bot, instructions):
    return sum(out == "output" or count_paths(instructions, where) for out, where in instructions[bot])

Kako se potruditi, da rešitev deluje tudi za velike mreže, je opisano spodaj.

Za oceno 10

Napiši funkcijo bots_on_path(output, instructions), ki pove, kateri roboti sodelujejo pri računanju vrednosti na podanem vhodu output.

Pri računanju izhoda 4 na gornji sliki sodelujejo roboti 1, 2, 4 in 6. Roboti 3, 5 in 7 na izhod 4 nimajo vpliva.

Rešitev

Ta naloga je ravno obratna kot naloga za oceno 9. Slovar instructions, ki je bil obrnjen natančno tako, kot smo ga potrebovali pri oceni 9 (in tudi 8 in 7), je za tole nalogo nepraktičen. Omogoča nam, da hitro odkrijemo komu nek bot daje, ne pa od koga nekaj dobi. Obrnimo ga. Da bo pregledneje, to storimo v ločeni funkciji.

def backwards(instructions):
    backs = defaultdict(list)
    for bot, ((lowout, lower), (highout, higher)) in instructions.items():
        if lowout == "bot":
            backs[lower].append(bot)
        if highout == "bot":
            backs[higher].append(bot)
    return backs

Prav tako napišimo ločeno funkcijo, ki bo povedala, kateri bot daje čip na iskani izhod.

def bot_to_output(output, instructions):
    for bot, ((lowout, lower), (highout, higher)) in instructions.items():
        if lowout == "output" and lower == output or highout == "output" and higher == output:
            return bot

Zdaj lahko poskusimo napisati rekurzivno rešitev naloge.

Napišemo rekurzivno funkcijo, ki prejme bota, ne izhod, in obrnjen slovar, vrne pa množico botov na poti - vključno s samim seboj.

def bots_on_path_bot(bot, backs):
    bots = {bot}
    for bot in backs:
        bots |= backs[bot]
    return bots

Končno napišemo še funkcijo, ki jo zahteva naloga: bots_on_path pokliče gornjo funkcijo z ustreznimim argumenti - številko bota in obrnjenim slovarjem.

def bots_on_path(output, instructions):
    return bots_on_path_bot(bot_to_output(output, instructions), backwards(instructions))

Takšen stvari so delovale pri nalogah z rodbine. Funkcija bots_on_path_bot je praktično enaka funkciji, ki vrne vse člane rodbine. In tisto je delovalo, ne?

Tule gre nekaj fundamentalno narobe. Predstavljajmo si, da iščemo bote na poti (puščice so že obrnjene nazaj).

Bot 7 pokliče funkcijo za bota 5 in 6. Bot 5 in 6 pokličeta (vsak!) funkcijo za bote 3 in 4. Torej funkcijo pokličemo dvakrat za bota 3 in dvakrat za 4. V vsakem od teh štirih klicev se pokliče funkcija za 1 in 2. Funkcija za 1 štirikrat in za 2 štirikrat. Če bota 1 in 2 kličeta neke bote pred sabo, so ti poklicani že osemkrat. Številko klicev so torej podvoji na vsakem nivoju.

Gornja funkcija zato deluje le za preprostejše mreže.

Napišemo jo lahko nekoliko drugače, nerekurzivno.

def bots_on_path(output, instructions):
    bot = bot_to_output(output, instructions)
    backs = backwards(instructions)
    to_check = [bot]
    on_path = {bot}
    while to_check:
        bot = to_check.pop()
        for prebot in backs[bot]:
            if prebot not in on_path:
                on_path.add(prebot)
                to_check.append(prebot)
    return on_path

on_path vsebuje bote na poti, to_check pa tiste, na katere smo naleteli in jih še nismo pregledali.

V začetku je to_check bot, ki daje na iskani izhod.

Dokler je potrebno še kaj pogledati (while to_check), vzamemo to, kar je potrebno pogledati, iz seznama stvari, ki jih je potrebno pregledati. Pogledamo, kdo pošilja temu botu. Za vsakega pogledamo, ali ga še nismo videli. Če je tako, da dodamo med bote na poti in bote, ki jih je potrebno še pregledati.

Obstajajo še druge rešitve tega problema. Ker naletimo na praktično isto težavo pri čisto dodatni nalogi, si jih bomo ogledali tam.

Rešitev naloge za oceno 9 za velike mreže

Način za reševanje te naloge smo spoznali pri nalogi za oceno 10: nekako si zapomnimo, kaj smo že pregledali in tja ne rinemo več. Tule si bomo ogledali preprost pristop k temu: memoizacija.

Prej je bila funkcija takšna:

def count_paths(bot, instructions):
    return sum(out == "output" or count_paths(instructions, where) for out, where in instructions[bot])

V osnovi želimo tole:

cached = {}
def count_paths(bot, instructions):
    if bot not in cached:
    cached[bot] = sum(out == "output" or count_paths(whom, instructions) for out, whom in instructions[bot]) or 1
    return cached[bot]

Slovar cached kot ključe vsebuje argumente, s katerimi smo klicali funkcijo (konkretno, številke botov), kot vrednost pa število poti.

Funkcija preveri, ali je rezultat že v slovarju. Če ni, ga shrani v slovar. Nato vrne, kar je v slovarju.

Težava te funkcije je, da slovarja cached nikoli ne pobriše. Če kličemo count_paths za različne instructions, tega ne bo opazila. V slovar zato dodajmo podatek o tem, na katere instructions se nanaša: pod ključ None bomo shranili instructions.

cached = {None: None}
def count_paths(bot, instructions):
    if cached[None] is not instructions:
        cached.clear()
        cached[None] = instructions
    if bot not in cached:
        cached[bot] = sum(out == "output" or count_paths(whom, instructions) for out, whom in instructions[bot]) or 1
    return cached[bot]

Če se trenutni slovar ne nanaša na podane instructions (if cached[None] is not instructions), izpraznimo slovar (cached.clear()) in zabeležimo, da se bo poslej nanašal na ta navodila (cached[None] = instructions).

Tole deluje, ni pa prav učinkovito. Slovar zdaj hrani instructions. Ne sicer kopije, tako da to ne zahteva dodatnega pomnilnika. Vendar pa teh instructions morda ne potrebujemo več, zato nihče več ne ve zanje in bi Python že davno pospravil pomnilnik za njimi - vendar, ups, slovar cached "ve" za instructions.

def count_paths(bot, instructions):
    cached = {}
    def cp(bot):
        if bot not in cached:
            cached[bot] = sum(out == "output" or cp(whom) for out, whom in instructions[bot]) or 1
        return cached[bot]
    return count_paths0(bot)

Rekurzivna funkcija je zdaj cp, nahaja pa se znotraj funkcije count_paths. Funkcija count_paths pripravi slovar in pokliče cp, ki ga uporablja.

Ker je memoizacija tako uporabna stvar, ima Python že pripravljeno, kar potrebujemo zanjo. Funkcijo je potrebno "dekorirati" (dekoratorji so še ena stvar, ki jih bomo, tako kot regularne izraze, v tej nalogi le omenili, pri predmetu pa se z njimi ne bomo ukvarjali) z dekoratorjem lru_cache, ki jo ustrezno ovije in doda potrebne slovarje.

Dekorirati bi lahko poskušali kar prvotno funkcijo

from functools import lru_cache

@lru_cache(1000)
def count_paths(bot, instructions):
    return sum(out == "output" or count_paths(instructions, where) for out, where in instructions[bot])

Tole naj bi hranilo zadnjih 1000 različnih klicev funkcije v (skritem) slovarju, katerega ključ je terka z argumenti funkcije, vrednost pa vrednost, ki jo je vrnila funkcija.

Vendar tole ne gre, ker funkcija count_paths kot enega od argumentov dobi instructions, ta pa ne more biti ključ v slovarju. Znebiti se je torej potrebno tega argumenta. Prav to pa smo naredili v zadnji rešitvi zgoraj.

Najpreprostejša rešitev tega dodatnega izziva je tako

from functools import lru_cache

def count_paths1(bot, instructions):
    @lru_cache(1000)
    def cp(bot):
        return sum(out == "output" or cp(whom) for out, whom in instructions[bot])
    return cp(bot)