Imamo procesor z enim samim registrom in tremi ukazi.
add op
poveča register za podano vrednost,
jmp op
je relativni skok za podano razdaljo,
nop op
ne naredi ničesar.
Podan je program v obliki
nop +0
acc +1
jmp +4
acc +3
jmp -3
acc -99
acc +1
jmp -4
acc +6
Program se zacikla. Prva naloga je ugotoviti vrednost registra ob
prvem ponovljenem ukazu. Druga naloga je ugotoviti, kateri
jmp
je potrebno zamenjati v nop
ali obratno,
tako da se program izteče, to je, poskuša izvesti ukaz, ki je ontran
programa. Naloga je, spet, poiskati vrednost registra v trenutku, ko se
to zgodi.
Najprej razkosamo vse vrstice na dvoje. To storimo z
map(str.split, open("input.txt"))
. map
, kot
morda vemo, ki prejme dva elementa, funkcijo in generator. Nato vsakem
elementu, ki ga vrne generator, pokliče funkcijo in vrača (kot
generator) njene rezultate.
Kaj je str.split
, pa vemo: nevezana metoda
split
razreda str
. Če tega stavka ne razumemo,
se lahko o tem poučimo ob rešitvi dneva 6.
Čez map
bomo šli s for zanko:
for instr, op in map(str.split, open("input.txt"))
. Te
instr
in arg
zlagamo v pare, ki pa jih -
zaradi kasnejše rabe - ne bomo shranili v terko, temveč v seznam, pri
čemer op
spremenimo v int
, torej
[instr, int(op)]
. Vse skupaj zložimo v seznam, ki
predstavlja naš par.
= [[instr, int(op)]
program for instr, op in map(str.split, open("input.txt"))]
6] program[:
[['jmp', 232],
['acc', 21],
['nop', 120],
['jmp', 239],
['acc', 18],
['acc', 41]]
Nič posebnega, je pa kratko in elegantno.
Ta ni popolnoma nič posebnega. Vedno, ko simuliramo procesor (lani je
bilo to potrebno početi v polovici nalog; procesor je bil vedno boljši
in naloge vedno zanimivejše), potrebujmo programski števec
(program counter) in akumulator
(accumulator), pri nas bo sta to pc
in
acc
. V tej konkretni nalogi pa potrebujemo seznam že
obiskanih lokacij (visited
), da bomo lahko zaznali prvo, ki
se ponovi.
Program bo tekel, dokler se lokacija še ni ponovila in je programski števec še znotraj programa.
V zanki pa imamo tri if
-e, ki ustrezajo trem ukazom. Pri
tem bodimo pozorni, da jmp
spremeni pc
in s
continue
preskoči ostanek, medtem ko se po preostalih
ukazih izvede tudi pc += 1
. Če bomo morali procesor
simulirati še v kateri nalogi, bo tega še veliko, saj bomo najbrž dobili
tudi pogojne skoke.
Funkcija vrne dve stvari: pove vrednost akumulatorja in ali se je program ustavil.
def execute(program):
= 0
pc = 0
acc = set()
visited while pc not in visited and pc < len(program):
visited.add(pc)= program[pc]
instr, arg if instr == "jmp":
+= arg
pc continue
if instr == "acc":
+= arg
acc elif instr == "nop":
pass
+= 1
pc
return acc, pc >= len(program)
Blok
elif instr == "nop":
pass
očitno ne naredi ničesar in je nepotreben. Vendar mi je všeč, da ga napišemo, saj je tako očitno, da ta možnost obstaja in da je nismo pozabili.
= execute(program)
last_acc, _ print(last_acc)
1528
Drugi del tudi ni nič posebnega, razen tega, da se lahko izživljamo s
tem, kako bomo spremenili nop
v jmp
in
obratno.
= {"nop", "jmp"}
nop_jmp for mem in program:
= mem[0]
instr if instr in nop_jmp:
0] = (nop_jmp - {instr}).pop()
mem[= execute(program)
acc, ok if ok:
print(acc)
break
0] = instr mem[
640