#include <fstream>
#include <iostream>
#include <sstream>
#include <vector>
#include <cassert>

using namespace std;

enum Op {
  NOP,
  ADD,
  MUL,
  CON
};

// checks whether a single calibration is valid
bool checkCalibration(unsigned long long expected, vector<unsigned long long> nums, vector<Op> ops) {
  assert(ops.size() == nums.size() - 1);

  unsigned long long result = nums[0];
  for (unsigned long long i = 1; i < nums.size(); i++) {
    if (result > expected) return false;
    switch (ops[i - 1]) {
      case NOP: return false;
      case ADD:
        result += nums[i];
        break;
      case MUL:
        result *= nums[i];
        break;
      case CON:
        stringstream ss;
        ss << result << nums[i];
        ss >> result;
        break;
    }
  }

  return result == expected;
}

// checks whether there exists a valid calibration
bool tryCalibration(unsigned long long expected, vector<unsigned long long> nums, vector<Op> ops, bool part2) {
  // base case
  if (ops.size() == nums.size() - 1) return checkCalibration(expected, nums, ops);

  unsigned long long i = ops.size();

  // try add
  ops.push_back(ADD);
  if (tryCalibration(expected, nums, ops, part2)) return true;

  // try mul
  ops[i] = MUL;
  if (tryCalibration(expected, nums, ops, part2)) return true;

  // try con
  ops[i] = CON;
  return part2 && tryCalibration(expected, nums, ops, part2);
}

void parseCalibrations(const char *path, vector<unsigned long long> &expected_v, vector<vector<unsigned long long>> &nums_v) {
  ifstream input(path);
  string line;
  char c;
  unsigned long long a;

  while (getline(input, line)) {
    stringstream line_stream;
    line_stream << line;
    // get expected value
    line_stream >> a;
    expected_v.push_back(a);
    // discard colon
    line_stream >> c;

    // get calibration numbers
    vector<unsigned long long> nums;
    while (line_stream >> a) {
      nums.push_back(a);
    }
    nums_v.push_back(nums);
  }
}

unsigned long long part1(const char *path) {
  vector<unsigned long long> expected_v;
  vector<vector<unsigned long long>> nums_v;

  parseCalibrations(path, expected_v, nums_v);

  unsigned long long result = 0;
  for (unsigned long long i = 0; i < expected_v.size(); i++) {
    vector<Op> ops;
    if (tryCalibration(expected_v[i], nums_v[i], ops, false)) {
      result += expected_v[i];
    }
  }
  return result;
}

unsigned long long part2(const char *path) {
  vector<unsigned long long> expected_v;
  vector<vector<unsigned long long>> nums_v;

  parseCalibrations(path, expected_v, nums_v);

  unsigned long long result = 0;
  for (unsigned long long i = 0; i < expected_v.size(); i++) {
    vector<Op> ops;
    if (tryCalibration(expected_v[i], nums_v[i], ops, true)) {
      result += expected_v[i];
    }
  }
  return result;
}

int main(int argc, char *argv[]) {
  cout << "example1: " << part1("example") << endl;
  cout << "input1:   " << part1("input") << endl;
  cout << "example2: " << part2("example") << endl;
  cout << "input2:   " << part2("input") << endl;
  return 0;
}