summaryrefslogtreecommitdiff
path: root/test/other
diff options
context:
space:
mode:
Diffstat (limited to 'test/other')
-rw-r--r--test/other/bitOps.cpp59
-rw-r--r--test/other/bitOps.cpp.awk9
-rw-r--r--test/other/divideAndConquer.cpp8
-rw-r--r--test/other/fastSubsetSum.cpp49
-rw-r--r--test/other/josephus2.cpp2
-rw-r--r--test/other/knuth.cpp8
-rw-r--r--test/other/pbs.cpp103
-rw-r--r--test/other/pbs.cpp.awk8
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; }" }
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 16:42:33 +0000