AdventOfCode2024/Aufgabe 5/main.cpp

#include <iostream>
#include <vector>
#include <fstream>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <omp.h>


struct Rule{
    int first;
    int second;

    Rule(int first, int second) : first(first), second(second) {}
};

struct Update {
    std::vector<int> pages;

    explicit Update(const std::vector<int> &pages) : pages(pages) {}
};

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;
}

std::vector<std::string> splitString(const std::string& input, char ch) {
    std::vector<std::string> splittedString;
    size_t pos = input.find(ch);
    size_t initialPos = 0;

    while(pos != std::string::npos) {
        splittedString.push_back(input.substr(initialPos, pos - initialPos));
        initialPos = pos + 1;
        pos = input.find(ch, initialPos);
    }

    splittedString.push_back(input.substr(initialPos, std::min(pos, input.size()) - initialPos));

    return splittedString;
}

std::vector<Rule> parseRules(std::vector<std::string>& input) {
    std::vector<Rule> rules;

    for(const auto& line : input) {
        if(line.find('|') != std::string::npos) {
            std::vector<std::string> splittedLine = splitString(line, '|');
            int first = std::stoi(splittedLine[0]);
            int second = std::stoi(splittedLine[1]);
            rules.emplace_back(first, second);
        }
    }
    return rules;
}

std::vector<Update> parseUpdates(std::vector<std::string>& input) {
    std::vector<Update> updates;
    for(const auto& line : input) {
        if(line.find(',') != std::string::npos) {
            std::vector<std::string> splittedString = splitString(line, ',');
            std::vector<int> pages;
            for(const auto& page : splittedString) {
                pages.push_back(std::stoi(page));
            }
            updates.emplace_back(pages);
        }
    }
    return updates;
}

std::vector<int> topologicalSort(const std::vector<Rule>& rules) {
    std::unordered_map<int, std::unordered_set<int>> adjList;
    std::unordered_map<int, int> inDegree;

    // Step 1: Build the graph
    for(const auto& rule : rules) {
        adjList[rule.first].insert(rule.second);
        inDegree[rule.second]++;

        if(inDegree.find(rule.first) == inDegree.end()) {
            inDegree[rule.first] = 0;
        }
    }

    // Step 2: Initialize queue with nodes having in degree 0
    std::queue<int> zeroInDegreeQueue;
    for(const auto& pair : inDegree) {
        if(pair.second == 0) {
            zeroInDegreeQueue.push(pair.first);
        }
    }

    //Step 3: Process nodes and generate topological order
    std::vector<int> topologicalOrder;
    while(!zeroInDegreeQueue.empty()) {
        int current = zeroInDegreeQueue.front();
        zeroInDegreeQueue.pop();
        topologicalOrder.push_back(current);

        if(adjList.find(current) != adjList.end()) {
            for(const auto& neighbor : adjList[current]) {
                inDegree[neighbor]--;
                if(inDegree[neighbor] == 0) {
                    zeroInDegreeQueue.push(neighbor);
                }
            }
        }
    }
    return topologicalOrder;
}

int indexOf(std::vector<int> vec, int element) {
    for(int i=0; i< vec.size(); i++) {
        if(vec[i] == element) {
            return i;
        }
    }
    return -1;
}

//Checks whether a is before b in topological order
bool isBefore(const std::vector<Rule>& rules, int a, int b) {
    for(const Rule& rule: rules) {
        if(rule.second == a && rule.first == b) {
            return false;
        }
    }
    return true;
}

bool isAfter(const std::vector<Rule>& rules, int a, int b) {
    for(const Rule& rule : rules) {
        if(rule.second == b && rule.first == a) {
            return false;
        }
    }
    return true;
}

bool isUpdateCorrect(const Update& update, const std::vector<Rule>& rules) {
    std::vector<int> topologicalOrder = topologicalSort(rules);
    //Check if all pages are printed after the previous one
    for(int i=0; i<update.pages.size(); i++) {
        for(int j=0; j<i; j++) {
            if(!isBefore(rules, update.pages[j], update.pages[i])) {
                return false;
            }
        }

        for(int j=i+1; j<update.pages.size(); j++) {
            if(!isAfter(rules, update.pages[j], update.pages[i])) {
                return false;
            }
        }
    }
    return true;
}

std::vector<Update> determineCorrectUpdates(std::vector<Update>& updates, std::vector<Rule>& rules) {
    std::vector<Update> validUpdates;
    for(const Update& update : updates) {
        if(isUpdateCorrect(update, rules)) {
            validUpdates.push_back(update);
        }
    }
    return validUpdates;
}

std::vector<Update> determineIncorrectUpdates(std::vector<Update>& updates, std::vector<Rule>& rules) {
    std::vector<Update> validUpdates;
    for(const Update& update : updates) {
        if(!isUpdateCorrect(update, rules)) {
            validUpdates.push_back(update);
        }
    }
    return validUpdates;
}

Update correctUpdate(const Update& update, std::vector<Rule>& rules) {
    Update correctedUpdate = update;
    for(int i=0; i<correctedUpdate.pages.size(); i++) {
        for(int j=0; j<i; j++) {
            if(!isBefore(rules, correctedUpdate.pages[j], correctedUpdate.pages[i])) {
                std::swap(correctedUpdate.pages[j], correctedUpdate.pages[i]);
            }
        }

        for(int j=i+1; j<correctedUpdate.pages.size(); j++) {
            if(!isAfter(rules, correctedUpdate.pages[j], correctedUpdate.pages[i])) {
                std::swap(correctedUpdate.pages[j], correctedUpdate.pages[i]);
            }
        }
    }
    return correctedUpdate;
}

std::vector<Update> correctUpdates(std::vector<Update>& updates, std::vector<Rule>& rules) {
    std::vector<Update> correctedUpdates;
    for(const Update& update : updates) {
        correctedUpdates.push_back(correctUpdate(update, rules));
    }
    return correctedUpdates;
}

int calcMiddleSum(std::vector<Update>& updates) {
    int sum = 0;
    for(const auto& update: updates) {
        sum += update.pages[update.pages.size()/2];
    }
    return sum;
}

int main() {
    std::vector<std::string> input = readTextFromFile("../input.txt");
    std::vector<Rule> rules = parseRules(input);
    std::vector<Update> updates = parseUpdates(input);
    std::vector<Update> validUpdates = determineCorrectUpdates(updates, rules);
    int result = calcMiddleSum(validUpdates);
    std::cout << "The middle sum of the correct Updates is: " << result << std::endl;

    std::vector<Update> incorrectUpdates = determineIncorrectUpdates(updates, rules);
    std::vector<Update> correctedUpdates = correctUpdates(incorrectUpdates, rules);
    int result2 = calcMiddleSum(correctedUpdates);
    std::cout << "The middle sum of the corrected Updates is: " << result2 << std::endl;
    return 0;
}