#include <algorithm>
#include <deque>
#include <fstream>
#include <iostream>
#include <memory>
#include <sstream>
#include <unordered_map>
#include <unordered_set>
#include <vector>

class BeaconPos {
public:
    BeaconPos() = delete;
    BeaconPos(int x, int y, int z): _x(x), _y(y), _z(z) {}

    int getX() const {
        return _x;
    }
    int getY() const {
        return _y;
    }
    int getZ() const {
        return _z;
    }

    void setX(int x) {
        _x = x;
    }
    void setY(int y) {
        _y = y;
    }
    void setZ(int z) {
        _z = z;
    }

    friend std::ostream& operator<<(std::ostream& stream, const BeaconPos& pos) {
        stream << pos.getX() << ", " << pos.getY() << ", " << pos.getZ();
        return stream;
    }

    friend bool operator==(const BeaconPos &pos1, const BeaconPos &pos2) {
        return pos1.getX() == pos2.getX() && pos1.getY() == pos2.getY() && pos1.getZ() == pos2.getZ();
    }

    friend bool operator!=(const BeaconPos &pos1, const BeaconPos &pos2) {
        return !(pos1 == pos2);
    }

    BeaconPos& operator+=(const BeaconPos& pos2) {
        setX(getX() + pos2.getX());
        setY(getY() + pos2.getY());
        setZ(getZ() + pos2.getZ());
        return *this;
    }

    friend BeaconPos operator+(BeaconPos pos1, const BeaconPos &pos2) {
        pos1 += pos2;
        return pos1;
    }

    BeaconPos& operator-=(const BeaconPos& pos2) {
        setX(getX() - pos2.getX());
        setY(getY() - pos2.getY());
        setZ(getZ() - pos2.getZ());
        return *this;
    }

    friend BeaconPos operator-(BeaconPos pos1, const BeaconPos &pos2) {
        pos1 -= pos2;
        return pos1;
    }

private:
    // X possitive - right, negative - left 
    int _x;
    // Y positive - top, negative - bottom
    int _y;
    // Z positive - further back, negative - closer
    int _z;
};

static std::vector<std::function<BeaconPos(const BeaconPos&)>> transformFunctions = {
    [](const BeaconPos &beacon) {return beacon;},
    [](const BeaconPos &beacon) {return BeaconPos(beacon.getZ(), beacon.getY(), -beacon.getX());},
    [](const BeaconPos &beacon) {return BeaconPos(-beacon.getX(), beacon.getY(), -beacon.getZ());},
    [](const BeaconPos &beacon) {return BeaconPos(-beacon.getZ(), beacon.getY(), beacon.getX());},
    [](const BeaconPos &beacon) {return BeaconPos(-beacon.getX(), -beacon.getY(), beacon.getZ());},
    [](const BeaconPos &beacon) {return BeaconPos(-beacon.getZ(), -beacon.getY(), -beacon.getX());},
    [](const BeaconPos &beacon) {return BeaconPos(beacon.getX(), -beacon.getY(), -beacon.getZ());},
    [](const BeaconPos &beacon) {return BeaconPos(beacon.getZ(), -beacon.getY(), beacon.getX());},
    [](const BeaconPos &beacon) {return BeaconPos(beacon.getX(), -beacon.getZ(), beacon.getY());},
    [](const BeaconPos &beacon) {return BeaconPos(beacon.getY(), -beacon.getZ(), -beacon.getX());},
    [](const BeaconPos &beacon) {return BeaconPos(-beacon.getX(), -beacon.getZ(), -beacon.getY());},
    [](const BeaconPos &beacon) {return BeaconPos(-beacon.getY(), -beacon.getZ(), beacon.getX());},
    [](const BeaconPos &beacon) {return BeaconPos(beacon.getX(), beacon.getZ(), -beacon.getY());},
    [](const BeaconPos &beacon) {return BeaconPos(-beacon.getY(), beacon.getZ(), -beacon.getX());},
    [](const BeaconPos &beacon) {return BeaconPos(-beacon.getX(), beacon.getZ(), beacon.getY());},
    [](const BeaconPos &beacon) {return BeaconPos(beacon.getY(), beacon.getZ(), beacon.getX());},
    [](const BeaconPos &beacon) {return BeaconPos(beacon.getZ(), beacon.getX(), beacon.getY());},
    [](const BeaconPos &beacon) {return BeaconPos(beacon.getY(), beacon.getX(), -beacon.getZ());},
    [](const BeaconPos &beacon) {return BeaconPos(-beacon.getZ(), beacon.getX(), -beacon.getY());},
    [](const BeaconPos &beacon) {return BeaconPos(-beacon.getY(), beacon.getX(), beacon.getZ());},
    [](const BeaconPos &beacon) {return BeaconPos(-beacon.getZ(), -beacon.getX(), beacon.getY());},
    [](const BeaconPos &beacon) {return BeaconPos(beacon.getY(), -beacon.getX(), beacon.getZ());},
    [](const BeaconPos &beacon) {return BeaconPos(beacon.getZ(), -beacon.getX(), -beacon.getY());},
    [](const BeaconPos &beacon) {return BeaconPos(-beacon.getY(), -beacon.getX(), -beacon.getZ());},
};

