Advent of Code 2019 - Day 2

day2.cpp

#include <iostream>
#include <string>
#include <vector>

// Valid program instructions
enum INSTRUCTION { ADD, MULTIPLY, HALT, UNKNOWN };

// Convert from an instuction opcode to internal representation
INSTRUCTION getInstruction(int instruction) {
  switch (instruction) {
  case 1:
    return ADD;
  case 2:
    return MULTIPLY;
  case 99:
    return HALT;
  default:
    return UNKNOWN;
  }
}

// A valid program consists of a series of integers delimited by a comma or EOF
// This function takes a string containing valid program source code and
// tokenises it into a series of instructions and arguments
std::vector<int> tokenise(const std::string &source) {
  std::vector<int> tokens;
  size_t tokenBegin = 0;
  std::string tokenString;
  for (size_t i = 0; i < source.size(); ++i) {
    if (source[i] == ',' || i + 1 == source.size()) {
      tokenString = source.substr(tokenBegin, i - tokenBegin);
      tokens.push_back(std::atoi(tokenString.c_str()));
      tokenString.clear();
      tokenBegin = i + 1;
    }
  }
  return tokens;
}

// Executes one instruction on program memory state.
// The instruction at index instructionPtr will be read, as will the following
// four elements of program memory, which will be considered to be the arguments
// of that instruction. instructionPtr will be accordingly incremented. Returns
// the value at the output register of the executed instruction. Returns -1 for
// execution error. Returns -2 for halting.
int execute(std::vector<int> &state, size_t *instructionPtr) {
  if (instructionPtr == nullptr) {
    return -1;
  }

  if (*instructionPtr + 4 >= state.size()) {
    return -1;
  }

  // Read the instruction and its operands
  INSTRUCTION instruction = getInstruction(state[*instructionPtr]);

  // Handle halts, which have no operands
  if (instruction == HALT) {
    *instructionPtr += 1;
    return -2;
  }

  int a = state[state[*instructionPtr + 1]];
  int b = state[state[*instructionPtr + 2]];
  size_t out = state[*instructionPtr + 3];
  *instructionPtr += 4;

  // Requesting out-of-bounds memory access
  if (out >= state.size()) {
    return -1;
  }

  switch (instruction) {
  case ADD:
    state[out] = a + b;
    break;
  case MULTIPLY:
    state[out] = a * b;
    break;
  case UNKNOWN:
  default:
    return -1;
  }

  return state[out];
};

// Execute an program starting at state state until either a HALT instruction or
// error is encountered. This will mutate state. If program execution is
// successful, returns the value at the output register (position 0). If an
// error is encountered, returns -1.
int executeProgram(std::vector<int> &state) {
  // Program execution starts at position 0
  size_t instructionPtr = 0;
  while (int out = execute(state, &instructionPtr) > 0) {
    if (out == -1) {
      std::cerr << "Error in program execution encountered at position "
                << instructionPtr << std::endl;
      return -1;
    }
    if (out == -2) {
      break;
    }
  }
  return state[0];
}

int main(int argc, char **argv) {
  // Read program input from stdin until EOF is encountered
  std::string programSource;
  std::string buf;
  while (std::getline(std::cin, buf)) {
    programSource += buf;
  }

  const std::vector<int> originalState = tokenise(programSource);

  ////////////////////////////////////////////////////////////
  // PART ONE
  ////////////////////////////////////////////////////////////

  // Copy the program state to avoid modifying the original
  std::vector<int> state = originalState;

  int originalOut = executeProgram(state);
  if (originalOut == -1) {
    return 1;
  }
  std::cout << originalOut << std::endl;

  ////////////////////////////////////////////////////////////
  // PART TWO
  ////////////////////////////////////////////////////////////
  constexpr int TARGET_OUTPUT = 19690720;
  constexpr int MAX_VALUE = 99;

  // Sweep over possible program mutations and check to see if we get the
  // desired output
  for (int noun = 0; noun <= MAX_VALUE; ++noun) {
    for (int verb = 0; verb <= MAX_VALUE; ++verb) {
      state = originalState;
      state[1] = noun;
      state[2] = verb;
      int out = executeProgram(state);

      if (out == -1) {
        std::cerr << "Error encountered with (noun, verb) => (" << noun << ", "
                  << verb << ")" << std::endl;
        break;
      }

      if (out == TARGET_OUTPUT) {
        std::cout << "Desired output found" << std::endl;
        std::cout << "(noun, verb) => (" << noun << ", " << verb << ")"
                  << std::endl;
        return 0;
      }
    }
  }

  std::cerr << "Did not encounter target output when exhaustively searching "
               "input values"
            << std::endl;
  return 1;
}