Untitled

#include <iostream>
#include <vector>
#include <unordered_map>
#include "../util.cc"

using namespace std;

// Define a constant for expansion value
const long EXPAND = 1000000 - 1;

// Define a structure to represent a Galaxy with row and column coordinates
struct Galaxy {
    long row;
    long col;

    // Define a custom hash function for Galaxy
    size_t operator()(const Galaxy& g) const {
        hash<long> hasher;
        size_t rowHash = hasher(g.row);
        size_t colHash = hasher(g.col);
        return rowHash ^ colHash;
    }

    // Define a custom equality operator for Galaxy
    bool operator==(const Galaxy& other) const {
        return row == other.row && col == other.col;
    }

    // Define a custom inequality operator for Galaxy
    bool operator!=(const Galaxy& other) const {
        return !(*this == other);
    }
};

// Declare an unordered map to store expanded galaxies, using Galaxy as both key and value types
unordered_map<Galaxy, Galaxy, Galaxy> expandedGalaxies;

// Define the solution function that takes a vector of strings as input and returns a long
long solution(vector<string> &input) {
    long expandedColumn = 0;
    long expandedRow = 0;

    // Scan columns to find galaxies and expand their coordinates
    for (long c = 0; c < input[0].size(); c++) {
        bool found = false;
        for (long r = 0; r < input.size(); r++) {
            if (input[r][c] == '#') {
                found = true;
                expandedGalaxies[{r, c}] = {0, c + expandedColumn};
            }
        }
        if (!found) {
            expandedColumn += EXPAND;
        }
    }

    // Scan rows to find galaxies and expand their coordinates
    for (long r = 0; r < input.size(); r++) {
        bool found = false;
        for (long c = 0; c < input[r].size(); c++) {
            if (input[r][c] == '#') {
                found = true;
                expandedGalaxies[{r, c}] = {r + expandedRow, expandedGalaxies[{r, c}].col};
            }
        }
        if (!found) {
            expandedRow += EXPAND;
        }
    }

    long count = 0;
    long sumDist = 0;

    // Calculate the sum of distances between all pairs of galaxies
    for (auto galaxy : expandedGalaxies) {
        for (auto otherGalaxy : expandedGalaxies) {
            if (galaxy.first != otherGalaxy.first) {
                long dist = abs(galaxy.second.row - otherGalaxy.second.row) +
                            abs(galaxy.second.col - otherGalaxy.second.col);
                sumDist += dist;
                count++;
            }
        }
    }

    // Return half of the sum of distances (each distance is counted twice)
    return sumDist / 2;
}

// Define the main function
int main() {
    // Read input from file
    vector<string> input = readInputFile("day_11/part1.txt");

    // Print the result of the solution function
    cout << solution(input) << endl;

    // Return 0 to indicate successful execution
    return 0;
}