class BeaconMap {
public:
    BeaconMap() {}

    void addBeacon(int x, int y, int z) {
        addBeacon(BeaconPos(x, y, z));
    }

    void addBeacon(BeaconPos beacon) {
        _map.push_back(beacon);
    }

    void generateRelativeBeacons(bool transform) {
        _relative_map.clear();
        _relative_map.emplace_back();
        for(size_t i = 0; i < _map.size(); i++) {
            _relative_map.back().push_back(std::vector<BeaconPos>());
            for(size_t j = 0; j < _map.size(); j++) {
                _relative_map.back().back().emplace_back(_map[j].getX() - _map[i].getX(), _map[j].getY() - _map[i].getY(), _map[j].getZ() - _map[i].getZ());
            }
        }
        if(transform) {
            for(size_t i = 1; i < transformFunctions.size(); i++) {
                _relative_map.emplace_back();
                for(auto &vec : _relative_map[0]) {
                    _relative_map.back().emplace_back();
                    for(auto &value : vec) {
                        _relative_map.back().back().push_back(transformFunctions[i](value));
                    }
                }
            }
        }
    }

    std::pair<BeaconPos, int> has12Common(const BeaconMap &other) {
        auto otherRelativeBeacons = other._relative_map[0];
        for(size_t transformIndex = 0; transformIndex < _relative_map.size(); transformIndex++) {
            for(auto &mybeaconmap : _relative_map[transformIndex]) {
                int commonBeacons = 0;
                for(auto &otherBeaconMap : otherRelativeBeacons) {
                    commonBeacons = 0;
                    for(auto &myBeacon : mybeaconmap) {
                        if(std::find(otherBeaconMap.begin(), otherBeaconMap.end(), myBeacon) != otherBeaconMap.end()) {
                            commonBeacons++;
                        }
                    }
                    if(commonBeacons >= 11) {
                        size_t otherIndex = 0;
                        size_t myIndex = 0;
                        for(size_t i = 0; i < otherBeaconMap.size(); i++) {
                            if(otherBeaconMap[i].getX() == 0 && otherBeaconMap[i].getY() == 0 && otherBeaconMap[i].getZ() == 0) {
                                otherIndex = i;
                                break;
                            }
                        }
                        for(size_t i = 0; i < otherBeaconMap.size(); i++) {
                            if(mybeaconmap[i].getX() == 0 && mybeaconmap[i].getY() == 0 && mybeaconmap[i].getZ() == 0) {
                                myIndex = i;
                                break;
                            }
                        }
                        return {other._map[otherIndex] - transformFunctions[transformIndex](_map[myIndex]), transformIndex};
                    }
                }
            }
        }
        return {{0,0,0}, -1};
    }

