Advent of Code 2020 - Day 8 Handheld Halting

day08_handheld_halting.cpp

#include <iostream>
#include <sstream>
#include <string>

#include "day08_machine.h"

using namespace std;

#define endl '\n'
#define pb push_back

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    Machine gameboy;

    // inputs read
    string line, operation;
    int number;
    while (getline(cin, line)) {
        istringstream tokens(line);
        tokens >> operation >> number;
        gameboy.instructions.pb(Instruction(operation, number));
    }

    // part 1
    while (true) {
        auto& ins = gameboy.curr();
        if (ins.called) break;
        gameboy.execute();
    }
    cout << "Part 1: " << gameboy.acc << endl;

    // part 2
    gameboy.reset();
    while (!gameboy.finished()) {
        auto& ins = gameboy.curr();
        if (ins.swappable()) {
            ins.swap();
            if (gameboy.boot()) {
                break;
            } else {
                ins.swap();
            }
        }
        gameboy.execute();
    }
    cout << "Part 2: " << gameboy.acc << endl;
    return 0;
}

day08_machine.h

#include <cassert>
#include <set>
#include <string>
#include <vector>

using namespace std;

struct Instruction {
    string operation;
    int number;
    bool called;

    Instruction(string op, int num) {
        operation = op;
        number = num;
        called = false;
    }

    bool swappable() {
        return operation == "jmp" || (operation == "nop" && number != 0);
    }

    void swap() {
        assert(swappable());
        operation = (operation == "nop" ? "jmp" : "nop");
    }
};

struct Machine {
    int acc;
    int idx;
    vector<Instruction> instructions;

    Machine() { acc = idx = 0; }

    bool boot() {
        int index = idx, accum = acc;
        set<int> ins_called;

        bool valid = true;
        while (!finished()) {
            if (instructions[idx].called) {
                valid = false;
                break;
            }
            ins_called.insert(idx);
            execute();
        }
        if (valid) return true;

        // revert state back to boot start
        idx = index;
        acc = accum;
        for (auto i : ins_called) instructions[i].called = false;
        return false;
    }

    void execute() {
        assert(idx < instructions.size());
        auto &ins = instructions[idx];
        ins.called = true;
        if (ins.operation == "nop") {
            idx++;
        } else if (ins.operation == "jmp") {
            idx += ins.number;
        } else {
            acc += ins.number;
            idx++;
        }
    }

    bool finished() {
        return idx >= instructions.size();
    }

    Instruction &curr() {
        return instructions[idx];
    }

    void reset() {
        acc = idx = 0;
        for (auto &ins : instructions) ins.called = false;
    }
};