manhattan.cpp

#include<fstream>
#include<vector>
#include<tuple>
#include<iostream>
#include<string>
#include<charconv>
#include<map>
#include<cmath>
#include<set>
#include<algorithm>

std::vector<std::pair<int, int>> loadpoints(std::string filename="input.txt"){
    std::vector<std::pair<int, int>> points;
    std::string xs, ys;
    int x, y;
    std::ifstream file{filename};

    while(getline(file, xs, ',') && getline(file, ys, '\n')) {
        auto q = std::from_chars(xs.data(), xs.data()+xs.size(), x);
        auto r = std::from_chars(ys.data()+1, ys.data()+ys.size(), y); // add one offset because of a space
        if (r.ec == std::errc::invalid_argument) {
            const auto error = std::make_error_code(r.ec);
            std::cout << error.message();
        }
        points.push_back(std::pair<int, int>{x, y});
    }
    return points;
}

std::pair<int, int> findmin(std::vector<std::pair<int, int>> points) {
    int xmin, ymin;
    xmin = ymin = 1<<20;
    for (auto point: points) {
        xmin = point.first < xmin ? point.first : xmin;
        ymin = point.second < ymin ? point.second : ymin; 
    }
    return std::pair<int, int>{xmin, ymin};
}

std::pair<int, int> findScaledMax(std::vector<std::pair<int, int>> points){
    int xmax, ymax;
    xmax = ymax = 0;
    for (auto point: points) {
        xmax = point.first > xmax ? point.first : xmax;
        ymax = point.second > ymax ? point.second : ymax; 
    }
    return std::pair<int, int>{xmax, ymax};
}

void scalePoints(int xmin, int ymin, std::vector<std::pair<int, int>>&points) {
    for (auto &point: points) {
        point.first -= xmin;
        point.second -= ymin;
    }
}

void printMap(const std::vector<std::vector<std::pair<int, int>>> &points) {
    for (auto &row: points) {
        for (auto point : row) {
            std::cout << point.first;
        }
        std::cout << std::endl;
    }
}

inline int manhattanDistance(std::pair<int, int> point1, std::pair<int, int> point2) {
    return abs(point1.first - point2.first) + abs(point1.second - point2.second);
}

std::pair<int, int> findClosestPoint(
    const int x, const int y, const std::vector<std::pair<int, int>> points
    ) {
    std::pair<int, int> point_and_distance{0, 1<<20};
    const std::pair<int, int> pos{x, y}; // map position
    int pointID=1;
    for (auto point: points) {
        auto distance = manhattanDistance(pos, point);
        if (distance < point_and_distance.second) {
            point_and_distance.first = pointID;
            point_and_distance.second = distance;
        } else if (distance == point_and_distance.second) {
            point_and_distance.first = -1;
        }
        pointID++;
    }
    return point_and_distance;
}



std::set<int> findValidPoints(std::vector<std::vector<std::pair<int, int>>> map){
    std::map<int, bool> validPoints;
    for (auto row: map) {
        for (auto point: row) {
            validPoints[point.first] = true;
        }
    }
    // check along all edges
    // top row
    for (auto point: map[0]) {
        validPoints[point.first] = false;
    }
    for (auto point: map[map.size()-1]) {
        validPoints[point.first] = false;
    }
    for (auto point: map) {
        validPoints[point[0].first] = false;
        validPoints[point[point.size()-1].first] = false;
    }

    std::set<int> validSet;
    for (auto point: validPoints) {
        if (point.second) {
            validSet.insert(point.first);
        }
    }
    return validSet;
}

int findPoint(const std::set<int> points, const std::vector<std::vector<std::pair<int, int>>> &map) {
    std::map<int, int> pointPopulus;
    for (auto row: map) {
        for (auto point: row) {
            auto it = points.find(point.first);
            if(it != points.end()) {
                pointPopulus[point.first]++;
            }
        }
    }
    int max = 0;
    int value = -1;
    for (auto p : pointPopulus) {
        if (p.second > max) {
            max = p.second;
            value = p.first;
        }
    }
    return max;
}

int main() {
    auto points = loadpoints();
    auto [xmin, ymin] = findmin(points);
    scalePoints(xmin, ymin, points);
    auto [xmax, ymax] = findScaledMax(points);

    // x y coordinate system that holds a pair, representing the closest point and its distance
    std::vector<std::vector< std::pair<int, int> >> map;
    map.reserve(xmax);
    for (int i = 0; i < xmax; i++){
        map.push_back(std::vector<std::pair<int, int>>{});
        map.at(i).reserve(ymax);
        for (int j = 0; j < ymax; j++) {
            map.at(i).push_back(std::pair<int, int>(0, xmax+ymax));
        }
    };
    
    for (auto x = 0; x < xmax; x++) {
        for (auto y = 0; y < ymax; y++) {
            map[x][y] = findClosestPoint(x, y, points);
        }
    }

    // a point is invalidated if it is closest to any point on the periphery
    auto validPoints = findValidPoints(map);
    for (auto p: validPoints) {
        std::cout << p << std::endl;
    }
    std::cout << "Most sparse inner point " << findPoint(validPoints, map) << std::endl;
    std::cout << xmin << ", " << xmax << ", " << ymin << ", " << ymax << std::endl;


    /*
    Part 2
    */
    std::vector<std::vector<int>> totalDistance;
    totalDistance.reserve(xmax);

    for (int i = 0; i < xmax; i++){
        totalDistance.push_back(std::vector<int>{});
        totalDistance.at(i).reserve(ymax);
        for (int j = 0; j < ymax; j++){
            totalDistance.at(i).push_back(0);
        }
    }

    for(auto i=0; i < xmax; i++){
        for (auto j = 0; j < ymax; j++) {
            for (auto point: points) {
                totalDistance[i][j] += manhattanDistance(std::pair<int, int>{i, j}, point);
            }
        }
    }
    int total = 0;
    for(auto i=0; i < xmax; i++){
        for (auto j = 0; j < ymax; j++) {
            if(totalDistance[i][j] < 10000){
                total++;
            }
        }
    }
    std::cout << total << std::endl;
    return 0;
}