300 lines
8.3 KiB
C++
300 lines
8.3 KiB
C++
#include <algorithm>
|
|
#include <deque>
|
|
#include <fstream>
|
|
#include <iostream>
|
|
#include <memory>
|
|
#include <sstream>
|
|
#include <unordered_map>
|
|
#include <unordered_set>
|
|
#include <vector>
|
|
|
|
class SnailFishNumber {
|
|
public:
|
|
SnailFishNumber() {}
|
|
|
|
void setParent(std::shared_ptr<SnailFishNumber> &parent) {
|
|
_parent = parent;
|
|
}
|
|
|
|
void setValue(uint64_t value) {
|
|
_simple = true;
|
|
_simple_value = value;
|
|
}
|
|
|
|
void setLeft(std::shared_ptr<SnailFishNumber> &left) {
|
|
_simple = false;
|
|
_left = left;
|
|
}
|
|
|
|
void setRight(std::shared_ptr<SnailFishNumber> &right) {
|
|
_simple = false;
|
|
_right = right;
|
|
}
|
|
|
|
void printNumber() {
|
|
if (_simple) {
|
|
std::cout << _simple_value;
|
|
} else {
|
|
std::cout << "[";
|
|
_left->printNumber();
|
|
std::cout << ",";
|
|
_right->printNumber();
|
|
std::cout << "]";
|
|
}
|
|
}
|
|
|
|
void addValue(uint64_t val) {
|
|
_simple_value += val;
|
|
}
|
|
|
|
uint64_t getValue() {
|
|
return _simple_value;
|
|
}
|
|
|
|
void fixNumber() {
|
|
// we rely on lazy execution
|
|
while (explodeNumber() || splitNumber()) {
|
|
}
|
|
}
|
|
|
|
std::shared_ptr<SnailFishNumber> findLeftNeighbour() {
|
|
auto child = this;
|
|
auto parent = _parent.get();
|
|
while (parent != nullptr && parent->isLeftChild(child)) {
|
|
child = parent;
|
|
parent = parent->getParent().get();
|
|
}
|
|
if (parent == nullptr) {
|
|
return nullptr;
|
|
}
|
|
auto left_neighbour = parent->getLeftChild();
|
|
while (!left_neighbour->isSimple()) {
|
|
left_neighbour = left_neighbour->getRightChild();
|
|
}
|
|
return left_neighbour;
|
|
}
|
|
|
|
std::shared_ptr<SnailFishNumber> findRightNeighbour() {
|
|
auto child = this;
|
|
auto parent = _parent.get();
|
|
while (parent != nullptr && parent->isRightChild(child)) {
|
|
child = parent;
|
|
parent = parent->getParent().get();
|
|
}
|
|
if (parent == nullptr) {
|
|
return nullptr;
|
|
}
|
|
auto right_neighbour = parent->getRightChild();
|
|
while (!right_neighbour->isSimple()) {
|
|
right_neighbour = right_neighbour->getLeftChild();
|
|
}
|
|
return right_neighbour;
|
|
}
|
|
|
|
std::shared_ptr<SnailFishNumber> getParent() {
|
|
return _parent;
|
|
}
|
|
|
|
std::shared_ptr<SnailFishNumber> getLeftChild() {
|
|
return _left;
|
|
}
|
|
|
|
std::shared_ptr<SnailFishNumber> getRightChild() {
|
|
return _right;
|
|
}
|
|
|
|
bool isSimple() {
|
|
return _simple;
|
|
}
|
|
|
|
bool isLeftChild(SnailFishNumber *ptr) {
|
|
return ptr == _left.get();
|
|
}
|
|
|
|
bool isRightChild(SnailFishNumber *ptr) {
|
|
return ptr == _right.get();
|
|
}
|
|
|
|
uint64_t getMagnitude() {
|
|
if (_simple) {
|
|
return _simple_value;
|
|
}
|
|
return 3 * _left->getMagnitude() + 2 * _right->getMagnitude();
|
|
}
|
|
|
|
std::shared_ptr<SnailFishNumber> copySelf() const {
|
|
auto res = std::make_shared<SnailFishNumber>();
|
|
if (_simple) {
|
|
res->setValue(_simple_value);
|
|
} else {
|
|
auto left_copy = _left->copySelf();
|
|
auto right_copy = _right->copySelf();
|
|
left_copy->setParent(res);
|
|
right_copy->setParent(res);
|
|
res->setLeft(left_copy);
|
|
res->setRight(right_copy);
|
|
}
|
|
return res;
|
|
}
|
|
|
|
private:
|
|
bool explodeNumber(int depth = 0) {
|
|
if (_simple) {
|
|
return false;
|
|
;
|
|
}
|
|
if (depth >= 4) {
|
|
auto left_neighbour = findLeftNeighbour();
|
|
auto right_neighbour = findRightNeighbour();
|
|
if (left_neighbour != nullptr) {
|
|
left_neighbour->addValue(_left->getValue());
|
|
}
|
|
if (right_neighbour != nullptr) {
|
|
right_neighbour->addValue(_right->getValue());
|
|
}
|
|
_simple = true;
|
|
_simple_value = 0;
|
|
_left.reset();
|
|
_right.reset();
|
|
return true;
|
|
}
|
|
if (_left->explodeNumber(depth + 1)) {
|
|
return true;
|
|
}
|
|
if (_right->explodeNumber(depth + 1)) {
|
|
return true;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
bool splitNumber() {
|
|
if (!_simple) {
|
|
if (_left->splitNumber()) {
|
|
return true;
|
|
}
|
|
if (_right->splitNumber()) {
|
|
return true;
|
|
}
|
|
return false;
|
|
}
|
|
if (_simple_value > 9) {
|
|
_simple = false;
|
|
_left = std::make_unique<SnailFishNumber>();
|
|
_right = std::make_unique<SnailFishNumber>();
|
|
_left->setValue(_simple_value / 2);
|
|
_right->setValue(_simple_value - _left->getValue());
|
|
std::shared_ptr<SnailFishNumber> me{};
|
|
if (_parent->isRightChild(this)) {
|
|
me = _parent->getRightChild();
|
|
} else {
|
|
me = _parent->getLeftChild();
|
|
}
|
|
_left->setParent(me);
|
|
_right->setParent(me);
|
|
_simple_value = 0;
|
|
return true;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
bool _simple = false;
|
|
uint64_t _simple_value{};
|
|
std::shared_ptr<SnailFishNumber> _left{ nullptr };
|
|
std::shared_ptr<SnailFishNumber> _right{ nullptr };
|
|
std::shared_ptr<SnailFishNumber> _parent{ nullptr };
|
|
};
|
|
|
|
std::vector<std::shared_ptr<SnailFishNumber>>
|
|
getNumbers(const std::string &file_name) {
|
|
std::vector<std::shared_ptr<SnailFishNumber>> numbers{};
|
|
|
|
std::ifstream file(file_name);
|
|
std::string str;
|
|
while (std::getline(file, str)) {
|
|
auto cur = std::make_shared<SnailFishNumber>();
|
|
numbers.push_back(cur);
|
|
std::deque<std::shared_ptr<SnailFishNumber>> parents;
|
|
for (auto &c : str) {
|
|
if (c == '[') {
|
|
parents.push_back(cur);
|
|
cur = std::make_shared<SnailFishNumber>();
|
|
cur->setParent(parents.back());
|
|
parents.back()->setLeft(cur);
|
|
}
|
|
if (c >= '0' && c <= '9') {
|
|
cur->setValue(c - '0');
|
|
}
|
|
if (c == ',') {
|
|
cur = std::make_shared<SnailFishNumber>();
|
|
cur->setParent(parents.back());
|
|
parents.back()->setRight(cur);
|
|
}
|
|
if (c == ']') {
|
|
cur = parents.back();
|
|
parents.pop_back();
|
|
}
|
|
}
|
|
if (parents.size() > 1) {
|
|
std::cout << "Something's wrong, I can feel it!" << std::endl;
|
|
}
|
|
}
|
|
|
|
return numbers;
|
|
}
|
|
|
|
std::shared_ptr<SnailFishNumber>
|
|
addNumbers(std::shared_ptr<SnailFishNumber> &a,
|
|
std::shared_ptr<SnailFishNumber> &b) {
|
|
auto result = std::make_shared<SnailFishNumber>();
|
|
result->setLeft(a);
|
|
result->setRight(b);
|
|
a->setParent(result);
|
|
b->setParent(result);
|
|
result->fixNumber();
|
|
return result;
|
|
}
|
|
|
|
uint64_t part1(const std::vector<std::shared_ptr<SnailFishNumber>> &numbers) {
|
|
auto n0 = numbers[0]->copySelf();
|
|
auto n1 = numbers[1]->copySelf();
|
|
auto res = addNumbers(n0, n1);
|
|
for (size_t i = 2; i < numbers.size(); i++) {
|
|
auto addition = numbers[i]->copySelf();
|
|
res = addNumbers(res, addition);
|
|
}
|
|
return res->getMagnitude();
|
|
}
|
|
|
|
uint64_t part2(const std::vector<std::shared_ptr<SnailFishNumber>> &numbers) {
|
|
uint64_t max_magnitude = 0;
|
|
for (const auto &number : numbers) {
|
|
for (const auto &number2 : numbers) {
|
|
if (number == number2) {
|
|
continue;
|
|
}
|
|
auto n1 = number->copySelf();
|
|
auto n2 = number2->copySelf();
|
|
auto res = addNumbers(n1, n2);
|
|
auto mag = res->getMagnitude();
|
|
if (mag > max_magnitude) {
|
|
max_magnitude = mag;
|
|
}
|
|
}
|
|
}
|
|
return max_magnitude;
|
|
}
|
|
|
|
int main(int argc, char **argv) {
|
|
if (argc < 2) {
|
|
std::cerr << "You must provide input file!" << std::endl;
|
|
return 1;
|
|
}
|
|
auto numbers = getNumbers(argv[1]);
|
|
std::cout << "The magnitude of final result is \033[91;1m" << part1(numbers)
|
|
<< "\033[0m." << std::endl;
|
|
std::cout
|
|
<< "The largest possible magnitude from only 2 numbers is \033[91;1m"
|
|
<< part2(numbers) << "\033[0m." << std::endl;
|
|
return 0;
|
|
}
|