AdventOfCode2024/Aufgabe 6/main.cpp

#include <iostream>
#include <vector>
#include <fstream>
#include <omp.h>

struct Point {
    int x;
    int y;

    Point(int x, int y) : x(x), y(y) {}

    bool isValid(int mapSizeX, int mapSizeY) {
        if(x >= 0 && x < mapSizeX && y >= 0 && y < mapSizeY) {
            return true;
        }
        return false;
    }
};

enum Direction {
    NORTH = 0,
    EAST = 1,
    SOUTH = 2,
    WEST = 3
};

struct Guard {
    Point currentPosition;
    Direction currentDirection;

    Guard(Point currentPosition, Direction currentDirection) : currentPosition(currentPosition),
                                                                currentDirection(currentDirection) {}
};

std::vector<std::string> readTextFromFile(const std::string& fileName) {
    std::vector<std::string> lines;
    std::ifstream file(fileName);
    if (!file) {  // Überprüft, ob die Datei geöffnet werden konnte
        std::cerr << "Fehler: Datei konnte nicht geöffnet werden: " << fileName << std::endl;
        return lines;
    }
    std::string s;
    while(getline(file, s)) {
        lines.push_back(s);
    }
    return lines;
}

Point calcGuardPositionFromInput(const std::vector<std::string>& input) {
    for(int y =0; y < input.size(); y++) {
        for(int x =0; x < input[y].size(); x++) {
            if(input[y][x] == '^' || input[y][x] == '<' || input[y][x] == '>' || input[y][x] == 'v') {
                return {x, y};
            }
        }
    }
    return {-1,-1};
}

std::vector<Point> calcObstaclePositionsFromInput(const std::vector<std::string>& input) {
    std::vector<Point> obstaclePositions;
    for(int y =0; y < input.size(); y++) {
        for(int x =0; x < input[y].size(); x++) {
            if(input[y][x] == '#') {
                obstaclePositions.emplace_back(x, y);
            }
        }
    }
    return obstaclePositions;
}

Point calcUpdatedGuardPosition(Point& currentPosition, Direction direction) {
    int x = currentPosition.x;
    int y = currentPosition.y;
    switch (direction) {
        case NORTH:
            y--;
            break;
        case WEST:
            x--;
            break;
        case SOUTH:
            y++;
            break;
        case EAST:
            x++;
            break;
    }
    return {x, y};
}

bool hasGuardReachedObstacle(Point guardPosition, const std::vector<Point>& map) {
    for(Point obstacles : map) {
        if(obstacles.x == guardPosition.x && obstacles.y == guardPosition.y) {
            return true;
        }
    }
    return false;
}


std::vector<Point> calcGuardPositions(Guard guard, const std::vector<Point>& map, int mapSizeX, int mapSizeY) {
    std::vector<Point> guardPositions;
    while(guard.currentPosition.isValid(mapSizeX, mapSizeY)) {
        bool duplicated = false;
        for(const auto& currentPos : guardPositions) {
            if(currentPos.x == guard.currentPosition.x && currentPos.y == guard.currentPosition.y) {
                duplicated = true;
            }
        }

        if(!duplicated) {
            guardPositions.push_back(guard.currentPosition);
        }

        Point nextPosition = calcUpdatedGuardPosition(guard.currentPosition, guard.currentDirection);
        if(hasGuardReachedObstacle(nextPosition, map)) {
            guard.currentDirection = static_cast<Direction>((guard.currentDirection + 1) % 4);
        } else {
            guard.currentPosition = nextPosition;
        }
    }
    return guardPositions;
}