    size_t getNumberOfBeacons() const {
        return _map.size();
    }

    void copyBeacons(const BeaconMap &map, BeaconPos relativePosition) {
        for(const auto &beacon : map._map) {
            auto repositioned = beacon + relativePosition;
            if(hasBeacon(repositioned)) {
                continue;
            } else {
                addBeacon(repositioned);
            }
        }
    }

    void updateMap(int transformIndex) {
        for(auto &beacon : _map) {
            beacon = transformFunctions[transformIndex](beacon);
        }
    }

private:
    bool hasBeacon(BeaconPos beacon) {
        return std::find(_map.begin(), _map.end(), beacon) != _map.end();
    }

    std::vector<BeaconPos> _map;
    std::vector<std::vector<std::vector<BeaconPos>>> _relative_map;
};

std::vector<BeaconMap>
getBeaconMaps(const std::string &file_name) {
    std::vector<BeaconMap> beaconMaps{};

    std::ifstream file(file_name);
    std::string str;
    while (std::getline(file, str)) {
        if(str[1] == '-') {
            auto cur = BeaconMap();
            beaconMaps.push_back(cur);
            continue;
        }
        if(str.empty()) {
            continue;
        }
        std::istringstream ss(str);
        int x, y, z;
        char delimiter;
        ss >> x;
        ss >> delimiter;
        ss >> y;
        ss >> delimiter;
        ss >> z;
        BeaconPos bp(x, y, z);
        beaconMaps.back().addBeacon(x, y, z);
    }

    beaconMaps[0].generateRelativeBeacons(false);
    for(size_t i = 1; i < beaconMaps.size(); i++) {
        beaconMaps[i].generateRelativeBeacons(true);
    }

    return beaconMaps;
}

std::pair<uint64_t, std::vector<BeaconPos>> part1(std::vector<BeaconMap> maps) {
    std::vector<BeaconPos> scanners{};
    std::deque<size_t> mapIndexes{};
    for(size_t i = 1; i < maps.size(); i++) {
        mapIndexes.push_back(i);
    }
    while(!mapIndexes.empty()) {
        auto prevCount = mapIndexes.size();
        for(auto iterator = mapIndexes.begin(); iterator != mapIndexes.end(); iterator++) {
            auto result = maps[*iterator].has12Common(maps[0]);
            if(result.second >= 0) {
                scanners.push_back(result.first);
                maps[*iterator].updateMap(result.second);
                maps[0].copyBeacons(maps[*iterator], result.first);
                mapIndexes.erase(iterator);
                maps[0].generateRelativeBeacons(false);
                break;
            }
        }
        if(prevCount == mapIndexes.size()) {
            std::cerr << "Cannot find all beacons";
            return {-1, {}};
        }
    }
    return {maps[0].getNumberOfBeacons(), scanners};
}

uint64_t part2(std::vector<BeaconPos> &scanners) {
    size_t maxManhattan = 0;
    for(size_t i = 0; i < scanners.size(); i++) {
        for(size_t j = i; j < scanners.size(); j++) {
            auto diff = scanners[i] - scanners[j];
            auto manhattan = abs(diff.getX()) + abs(diff.getY()) + abs(diff.getZ());
            if(manhattan > maxManhattan) {
                maxManhattan = manhattan;
            }
        }
    }
    return maxManhattan;
}

int main(int argc, char **argv) {
    if (argc < 2) {
        std::cerr << "You must provide input file!" << std::endl;
        return 1;
    }
    auto maps = getBeaconMaps(argv[1]);
    auto result = part1(maps);
    std::cout << "The number of beacons mapped in the ocean is \033[91;1m" << result.first
              << "\033[0m." << std::endl;
    std::cout
        << "The largest manhattan distance between any 2 scanners is \033[91;1m"
        << part2(result.second) << "\033[0m." << std::endl;
    return 0;
}