Algorithms : complete 05-advanced_algorithms_and_complexity 04-np-completenessalgos

1 files changed, 157 insertions, 4 deletions

diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/04-reschedule_exams/reschedule_exams.cpp b/05-advanced_algorithms_and_complexity/04-np-completeness/04-reschedule_exams/reschedule_exams.cpp
index b3ff8eb..5a3a875 100644
--- a/05-advanced_algorithms_and_complexity/04-np-completeness/04-reschedule_exams/reschedule_exams.cpp
+++ b/05-advanced_algorithms_and_complexity/04-np-completeness/04-reschedule_exams/reschedule_exams.cpp
@@ -1,8 +1,104 @@
 #include <iostream>
 #include <vector>
 #include <string>
+#include <bits/stdc++.h>
 using namespace std;
 
+struct Clause {
+    int firstVar;
+    int secondVar;
+};
+
+struct Vertex {
+    int index;
+    int lowLink;
+    bool onStack;
+};
+
+struct TwoSatisfiability {
+    int numVars;
+    int x;
+    vector<Clause> &clauses;
+    stack<int> st;
+    vector<Vertex> vertices;
+    vector<vector<int> > adj;
+
+    TwoSatisfiability(int n, vector<Clause> &clauses) :
+        numVars(n),
+        clauses(clauses),
+        x(0),
+        vertices(n * 2, {-1, -1, false}),
+        adj(n * 2, vector<int>())
+    {
+    }
+
+    bool tarjan(int i, vector<int> &result) {
+        Vertex &v = vertices[i];
+        v.index = x;
+        v.lowLink = x;
+        v.onStack = true;
+        st.push(i);
+        x++;
+        for (int a : adj[i]) {
+            Vertex &w = vertices[a];
+            if (w.index == -1) {
+                if (!tarjan(a, result)) return false;
+                v.lowLink = min(v.lowLink, w.lowLink);
+            } else if (w.onStack) {
+                v.lowLink = min(v.lowLink, w.index);
+            }
+        }
+        // is a SCC root node
+        if (v.lowLink == v.index) {
+            for (;;) {
+                int i = st.top();
+                int iv = inv(i);
+                if (vertices[iv].index == v.index) return false;
+                st.pop();
+                if (i < numVars) {
+                    if (result[i] == -1)
+                        result[i] = 1;
+                } else {
+                    if (result[iv] == -1)
+                        result[iv] = 0;
+                }
+                vertices[i].onStack = false;
+                if (vertices[i].index == v.index) {
+                    break;
+                }
+            }
+        }
+        return true;
+    }
+
+    inline int idx(int v) { return (v > 0 ? (v - 1) : (numVars - v - 1)); }
+    inline int inv(int i) { return i + ((i < numVars) ? numVars : -numVars); }
+
+    bool isSatisfiable(vector<int>& result) {
+
+        // construct the implication graph        (l1 l2) -> !l1 ->l2 !l2->l1
+        for(Clause clause : clauses) {
+            adj[idx(-clause.firstVar)].push_back(idx(clause.secondVar));
+            adj[idx(-clause.secondVar)].push_back(idx(clause.firstVar));
+        }
+
+        // find SCC's of graph
+        // int x = 0;
+        for (int i = 0; i < vertices.size(); i++) {
+            Vertex &v = vertices[i];
+            if (v.index == -1)  {
+                if (!tarjan(i, result)) return false;
+            }
+        }
+
+        return true;
+    }
+};
+
+enum Color { R=1, G, B };
+
+static inline int var(int vertex, int color) { return vertex * 3 + color; }
+
 /*
   Arguments:
     * `n` - the number of vertices.
@@ -13,11 +109,68 @@ using namespace std;
     * Otherwise, return value is an empty string.
 */
 string assign_new_colors(int n, vector<pair<int, int>> edges, string colors) {
-    // Insert your code here.
-    if (n % 3 == 0) {
+
+    // cout << " N      : " << n << endl;
+    // cout << " edges  : " << edges.size() << endl;
+    // cout << " colors : " << colors << endl;
+
+    int vars = 3 * n;
+    vector<Clause> clauses;
+
+    // for each vertex
+    for (int i = 0; i < n; i++) {
+        //  each node must be of a different color than its initial state
+        int v1, v2, v3;
+        if (colors[i] == 'R') {
+            v1 = var(i, R);
+            v2 = var(i, G);
+            v3 = var(i, B);
+        } else if (colors[i] == 'G') {
+            v1 = var(i, G);
+            v2 = var(i, B);
+            v3 = var(i, R);
+        } else {
+            v1 = var(i, B);
+            v2 = var(i, R);
+            v3 = var(i, G);
+        }
+        clauses.push_back({-v1, -v1}); // !1 || !1 => different from initial color
+        clauses.push_back({ v2,  v3}); //  2 ||  3 => one of the other
+        clauses.push_back({-v2, -v3}); // !2 || !3 => not both
+    }
+    //  both node of an edge cannot be of the same color
+    for (auto &p : edges) {
+        int i = p.first - 1;
+        int j = p.second - 1;
+        clauses.push_back({-var(i, R), -var(j, R)});
+        clauses.push_back({-var(i, G), -var(j, G)});
+        clauses.push_back({-var(i, B), -var(j, B)});
+    }
+
+    // cout << "clauses : " << clauses.size() << endl;
+    // cout << "vars    : " << vars << endl;
+    TwoSatisfiability twoSat(vars, clauses);
+
+    vector<int> result(vars, -1);
+    if (twoSat.isSatisfiable(result)) {
+        // cout << "SATISFIABLE" << endl;
+        // for (int i = 1; i <= vars; ++i) {
+        //     if (result[i-1]) {
+        //         cout << i;
+        //     } else {
+        //         cout << -i;
+        //     }
+        //     if (i < vars) {
+        //         cout << " ";
+        //     } else {
+        //         cout << endl;
+        //     }
+        // }
         string new_colors;
-        for (int i = 0; i < n; i++) {
-            new_colors.push_back("RGB"[i % 3]);
+        for (int i = 0; i < vars; ++i) {
+            if (result[i]) {
+                new_colors.push_back("RGB"[i % 3]);
+            }
         }
         return new_colors;
     } else {