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

Question

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

Answer 1

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().