aoc 2025 p8

#include <vector>
#include <iostream>
#include <fstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <cmath>
using namespace std;

#define ll long long

std::vector<string> split(std::string& s, std::string&& delim) {
    std::vector<string> tokens;
    int start = 0;
    int end;
    while( (end = s.find(delim, start)) != string::npos) {
        tokens.push_back(s.substr(start, end - start));
        start = end + delim.length();
    }
    if(start < s.length()) {
        tokens.push_back(s.substr(start));
    }
    return tokens;
}

struct Coord {
    ll x;
    ll y;
    ll z;
    int index;
    bool operator==(const Coord& other) const {
        return x == other.x && y == other.y && z == other.z;
    }
};

struct CoordPair {
    Coord c1;
    Coord c2;
    ll dist;
    bool operator<(const CoordPair& other) const {
        return dist < other.dist;
    }
};

ll getDist(Coord c1, Coord c2) {
    return (std::pow((c1.x - c2.x),2) + std::pow((c1.y - c2.y),2) + std::pow((c1.z - c2.z),2));
}

int find(int i, std::vector<int>& parent) {
    if(i != parent[i]) {
        parent[i] = find(parent[i], parent);
    }
    return parent[i];
}
void uni(Coord c1, Coord c2, std::vector<int>& parent, std::vector<int>& groupSize, int& groups) {
    int p1 = find(c1.index, parent);
    int p2 = find(c2.index, parent);
    if(p1 == p2) {
        return;
    }
    groups -= 1;
    if(groupSize[p1] > groupSize[p2]) {
        parent[p2] = p1;
        groupSize[p1] += groupSize[p2];
        groupSize[p2] = 0;
    }
    else {
        parent[p1] = p2;
        groupSize[p2] += groupSize[p1];
        groupSize[p1] = 0;
    }
}

ll solve(std::vector<Coord> coords) {
    std::vector<CoordPair> pairs;
    for(int i=0; i<coords.size(); i++) {
        for(int j = i+1; j<coords.size(); j++) {
            pairs.emplace_back(coords[i], coords[j], getDist(coords[i], coords[j]));
        }
    }
    std::sort(pairs.begin(), pairs.end());
    std::vector<int> parent(coords.size(), 0);
    for(int i=0; i<parent.size(); i++) {
        parent[i] = i;
    }
    std::vector<int> groupSize(coords.size(), 1);
    int group = coords.size();
    for(int i=0; i<1000; i++) {
        const auto& pair = pairs[i];
        uni(pair.c1, pair.c2, parent, groupSize, group);
    }
    std::sort(groupSize.begin(), groupSize.end(), std::greater<int>());
    ll ans = groupSize[0] * groupSize[1] * groupSize[2];

    return ans;
}

ll solve2(std::vector<Coord> coords) {
    ll ans = 0;
    std::vector<CoordPair> pairs;
    for(int i=0; i<coords.size(); i++) {
        for(int j = i+1; j<coords.size(); j++) {
            pairs.emplace_back(coords[i], coords[j], getDist(coords[i], coords[j]));
        }
    }
    std::sort(pairs.begin(), pairs.end());
    std::vector<int> parent(coords.size(), 0);
    for(int i=0; i<parent.size(); i++) {
        parent[i] = i;
    }
    std::vector<int> groupSize(coords.size(), 1);
    int groups = coords.size();
    for(int i=0; i<pairs.size(); i++) {
        const auto& pair = pairs[i];
        uni(pair.c1, pair.c2, parent, groupSize, groups);
        if(groups == 1) {
            ans = pair.c1.x * pair.c2.x;
            break;
        }
    }

    return ans;
}

int main() {
    ifstream inputFile("../data/day8.txt");
    std::string line;
    std::vector<Coord> coords;
    int index = 0;
    while(std::getline(inputFile, line)) {
        vector<string> coordStrs = split(line, ",");
        coords.emplace_back(std::stoull(coordStrs[0]), std::stoull(coordStrs[1]), std::stoull(coordStrs[2]), index++);
    }
    std::cout << solve2(coords) << std::endl;
    return 0;
}