AoC Day 18 2021

day_18_2021.cpp

#include <stdio.h>
#include <iostream>

using namespace std;

inline string IntToString(int a){
    char x[100];
    sprintf(x,"%d",a); string s = x;
    return s;
}
inline int StringToInt(string a){
    char x[100]; int res;
    strcpy(x,a.c_str()); sscanf(x,"%d",&res);
    return res;
}

struct Node {
    Node* parent;
    Node* left;
    Node* right;

    Node* prev_node;
    Node* next_node;

    int value;
    int depth;
};

Node* newNode() {
    Node* temp = new Node;
    temp->parent = NULL;
    temp->left = NULL;
    temp->right = NULL;
    temp->prev_node = NULL;
    temp->next_node = NULL;
    temp->value = -1; // means operator
    return temp;
}

Node* convert_to_tree(string s) {
    Node* current_node = newNode();
    Node* temp_prev = NULL;
    current_node->depth = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '[') {
            // Create left node
            current_node->left = newNode();
            current_node->left->parent = current_node;
            current_node->left->depth = current_node->depth + 1;
            // Move down
            current_node = current_node->left;
        } else if (s[i] == ',') {
            // Move back to the parent
            current_node = current_node->parent;
            // Create right node
            current_node->right = newNode();
            current_node->right->parent = current_node;
            current_node->right->depth = current_node->depth + 1;
            // Move down
            current_node = current_node->right;
        } else if (s[i] == ']') {
            // Move back to the parent
            current_node = current_node->parent;
        } else {
            string x = "";
            x += s[i];
            current_node->value = StringToInt(x);
            if (temp_prev != NULL) {
                temp_prev->next_node = current_node;
                current_node->prev_node = temp_prev;
            }
            temp_prev = current_node;
        }
    }
    return current_node;
}

bool explodes(Node* node) {
    if (node == NULL) return false;
    if (node->depth >= 5 && node->value != -1) {
        // Go back to parent
        node = node->parent;
        // Check if both left & right side are values
        if (node->left->value != -1 && node->right->value != -1) {
            // We should reduce this
            // Find left value that can be added
            if (node->left->prev_node != NULL) {
                node->left->prev_node->value += node->left->value;
                node->prev_node = node->left->prev_node;
                node->left->prev_node->next_node = node;
            }
            // Find right value that can be added
            if (node->right->next_node != NULL) {
                node->right->next_node->value += node->right->value;
                node->next_node = node->right->next_node;
                node->right->next_node->prev_node = node;
            }
            // Replace current node from operator to value
            node->value = 0;
            node->left = NULL;
            node->right = NULL;
            return true;
        }
    }
    return explodes(node->left) || explodes(node->right);
}

bool split(Node* node) {
    if (node == NULL) return false;
    if (node->value >= 10) {
        node->left = newNode();
        node->right = newNode();

        // Initialize left
        node->left->parent = node;
        node->left->depth = node->depth + 1;
        node->left->value = node->value / 2;
        if (node->prev_node != NULL) {
            node->left->prev_node = node->prev_node;
            node->prev_node->next_node = node->left;
        }
        node->left->next_node = node->right;

        // Initialize right
        node->right->parent = node;
        node->right->depth = node->depth + 1;
        node->right->value = node->value / 2 + node->value % 2;
        if (node->next_node != NULL) {
            node->right->next_node = node->next_node;
            node->next_node->prev_node = node->right;
        }
        node->right->prev_node = node->left;

        // Replace current node from value to operator
        node->value = -1;
        node->prev_node = NULL;
        node->next_node = NULL;
        return true;
    }
    return split(node->left) || split(node->right);
}

string convert_to_snailfish(Node *node) {
    string current_snailfish = "";
    if (node == NULL) return current_snailfish;
    if (node->value == -1) current_snailfish += '[';
    current_snailfish += convert_to_snailfish(node->left);
    if (node->value == -1) current_snailfish += ',';
    else {
        string s = IntToString(node->value);
        current_snailfish += s;
    }
    current_snailfish += convert_to_snailfish(node->right);
    if (node->value == -1) current_snailfish += ']';
    return current_snailfish;
}

int magnitude(Node *node) {
    int sum = 0;
    if (node == NULL) return 0;
    if (node->value == -1) {
        sum += 3 * magnitude(node->left);
        sum += 2 * magnitude(node->right);
    } else {
        return node->value;
    }
    return sum;
}

Node* sum_two_snailfish(string s1, string s2) {
    string current_snailfish = '[' + s1 + ',' + s2 + ']';
    Node* root = convert_to_tree(current_snailfish);
    bool is_changed = true;
    while (is_changed) {
        is_changed = explodes(root);
        if (is_changed) continue;
        is_changed = split(root) || is_changed;
    }
    return root;
}

int main() {
  int N = 100;
  string s[105];
  for (int i = 0; i < N; i++)
    cin >> s[i];

  Node* root;
  string snailfish = s[0];
  for (int i = 1; i < N; i++) {
    root = sum_two_snailfish(snailfish, s[i]);
    // Convert back to snailfish
    snailfish = convert_to_snailfish(root);
  }
  cout << snailfish << " " << magnitude(root) << endl;

  int max_magnitude = 0;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        if (i == j) continue;
        int temp_magnitude = magnitude(sum_two_snailfish(s[i], s[j]));
        if (max_magnitude < temp_magnitude) max_magnitude = temp_magnitude;
    }
  }
  cout << max_magnitude << endl;

  return 0;
}