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.
program = [[instr, int(op)]
for instr, op in map(str.split, open("input.txt"))]program[:6][['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):
pc = 0
acc = 0
visited = set()
while pc not in visited and pc < len(program):
visited.add(pc)
instr, arg = program[pc]
if instr == "jmp":
pc += arg
continue
if instr == "acc":
acc += arg
elif instr == "nop":
pass
pc += 1
return acc, pc >= len(program)Blok
elif instr == "nop":
passoč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.
last_acc, _ = execute(program)
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:
instr = mem[0]
if instr in nop_jmp:
mem[0] = (nop_jmp - {instr}).pop()
acc, ok = execute(program)
if ok:
print(acc)
break
mem[0] = instr640