Day 08: Handheld Halting

(Povezava na nalogo)

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.

Branje podatkov

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.

Simulacija procesorja

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":
            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.

Prvi del

last_acc, _ = execute(program)
print(last_acc)
1528

Drugi del

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] = instr
640