This is my solution to Advent of Code 2017, Day 8.
Problem description
The task is to model a machine which has an unspecified number of registers which are accessed by name and contain integer values. The machine executes instructions which can modify the register values if a comparison succeeds.
Each instruction consists of several parts: the register to modify, whether to increase or decrease that register's value, the amount by which to increase or decrease it, and a condition. If the condition fails, skip the instruction without modifying the register. The registers all start at 0. The instructions look like this:
b inc 5 if a > 1 a inc 1 if b < 5 c dec -10 if a >= 1 c inc -20 if c == 10
[…]
You might also encounter
<=
(less than or equal to) or!=
(not equal to).
Given a sequence of instructions as input, the output of the program should be
- the maximum register value at the end of execution
- the maximum value contained in any register at any time during execution
In the above example, these values are 1, and 10.
My code
My program works by parsing each line of the input to an Instruction
object which is passed to the execute
method of a Machine
object which evaluates the condition contained in the instruction and modifies its register values appropriately.
machine.h
#include <stdexcept>
#include <string>
#include <unordered_map>
class Machine {
public:
using RegisterName = std::string;
using RegisterValue = int;
struct Instruction {
enum class Operation { Inc, Dec };
enum class Comparison {
Equal, Unequal,
Less, LessEqual,
Greater, GreaterEqual
};
struct ParseError : public std::runtime_error {
ParseError(const std::string& what_arg);
};
static Operation to_operation(const std::string&);
static Comparison to_comparison(const std::string&);
// evaluate "a <cmp> b"
static bool evaluate(Comparison cmp, RegisterValue a, RegisterValue b);
Instruction() = default;
Instruction(const std::string& line);
friend std::istream& operator>>(std::istream&, Instruction&);
RegisterName target;
Operation operation;
RegisterValue operation_amount;
RegisterName source;
Comparison comparison;
RegisterValue compare_value;
};
void execute(const Instruction&);
RegisterValue max_value() const;
RegisterValue all_time_max_value() const { return all_time_max_; }
private:
RegisterValue all_time_max_{0};
std::unordered_map<RegisterName, RegisterValue> registers_;
};
machine.cpp
#include "machine.h"
#include <algorithm>
#include <regex>
#include <sstream>
#include <string>
Machine::Instruction::ParseError::ParseError(const std::string& what_arg)
: std::runtime_error{what_arg}
{}
Machine::Instruction::Operation
Machine::Instruction::to_operation(const std::string& s)
{
if (s == "inc") return Operation::Inc;
if (s == "dec") return Operation::Dec;
std::stringstream error;
error << "Unknown operation: " << s;
throw ParseError{error.str()};
}
Machine::Instruction::Comparison
Machine::Instruction::to_comparison(const std::string& s)
{
if (s == "==") return Comparison::Equal;
if (s == "!=") return Comparison::Unequal;
if (s == "<" ) return Comparison::Less;
if (s == "<=") return Comparison::LessEqual;
if (s == ">" ) return Comparison::Greater;
if (s == ">=") return Comparison::GreaterEqual;
std::stringstream error;
error << "Unknown comparison: " << s;
throw ParseError{error.str()};
}
bool Machine::Instruction::evaluate(
Comparison cmp, RegisterValue a, RegisterValue b)
{
switch (cmp) {
case Comparison::Equal: return a == b;
case Comparison::Unequal: return a != b;
case Comparison::Less: return a < b;
case Comparison::LessEqual: return a <= b;
case Comparison::Greater: return a > b;
case Comparison::GreaterEqual: return a >= b;
}
}
Machine::Instruction::Instruction(const std::string& line)
{
std::smatch line_match;
if (!std::regex_match(line, line_match,
std::regex{R"((\w+) (\w+) ([+-]?\d+) if (\w+) (\W+) ([+-]?\d+))"}
)) {
std::stringstream error;
error << "Invalid format: " << line;
throw ParseError{error.str()};
}
target = line_match[1];
operation = to_operation(line_match[2]);
operation_amount = stoi(line_match[3]);
source = line_match[4];
comparison = to_comparison(line_match[5]);
compare_value = stoi(line_match[6]);
}
std::istream& operator>>(std::istream& input, Machine::Instruction& i)
{
std::string line;
if (std::getline(input, line)) {
Machine::Instruction dummy{line};
std::swap(i, dummy);
}
return input;
}
Machine::RegisterValue Machine::max_value() const
{
if (!registers_.size()) return 0;
return std::max_element(std::begin(registers_), std::end(registers_),
[](auto const& a, auto const& b) { return a.second < b.second; }
)->second;
}
void Machine::execute(const Instruction& i)
{
RegisterValue src{registers_[i.source]};
if (Instruction::evaluate(i.comparison, src, i.compare_value)) {
RegisterValue& target{registers_[i.target]};
switch (i.operation) {
case Instruction::Operation::Inc:
target += i.operation_amount; break;
case Instruction::Operation::Dec:
target -= i.operation_amount; break;
}
if (target > all_time_max_) all_time_max_ = target;
}
}
main.cpp
#include "machine.h"
#include <iostream>
int main()
{
Machine m;
Machine::Instruction i;
try {
while (std::cin >> i) m.execute(i);
} catch (const Machine::Instruction::ParseError& e) {
std::cerr << e.what() << '\n';
}
std::cout << m.max_value() << '\n';
std::cout << m.all_time_max_value() << '\n';
}
Example
$ cat instructions.txt
b inc 5 if a > 1
a inc 1 if b < 5
c dec -10 if a >= 1
c inc -20 if c == 10
$ ./machine <instructions.txt
1
10