AdventOfCode2022/21b.cpp at master · HereComesTheMoon/AdventOfCode2022 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <fstream>
#include <iostream>
#include <vector>
#include <stdint.h>
#include <map>
#include <assert.h>
#include <limits>

const std::string INPUT_FILE = "./data/21.txt";

typedef std::pair<std::string, std::string> Monkey;

bool is_number(std::string& s) {
  for (const auto& c : s) {
    if (!isdigit(c)) {
      return false;
    }
  }
  return true;
}

std::map<std::string, std::string> read() {
  std::ifstream infile(INPUT_FILE);
  std::string line;

  auto data = std::map<std::string, std::string>();

  while (std::getline(infile, line)) {
    std::string name = line.substr(0, 4);
    line.erase(0, 6);
    data.insert({name, line});
  }

  data.insert_or_assign("humn", "humn");
  data.at("root")[5] = '=';
  return data;
}

std::string substitute(std::string name, const std::map<std::string, std::string>& dict) {
  auto val = dict.at(name);
  if (is_number(val)) { return val; }
  if (val == "humn") { return val; }

  char op = val.at(5);
  auto sa = val.substr(0, 4);
  auto sb = val.substr(7, 4);
  assert(dict.contains(sa));
  assert(dict.contains(sb));
  auto ta = substitute(sa, dict);
  auto tb = substitute(sb, dict);

  if (is_number(ta) && is_number(tb)) {
    auto a = std::stoll(ta);
    auto b = std::stoll(tb);
    switch (op) {
      case '+':
        return std::to_string(a + b);
      case '*':
        if (a > std::numeric_limits<int64_t>::max() / b) { assert(false); }
        return std::to_string(a * b);
      case '/':
        assert(a == (a/b)*b);
        return std::to_string(a / b);
      case '-':
        return std::to_string(a - b);
      default:
        assert(false);
    }

  }

  return "(" + ta + " " + op + " " + tb + ")";
}

std::tuple<std::string, char, std::string> split(std::string s) {
  auto count = 0;
  for (uint i = 1; i < s.size() - 1; ++i) {
    if (count == 0) {
      if (s[i] == '+' || s[i] == '*' || s[i] == '/' || s[i] == '-' || s[i] == '=') {
        return {s.substr(1, i - 2), s[i], s.substr(i + 2, s.size() - i - 3)};
      }
    }
    if (s[i] == '(') count++;
    if (s[i] == ')') count--;
  }

  assert(false);
}

int64_t simplify(std::string root, int64_t equals) {
  if (root == "humn") return equals;
  auto [a, op, b] = split(root);
  if (is_number(a)) {
    auto aa = std::stoll(a);
    switch (op) {
      case '+': return simplify(b, equals - aa);
      case '*': return simplify(b, equals / aa);
      case '/': assert(false);
      case '-': return simplify(b, aa - equals);
      default :  assert(false);
    }
  } else if (is_number(b)) {
    auto bb = std::stoll(b);
    switch (op) {
      case '+': return simplify(a, equals - bb);
      case '*': return simplify(a, equals / bb);
      case '/': return simplify(a, equals * bb);
      case '-': return simplify(a, equals + bb);
      default : assert(false);
    }
  }

  assert(false);
}


int main() {
  auto data = read();

  auto subs = substitute("root", data);
  auto [a, op, b] = split(subs);
  assert(op == '=');
  int64_t res = 0;

  if (is_number(a)) {
    res = simplify(b, std::stoll(a));
  } else if (is_number(b)) {
    res = simplify(a, std::stoll(b));
  } else { assert(false); }

  std::cout << "Result: " << res << std::endl;
  return 0;
}