# Advent of Code 2017, Day 8 - Evaluate instructions to modify registers

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


## First impressions

It's clear and easy to read; the program structure is obvious. There's not a lot to improve here!

## Prefer function objects to switching on enums

We can eliminate the Operation and Comparison enums and their associated switches by passing the function itself; that means less code to modify if the language changes. Here's what I ended up with:

    using Operation = std::function<RegisterValue(RegisterValue, RegisterValue)>;
using Comparison = std::function<bool(RegisterValue, RegisterValue)>;

Machine::Instruction::Operation
Machine::Instruction::to_operation(const std::string& s)
{
if (s == "inc") return std::plus<RegisterValue>();
if (s == "dec") return std::minus<RegisterValue>();

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 std::equal_to<RegisterValue>();
if (s == "!=") return std::not_equal_to<RegisterValue>();
if (s == "<" ) return std::less<RegisterValue>();
if (s == "<=") return std::less_equal<RegisterValue>();
if (s == ">" ) return std::greater<RegisterValue>();
if (s == ">=") return std::greater_equal<RegisterValue>();

std::stringstream error;
error << "Unknown comparison: " << s;
throw ParseError{error.str()};
}

void Machine::execute(const Instruction& i)
{
RegisterValue src{registers_[i.source]};
if (i.comparison(src, i.compare_value)) {
RegisterValue& target{registers_[i.target]};
target = i.operation(target, i.operation_amount);
if (target > all_time_max_) all_time_max_ = target;
}
}


The evaluate() function is no longer required and drops out of the code.

If the construction of new function objects for every instruction is a concern, we could make static members for them all, and return the appropriate one by reference, or have a static std::map, where we can use at() for the lookup, and pass or convert the std::out_of_range error if needed.

# Use formatted input instead of regular expressions

We don't need all the weight of regular expressions to parse this simple input format. We can drop the #include <regex> and simplify our instruction reading:

std::istream& operator>>(std::istream& input, Machine::Instruction& i)
{
std::string line;
if (!std::getline(input, line)) return input;
std::string op_str, cmp_str, if_str;
std::istringstream in{line};
in >> i.target >> op_str >> i.operation_amount
>> if_str >> i.source >> cmp_str >> i.compare_value;
if (std::string dummy; if_str != "if" || !in || in >> dummy) {
std::stringstream error;
error << "Invalid format: " << line;
throw Machine::Instruction::ParseError{error.str()};
}
i.operation = Machine::Instruction::to_operation(op_str);
i.comparison = Machine::Instruction::to_comparison(cmp_str);
return input;
}


# Does it make sense to print outputs if an instruction failed?

I reorganised main() to reduce the scope of i and to avoid printing result if we fail to parse (and to accept a fixed input, for my testing convenience):

int main()
{
std::istringstream instructions{
"b inc 5 if a > 1\n"
"a inc 1 if b < 5\n"
"c dec -10 if a >= 1\n"
"c inc -20 if c == 10\n"
};

try {
Machine m;
Machine::Instruction i;
while (instructions >> i) m.execute(i);
std::cout << m.max_value() << '\n';
std::cout << m.all_time_max_value() << '\n';
} catch (const Machine::Instruction::ParseError& e) {
std::cerr << e.what() << '\n';
return 1;
}
}


# Minor tweaks

• We can write registers.empty() instead of !registers.size().