merge mzuenni changes

8 files changed, 237 insertions, 9 deletions

diff --git a/test/other/bitOps.cpp b/test/other/bitOps.cpp
new file mode 100644
index 0000000..44f6297
--- /dev/null
+++ b/test/other/bitOps.cpp
@@ -0,0 +1,59 @@
+#include "../util.h"
+#include <other/bitOps.cpp>
+
+void test_subsets() {
+	int queries = 0;
+	for (int i = 0; i < 1000'000; i++) {
+		int mask = 0;
+		int limBits = Random::integer<int>(1, 15);
+		for (int j = 0; j < limBits; j++) {
+			mask |= 1 << Random::integer<int>(0, 31);
+		}
+
+		int expeced = 1 << __builtin_popcount(mask);
+		int last = -1;
+		int seen = 1;
+		subsets(mask, [&](int active){
+			if (active <= 0) cerr << "error active: " << active << FAIL;
+			if (last >= 0 && active >= last) cerr << "error active: " << active  << ", last: " << last << FAIL;
+			last = active;
+			seen++;
+		});
+		if (expeced != seen) cerr << "got: " << seen << ", expeced: " << expeced << FAIL;
+		queries++;
+	}
+	cerr << "tested subsets queries: " << queries << endl;
+}
+
+ll naive(ll x) {
+	vector<ll> bits;
+	for (ll i = 0; i < 64; i++) {
+		bits.push_back(x & 1);
+		x >>= 1;
+	}
+	reverse(all(bits));
+	next_permutation(all(bits));
+	reverse(all(bits));
+	x = 0;
+	for (ll i = 0, j = 1; i < 64; i++, j <<= 1) {
+		if (bits[i] != 0) x |= j;
+	}
+	return x;
+}
+
+void test_nextPerm() {
+	int queries = 0;
+	for (int i = 0; i < 1000'000; i++) {
+		ll x = 4;//Random::integer<ll>(1, LL::INF);
+		ll got = nextPerm(x);
+		ll expeced = naive(x);
+		if (got != expeced) cerr << x << ": got: " << got << ", expeced: " << expeced << FAIL;
+		queries++;
+	}
+	cerr << "tested nextPerm queries: " << queries << endl;
+}
+
+int main() {
+	test_subsets();
+	test_nextPerm();
+}
\ No newline at end of file
diff --git a/test/other/bitOps.cpp.awk b/test/other/bitOps.cpp.awk
new file mode 100644
index 0000000..f1abcfb
--- /dev/null
+++ b/test/other/bitOps.cpp.awk
@@ -0,0 +1,9 @@
+/for \(int subset/ {
+	print "template<typename F>"
+	print "void subsets(int bitmask, F&& f) {"
+}
+/\/\/ Nächste Permutation/ {
+	print "	{f(subset);}"
+	print "}"
+}
+{ print }
diff --git a/test/other/divideAndConquer.cpp b/test/other/divideAndConquer.cpp
index a6fda9d..6d1b444 100644
--- a/test/other/divideAndConquer.cpp
+++ b/test/other/divideAndConquer.cpp
@@ -1,5 +1,5 @@
 #include "../util.h"
-constexpr ll inf = LL::INF;
+constexpr ll INF = LL::INF;
 #include <other/divideAndConquer.cpp>
 
 vector<vector<ll>> gen(int n) {
@@ -43,7 +43,7 @@ vector<vector<ll>> genQuick(int n) {
 }
 
 /*ll naive(int n, int m) {
-	vector<vector<ll>> state(m+1, vector<ll>(n+1, inf));
+	vector<vector<ll>> state(m+1, vector<ll>(n+1, INF));
 	state[0][0] = 0;
 	for (int i = 1; i <= m; i++) {
 		for (int j = 1; j <= n; j++) {
@@ -56,9 +56,9 @@ vector<vector<ll>> genQuick(int n) {
 }*/
 
 vector<ll> naive(int n) {
-	vector<vector<ll>> state(n+1, vector<ll>(n+1, inf));
+	vector<vector<ll>> state(n+1, vector<ll>(n+1, INF));
 	state[0][0] = 0;
-	vector<ll> res(n+1, inf);
+	vector<ll> res(n+1, INF);
 	for (int i = 1; i <= n; i++) {
 		for (int j = 1; j <= n; j++) {
 			for (int k = 1; k <= j; k++) {
diff --git a/test/other/fastSubsetSum.cpp b/test/other/fastSubsetSum.cpp
new file mode 100644
index 0000000..c61b1ea
--- /dev/null
+++ b/test/other/fastSubsetSum.cpp
@@ -0,0 +1,49 @@
+#include "../util.h"
+#include <other/fastSubsetSum.cpp>
+
+int subsetSum(vector<int> w, int t){
+	vector<bool> dp(t+1);
+	dp[0] = true;
+	for(int x : w){
+		for(int i = t; i >= x; i--){
+			dp[i] = dp[i] || dp[i-x];
+		}
+	}
+	int ma = 0;
+	for(int i = 0; i <= t; i++){
+		if(dp[i]) ma = i;
+	}
+	return ma;
+}
+
+void stress_test() {
+	int queries = 0;
+	for (int test = 0; test < 10'000; test++) {
+		int n = Random::integer<int>(1, 20);
+		int t = Random::integer<int>(1, 500);
+		vector<int> w = Random::integers<int>(n, 0, 50);
+		int got = fastSubsetSum(w, t);
+		int expected = subsetSum(w, t);
+		if(got != expected) cerr << "got: " << got << " expected: " << expected << FAIL;
+		queries++;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+void performance_test() {
+	timer t;
+	int n = 10'000, a = 10'000;
+	vector<int> w = Random::integers<int>(n, 0, a);
+	int target = 10'000'000;
+	t.start();
+	hash_t hash = fastSubsetSum(w, target);
+	t.stop();
+	if (t.time > 750) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/other/josephus2.cpp b/test/other/josephus2.cpp
index d28fe0d..85a9d28 100644
--- a/test/other/josephus2.cpp
+++ b/test/other/josephus2.cpp
@@ -31,7 +31,7 @@ void performance_test() {
 		hash += rotateLeft(1'000'000'000'000'000'000ll + i);
 	}
 	t.stop();
-	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	if (t.time > 750) cerr << "too slow: " << t.time << FAIL;
 	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
 }
 
diff --git a/test/other/knuth.cpp b/test/other/knuth.cpp
index d469ceb..aaf5059 100644
--- a/test/other/knuth.cpp
+++ b/test/other/knuth.cpp
@@ -1,5 +1,5 @@
 #include "../util.h"
-constexpr ll inf = LL::INF;
+constexpr ll INF = LL::INF;
 #include <other/knuth.cpp>
 
 vector<vector<ll>> gen(int n) {
@@ -43,7 +43,7 @@ vector<vector<ll>> genQuick(int n) {
 }
 
 /*ll naive(int n, int m, const vector<vector<ll>>& C) {
-	vector<vector<ll>> state(m+1, vector<ll>(n+1, inf));
+	vector<vector<ll>> state(m+1, vector<ll>(n+1, INF));
 	state[0][0] = 0;
 	for (int i = 1; i <= m; i++) {
 		for (int j = 1; j <= n; j++) {
@@ -56,9 +56,9 @@ vector<vector<ll>> genQuick(int n) {
 }*/
 
 vector<ll> naive(int n, const vector<vector<ll>>& C) {
-	vector<vector<ll>> state(n+1, vector<ll>(n+1, inf));
+	vector<vector<ll>> state(n+1, vector<ll>(n+1, INF));
 	state[0][0] = 0;
-	vector<ll> res(n+1, inf);
+	vector<ll> res(n+1, INF);
 	for (int i = 1; i <= n; i++) {
 		for (int j = 1; j <= n; j++) {
 			for (int k = 1; k <= j; k++) {
diff --git a/test/other/pbs.cpp b/test/other/pbs.cpp
new file mode 100644
index 0000000..ba3b9d0
--- /dev/null
+++ b/test/other/pbs.cpp
@@ -0,0 +1,103 @@
+#include "../util.h"
+
+struct Union {
+    vector<int> a;
+
+    Union(int n) : a(n, -1) {}
+
+    int find(int i) {
+        return a[i] < 0 ? i : a[i] = find(a[i]);
+    }
+
+    void join(int i, int j) {
+        i = find(i), j = find(j);
+        if (i == j) return;
+        a[j] = i;
+    }
+
+    bool same(int i, int j) {
+        return find(i) == find(j);
+    }
+};
+
+int n;
+Union un(0);
+void reset() {
+    un = Union(n);
+}
+
+vector<pair<int, int>> edges;
+void do_step(int i) {
+    auto [u, v] = edges[i];
+    un.join(u, v);
+}
+
+vector<pair<int, int>> queries;
+bool test(int i) {
+    auto [u, v] = queries[i];
+    return un.same(u, v);
+}
+
+#include <other/pbs.cpp>
+void stress_test() {
+	for (int it = 0; it < 100'000; it++) {
+        n = Random::integer(2, 31);
+        int Q = Random::integer(2, 31);
+        int MAX_OPERATIONS = n-1;
+
+        edges.clear();
+        for (int i=1; i<n; i++) {
+            edges.emplace_back(Random::integer(0, i), i);
+        }
+        shuffle(all(edges), Random::rng);
+        queries.clear();
+        for (int i=0; i<Q; i++) {
+            auto x = Random::distinct(2, n);
+            queries.emplace_back(x[0], x[1]);
+        }
+        vector<int> ans = pbs(Q, MAX_OPERATIONS);
+
+        vector<int> correct(Q, -1);
+        Union un2(n);
+        for (int j=0; j<MAX_OPERATIONS; j++) {
+            un2.join(edges[j].first, edges[j].second);
+            for (int k=0; k<Q; k++) if (correct[k] == -1) {
+                if (un2.same(queries[k].first, queries[k].second)) {
+                    correct[k] = j;
+                }
+            }
+        }
+
+        if (ans != correct) cerr << "Failed stress test" << FAIL;
+	}
+}
+
+void performance_test() {
+    n = 300'000;
+    constexpr int Q = 300'000;
+    int MAX_OPERATIONS = n-1;
+    edges.clear();
+    for (int i=1; i<n; i++) {
+        edges.emplace_back(Random::integer(0, i), i);
+    }
+    shuffle(all(edges), Random::rng);
+    queries.clear();
+    for (int i=0; i<Q; i++) {
+        auto x = Random::distinct(2, n);
+        queries.emplace_back(x[0], x[1]);
+    }
+
+    timer t;
+    t.start();
+    vector<int> ans = pbs(Q, MAX_OPERATIONS);
+    t.stop();
+    ll hash = accumulate(all(ans), 0LL);
+
+	if (t.time > 700) cerr << "too slow: " << t.time << FAIL;
+    cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+    stress_test();
+    performance_test();
+}
diff --git a/test/other/pbs.cpp.awk b/test/other/pbs.cpp.awk
new file mode 100644
index 0000000..3084ebd
--- /dev/null
+++ b/test/other/pbs.cpp.awk
@@ -0,0 +1,8 @@
+BEGIN { print "vector<int> pbs(int Q, int MAX_OPERATIONS) {" }
+{ 
+    sub(/\/\* requirement already fulfilled \*\//, "test(i)")
+    sub(/\/\/ simulation step/, "do_step(step);")
+    sub(/\/\/ reset simulation/, "reset();")
+}
+{ print }
+END { print "return high; }" }