1494. Parallel Courses II

Info

https://leetcode.com/problems/parallel-courses-ii/description/

// https://leetcode.com/problems/parallel-courses-ii/description/
 
#include <bit>
#include <cstdint>
#include <iostream>
#include <optional>
#include <print>
#include <utility>
#include <vector>
 
template<typename Callback>
void iterateKSetBits(uint64_t bitMask, int k, Callback&& callback) {
    uint32_t subMask = 0;
    while (k--) {
        subMask |= std::bit_floor(bitMask ^ subMask);
    }
 
    auto prevStart = subMask;
 
    while (true) {
        callback(subMask);
 
        if (bitMask == subMask) {
            return;
        }
 
        auto a = (subMask & -subMask);
        auto b = std::bit_floor(bitMask & (a - 1));
 
        if (b) {
            subMask ^= a ^ b;
        } else {
            auto c = std::bit_floor(bitMask);
            bitMask ^= c;
            subMask = prevStart ^ c;
            subMask |= std::bit_floor(bitMask ^ subMask);
            prevStart = subMask;
        }
    }
}
 
template<typename Callback>
void iterateSetBits(uint64_t bitMask, Callback&& callback) {
    while (bitMask) {
        auto setBit = bitMask & -bitMask;
        callback(setBit);
        bitMask ^= setBit;
    }
}
 
int parallelCourses2(int n, std::vector<std::vector<int>> const& relations, int k) {
    auto dp = std::vector<std::optional<int>>(1 << n, std::nullopt);
 
    std::vector<int> prerequisites(n, 0);
    for (auto const& relation: relations) {
        prerequisites[relation[1] - 1] |= (1 << (relation[0] - 1));
    }
 
    auto dpFunc = [n = n, k = k, &dp = dp, &prerequisites = std::as_const(prerequisites)](this auto&& dpFunc, int coursesTaken) -> int {
        std::println("called | coursesTaken: {:0{}b}", coursesTaken, n);
        auto& dpVal = dp[coursesTaken];
        if (dpVal) {
            std::println("done   | coursesTaken: {:0{}b} | dpVal: {}", coursesTaken, n, *dpVal);
            return *dpVal;
        }
 
        if (coursesTaken == (1 << n) - 1) {
            dpVal = 0;
            std::println("done   | coursesTaken: {:0{}b} | dpVal: {}", coursesTaken, n, *dpVal);
            return *dpVal;
        }
 
        uint64_t nextCourses = 0;
        iterateSetBits(((uint64_t(1) << n) - 1) ^ coursesTaken, [&](auto const& notTakenCourseMask) {
            auto notTakenCourse = std::countr_zero(notTakenCourseMask);
            if ((coursesTaken & prerequisites[notTakenCourse]) == prerequisites[notTakenCourse]) {
                nextCourses |= (1 << notTakenCourse);
            }
        });
 
        iterateKSetBits(nextCourses, k, [&](auto const& subMask) {
            auto minSemesters = 1 + dpFunc(coursesTaken ^ subMask);
            if (dpVal) {
                dpVal = std::min(*dpVal, minSemesters);
            } else {
                dpVal = minSemesters;
            }
        });
 
        if (dpVal) {
            std::println("done   | coursesTaken: {:0{}b} | dpVal: {}", coursesTaken, n, *dpVal);
            return *dpVal;
        }
 
        std::println("done   | coursesTaken: {:0{}b} | dpVal: {}", coursesTaken, n, *dpVal);
        return *dpVal;
    };
 
    return dpFunc(0);
}
 
int main() {
    {
        auto minSemesters = parallelCourses2(4, {{2, 1}, {3, 1}, {1, 4}}, 2);
        std::println("minSemesters: {}", minSemesters);
    }
    {
        auto minSemesters = parallelCourses2(5, {{2, 1}, {3, 1}, {4, 1}, {1, 5}}, 2);
        std::println("minSemesters: {}", minSemesters);
    }
}