/**std::vector<Point> calcObstaclePositionForCycle(Guard initialGuard, const std::vector<Point>& map, int mapSizeX, int mapSizeY) {
    Guard guard = initialGuard;
    std::vector<Point> possibleObstaclePositions;

    #pragma omp parallel
        // Lokaler Vector für jeden Thread
        std::vector<Point> localObstaclePositions;
        for(int x=0; x < mapSizeX; x++) {
            #pragma omp for collapse(2) schedule(dynamic)
            for(int y =0; y < mapSizeY; y++) {
                Guard localGuard = guard;
                std::vector<Point> guardPositions;
                std::vector<Point> currentMap = map;
                currentMap.emplace_back(x, y);
                while(localGuard.currentPosition.isValid(mapSizeX, mapSizeY)) {
                    guardPositions.push_back(guard.currentPosition);

                    if(guardPositions.size() > (mapSizeX * mapSizeY)) {
                        localObstaclePositions.emplace_back(x, y);
                        break;
                    }

                    Point nextPosition = calcUpdatedGuardPosition(localGuard.currentPosition, localGuard.currentDirection);
                    if(hasGuardReachedObstacle(nextPosition, currentMap)) {
                        localGuard.currentDirection = static_cast<Direction>((localGuard.currentDirection + 1) % 4);
                    } else {
                        localGuard.currentPosition = nextPosition;
                    }
                }
                guard = initialGuard;
            }
        }
        // Zusammenführen der lokalen Ergebnisse in den globalen Vector
        #pragma omp critical
        possibleObstaclePositions.insert(possibleObstaclePositions.end(), localObstaclePositions.begin(), localObstaclePositions.end());
    return possibleObstaclePositions;
}**/

std::vector<Point> calculateObstaclePositions(Guard initialGuard, std::vector<Point> map, int mapSizeX, int mapSizeY) {
    Guard guard = initialGuard;
    std::vector<Point> possibleObstaclePositions;

    // OpenMP für Parallelisierung der äußeren Schleife
#pragma omp parallel
    {
        // Lokaler Vector für jeden Thread
        std::vector<Point> localObstaclePositions;

#pragma omp for collapse(2) schedule(dynamic)
        for (int x = 0; x < mapSizeX; x++) {
            for (int y = 0; y < mapSizeY; y++) {
                Guard localGuard = guard; // Kopie des Guards für jeden Thread
                std::vector<Point> guardPositions;
                std::vector<Point> currentMap = map; // Lokale Kopie der Karte
                currentMap.emplace_back(x, y);

                while (localGuard.currentPosition.isValid(mapSizeX, mapSizeY)) {
                    guardPositions.push_back(localGuard.currentPosition);

                    if (guardPositions.size() > (mapSizeX * mapSizeY)) {
                        localObstaclePositions.emplace_back(x, y);
                        break;
                    }

                    Point nextPosition = calcUpdatedGuardPosition(localGuard.currentPosition, localGuard.currentDirection);
                    if (hasGuardReachedObstacle(nextPosition, currentMap)) {
                        localGuard.currentDirection = static_cast<Direction>((localGuard.currentDirection + 1) % 4);
                    } else {
                        localGuard.currentPosition = nextPosition;
                    }
                }
            }
        }

        // Zusammenführen der lokalen Ergebnisse in den globalen Vector
#pragma omp critical
        possibleObstaclePositions.insert(possibleObstaclePositions.end(), localObstaclePositions.begin(), localObstaclePositions.end());
    }

    return possibleObstaclePositions;
}

int main() {

    std::vector<std::string> input = readTextFromFile("../input.txt");
    Point initialGuardPos = calcGuardPositionFromInput(input);
    std::vector<Point> obstaclePositions = calcObstaclePositionsFromInput(input);
    Guard guard = Guard(initialGuardPos, NORTH);
    auto visitedPoints = calcGuardPositions(guard, obstaclePositions, input[0].size(), input.size());

    std::cout << "The guard visited " << visitedPoints.size() << " points!" << std::endl;

    auto possibleObstaclePositions = calculateObstaclePositions(guard, obstaclePositions, input[0].size(), input.size());
    std::cout << "There are  " << possibleObstaclePositions.size() << " possible positions!" << std::endl;
    return 0;
}