From 8d11c6c8213f46f0fa19826917c255edd5d43cb1 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sun, 28 Jul 2024 22:54:40 +0200 Subject: Test (#4) * update * moved content in subdir * rename file * add test setup * add test setup * add github action * automaticly test all cpp files * timeout after 10s * setulimit and dont zero memory * test build pdf * install latexmk * update * update * ngerman * fonts * removed old code * add first test * added tests * test in sorted order * more tests * simplified test * more tests * fix suffix tree * fixes and improvements * done ust lst directly * fix swap * add links to pdf * fix constants * add primorial * add comment * various improvements * more tests * added missing stuf * more tests * fix tests * more tests * more tests * more tests * fix recursion? * test trie * more tests * only use python temporarily for listings * only use python temporarily for listings * more tests * fix longestCommonSubstring * more tests * more tests * made code more similiar * fix? * more tests * more tests * more tests * add ahoCorasick test + limit 4GB stack size * more tests * fix test * add additional test * more tests * more tests * fix? * better fix * fix virtual tree * more tests * more tests * recursive closest pair * more tests * decrease limit * new tests * more tests * fix name * more tests * add test * new test * more tests * more tests * more tests * more tests * new test and content * new code * new code * larger tests * fix and test * new test * new test * update pdf * remove comments * new test * more tests * more testcases * more tests * increased limit * more tests * more tests * more tests * new tests * more tests * shortened code * new test * add basic tests for bigint * more tests * removed old files * new test * ignore some files * more auto more ccw * fix test * more tests * fix * new tests * more tests * more tests * stronger test * actually verify delaunay... * more tests * fix header * more tests * run tests parallel? * test parralel? * add --missing * separate workflows * test * is the pdf checked? * separate workflows * fix workflow * more workflows --------- Co-authored-by: Yidi --- test/datastructures/bitset.cpp | 6 + test/datastructures/fenwickTree.cpp | 58 ++++ test/datastructures/fenwickTree2.cpp | 60 ++++ test/datastructures/lazyPropagation.cpp | 61 +++++ test/datastructures/pbds.cpp | 11 + test/datastructures/segmentTree.cpp | 122 +++++++++ test/datastructures/sparseTable.cpp | 51 ++++ test/datastructures/sparseTableDisjoint.cpp | 48 ++++ test/datastructures/stlHashMap.cpp | 4 + test/datastructures/stlTree.cpp | 2 + test/datastructures/unionFind.cpp | 109 ++++++++ test/datastructures/waveletTree.cpp | 75 +++++ test/geometry.h | 140 ++++++++++ test/geometry/antipodalPoints.cpp | 70 +++++ test/geometry/circle.cpp | 116 ++++++++ test/geometry/closestPair.cpp | 69 +++++ test/geometry/closestPair.double.cpp | 66 +++++ test/geometry/convexHull.cpp | 79 ++++++ test/geometry/delaunay.cpp | 144 ++++++++++ test/geometry/formulas.cpp | 127 +++++++++ test/geometry/linesAndSegments.cpp | 240 ++++++++++++++++ test/geometry/polygon.cpp | 296 ++++++++++++++++++++ test/geometry/segmentIntersection.cpp | 88 ++++++ test/geometry/sortAround.cpp | 83 ++++++ test/geometry/triangle.cpp | 146 ++++++++++ test/graph/2sat.cpp | 133 +++++++++ test/graph/LCA_sparse.cpp | 63 +++++ test/graph/TSP.cpp | 67 +++++ test/graph/articulationPoints.bcc.cpp | 78 ++++++ test/graph/articulationPoints.bridges.cpp | 64 +++++ test/graph/articulationPoints.cpp | 85 ++++++ test/graph/bellmannFord.cpp | 70 +++++ test/graph/bitonicTSP.cpp | 49 ++++ test/graph/bitonicTSPsimple.cpp | 49 ++++ test/graph/blossom.cpp | 76 +++++ test/graph/bronKerbosch.cpp | 73 +++++ test/graph/centroid.cpp | 77 ++++++ test/graph/cycleCounting.cpp | 79 ++++++ test/graph/dijkstra.cpp | 64 +++++ test/graph/dinicScaling.cpp | 61 +++++ test/graph/euler.cpp | 87 ++++++ test/graph/floydWarshall.cpp | 90 ++++++ test/graph/havelHakimi.cpp | 65 +++++ test/graph/hopcroftKarp.cpp | 74 +++++ test/graph/kruskal.cpp | 91 ++++++ test/graph/matching.cpp | 62 +++++ test/graph/maxCarBiMatch.cpp | 74 +++++ test/graph/maxWeightBipartiteMatching.cpp | 59 ++++ test/graph/minCostMaxFlow.cpp | 68 +++++ test/graph/pushRelabel.cpp | 61 +++++ test/graph/scc.cpp | 92 +++++++ test/graph/stoerWagner.cpp | 81 ++++++ test/graph/treeIsomorphism.cpp | 126 +++++++++ test/math/berlekampMassey.cpp | 68 +++++ test/math/bigint.cpp | 122 +++++++++ test/math/binomial0.cpp | 31 +++ test/math/binomial1.cpp | 27 ++ test/math/binomial2.cpp | 29 ++ test/math/binomial3.cpp | 31 +++ test/math/chineseRemainder.cpp | 47 ++++ test/math/cycleDetection.cpp | 47 ++++ test/math/discreteLogarithm.cpp | 64 +++++ test/math/discreteNthRoot.cpp | 78 ++++++ test/math/divisors.cpp | 65 +++++ test/math/extendedEuclid.cpp | 41 +++ test/math/gauss.cpp | 118 ++++++++ test/math/gcd-lcm.cpp | 46 ++++ test/math/goldenSectionSearch.cpp | 74 +++++ test/math/inversions.cpp | 43 +++ test/math/inversionsMerge.cpp | 46 ++++ test/math/kthperm.cpp | 38 +++ test/math/kthperm_permIndex.cpp | 21 ++ test/math/legendre.cpp | 43 +++ test/math/lgsFp.cpp | 118 ++++++++ test/math/linearCongruence.cpp | 53 ++++ test/math/linearRecurence.cpp | 54 ++++ test/math/linearSieve.cpp | 71 +++++ test/math/longestIncreasingSubsequence.cpp | 76 +++++ test/math/matrixPower.cpp | 116 ++++++++ test/math/millerRabin.base32.cpp | 137 ++++++++++ test/math/millerRabin.cpp | 129 +++++++++ test/math/modExp.cpp | 42 +++ test/math/modMulIterativ.cpp | 57 ++++ test/math/modPowIterativ.cpp | 42 +++ test/math/multInv.cpp | 40 +++ test/math/permIndex.cpp | 39 +++ test/math/piLegendre.cpp | 40 +++ test/math/piLehmer.cpp | 42 +++ test/math/primeSieve.cpp | 47 ++++ test/math/primitiveRoot.cpp | 82 ++++++ test/math/rho.cpp | 117 ++++++++ test/math/shortModInv.cpp | 39 +++ test/math/simpson.cpp | 63 +++++ test/math/sqrtModCipolla.cpp | 48 ++++ test/math/transforms/andTransform.cpp | 38 +++ test/math/transforms/bitwiseTransforms.cpp | 38 +++ test/math/transforms/fft.cpp | 51 ++++ test/math/transforms/fftMul.cpp | 62 +++++ test/math/transforms/multiplyBitwise.cpp | 55 ++++ test/math/transforms/multiplyFFT.cpp | 55 ++++ test/math/transforms/multiplyNTT.cpp | 56 ++++ test/math/transforms/ntt.cpp | 39 +++ test/math/transforms/orTransform.cpp | 38 +++ test/math/transforms/xorTransform.cpp | 38 +++ test/other/compiletime.cpp | 2 + test/other/divideAndConquer.cpp | 103 +++++++ test/other/fastIO.cpp | 32 +++ test/other/fastIO.in | 2 + test/other/josephus2.cpp | 42 +++ test/other/josephusK.cpp | 43 +++ test/other/knuth.cpp | 103 +++++++ test/other/sos.cpp | 50 ++++ test/other/split.cpp | 24 ++ test/string/ahoCorasick.cpp | 76 +++++ test/string/deBruijn.cpp | 43 +++ test/string/duval.cpp | 85 ++++++ test/string/kmp.cpp | 85 ++++++ test/string/longestCommonSubsequence.cpp | 55 ++++ test/string/lyndon.cpp | 61 +++++ test/string/manacher.cpp | 49 ++++ test/string/rollingHash.cpp | 92 +++++++ test/string/rollingHashCf.cpp | 94 +++++++ test/string/suffixArray.cpp | 61 +++++ test/string/suffixAutomaton.cpp | 62 +++++ test/string/suffixTree.cpp | 50 ++++ test/string/trie.cpp | 58 ++++ test/string/z.cpp | 41 +++ test/template/template.cpp | 1 + test/test.sh | 70 +++++ test/util.h | 411 ++++++++++++++++++++++++++++ 130 files changed, 9185 insertions(+) create mode 100644 test/datastructures/bitset.cpp create mode 100644 test/datastructures/fenwickTree.cpp create mode 100644 test/datastructures/fenwickTree2.cpp create mode 100644 test/datastructures/lazyPropagation.cpp create mode 100644 test/datastructures/pbds.cpp create mode 100644 test/datastructures/segmentTree.cpp create mode 100644 test/datastructures/sparseTable.cpp create mode 100644 test/datastructures/sparseTableDisjoint.cpp create mode 100644 test/datastructures/stlHashMap.cpp create mode 100644 test/datastructures/stlTree.cpp create mode 100644 test/datastructures/unionFind.cpp create mode 100644 test/datastructures/waveletTree.cpp create mode 100644 test/geometry.h create mode 100644 test/geometry/antipodalPoints.cpp create mode 100644 test/geometry/circle.cpp create mode 100644 test/geometry/closestPair.cpp create mode 100644 test/geometry/closestPair.double.cpp create mode 100644 test/geometry/convexHull.cpp create mode 100644 test/geometry/delaunay.cpp create mode 100644 test/geometry/formulas.cpp create mode 100644 test/geometry/linesAndSegments.cpp create mode 100644 test/geometry/polygon.cpp create mode 100644 test/geometry/segmentIntersection.cpp create mode 100644 test/geometry/sortAround.cpp create mode 100644 test/geometry/triangle.cpp create mode 100644 test/graph/2sat.cpp create mode 100644 test/graph/LCA_sparse.cpp create mode 100644 test/graph/TSP.cpp create mode 100644 test/graph/articulationPoints.bcc.cpp create mode 100644 test/graph/articulationPoints.bridges.cpp create mode 100644 test/graph/articulationPoints.cpp create mode 100644 test/graph/bellmannFord.cpp create mode 100644 test/graph/bitonicTSP.cpp create mode 100644 test/graph/bitonicTSPsimple.cpp create mode 100644 test/graph/blossom.cpp create mode 100644 test/graph/bronKerbosch.cpp create mode 100644 test/graph/centroid.cpp create mode 100644 test/graph/cycleCounting.cpp create mode 100644 test/graph/dijkstra.cpp create mode 100644 test/graph/dinicScaling.cpp create mode 100644 test/graph/euler.cpp create mode 100644 test/graph/floydWarshall.cpp create mode 100644 test/graph/havelHakimi.cpp create mode 100644 test/graph/hopcroftKarp.cpp create mode 100644 test/graph/kruskal.cpp create mode 100644 test/graph/matching.cpp create mode 100644 test/graph/maxCarBiMatch.cpp create mode 100644 test/graph/maxWeightBipartiteMatching.cpp create mode 100644 test/graph/minCostMaxFlow.cpp create mode 100644 test/graph/pushRelabel.cpp create mode 100644 test/graph/scc.cpp create mode 100644 test/graph/stoerWagner.cpp create mode 100644 test/graph/treeIsomorphism.cpp create mode 100644 test/math/berlekampMassey.cpp create mode 100644 test/math/bigint.cpp create mode 100644 test/math/binomial0.cpp create mode 100644 test/math/binomial1.cpp create mode 100644 test/math/binomial2.cpp create mode 100644 test/math/binomial3.cpp create mode 100644 test/math/chineseRemainder.cpp create mode 100644 test/math/cycleDetection.cpp create mode 100644 test/math/discreteLogarithm.cpp create mode 100644 test/math/discreteNthRoot.cpp create mode 100644 test/math/divisors.cpp create mode 100644 test/math/extendedEuclid.cpp create mode 100644 test/math/gauss.cpp create mode 100644 test/math/gcd-lcm.cpp create mode 100644 test/math/goldenSectionSearch.cpp create mode 100644 test/math/inversions.cpp create mode 100644 test/math/inversionsMerge.cpp create mode 100644 test/math/kthperm.cpp create mode 100644 test/math/kthperm_permIndex.cpp create mode 100644 test/math/legendre.cpp create mode 100644 test/math/lgsFp.cpp create mode 100644 test/math/linearCongruence.cpp create mode 100644 test/math/linearRecurence.cpp create mode 100644 test/math/linearSieve.cpp create mode 100644 test/math/longestIncreasingSubsequence.cpp create mode 100644 test/math/matrixPower.cpp create mode 100644 test/math/millerRabin.base32.cpp create mode 100644 test/math/millerRabin.cpp create mode 100644 test/math/modExp.cpp create mode 100644 test/math/modMulIterativ.cpp create mode 100644 test/math/modPowIterativ.cpp create mode 100644 test/math/multInv.cpp create mode 100644 test/math/permIndex.cpp create mode 100644 test/math/piLegendre.cpp create mode 100644 test/math/piLehmer.cpp create mode 100644 test/math/primeSieve.cpp create mode 100644 test/math/primitiveRoot.cpp create mode 100644 test/math/rho.cpp create mode 100644 test/math/shortModInv.cpp create mode 100644 test/math/simpson.cpp create mode 100644 test/math/sqrtModCipolla.cpp create mode 100644 test/math/transforms/andTransform.cpp create mode 100644 test/math/transforms/bitwiseTransforms.cpp create mode 100644 test/math/transforms/fft.cpp create mode 100644 test/math/transforms/fftMul.cpp create mode 100644 test/math/transforms/multiplyBitwise.cpp create mode 100644 test/math/transforms/multiplyFFT.cpp create mode 100644 test/math/transforms/multiplyNTT.cpp create mode 100644 test/math/transforms/ntt.cpp create mode 100644 test/math/transforms/orTransform.cpp create mode 100644 test/math/transforms/xorTransform.cpp create mode 100644 test/other/compiletime.cpp create mode 100644 test/other/divideAndConquer.cpp create mode 100644 test/other/fastIO.cpp create mode 100644 test/other/fastIO.in create mode 100644 test/other/josephus2.cpp create mode 100644 test/other/josephusK.cpp create mode 100644 test/other/knuth.cpp create mode 100644 test/other/sos.cpp create mode 100644 test/other/split.cpp create mode 100644 test/string/ahoCorasick.cpp create mode 100644 test/string/deBruijn.cpp create mode 100644 test/string/duval.cpp create mode 100644 test/string/kmp.cpp create mode 100644 test/string/longestCommonSubsequence.cpp create mode 100644 test/string/lyndon.cpp create mode 100644 test/string/manacher.cpp create mode 100644 test/string/rollingHash.cpp create mode 100644 test/string/rollingHashCf.cpp create mode 100644 test/string/suffixArray.cpp create mode 100644 test/string/suffixAutomaton.cpp create mode 100644 test/string/suffixTree.cpp create mode 100644 test/string/trie.cpp create mode 100644 test/string/z.cpp create mode 100644 test/template/template.cpp create mode 100755 test/test.sh create mode 100644 test/util.h (limited to 'test') diff --git a/test/datastructures/bitset.cpp b/test/datastructures/bitset.cpp new file mode 100644 index 0000000..2ba61a5 --- /dev/null +++ b/test/datastructures/bitset.cpp @@ -0,0 +1,6 @@ +#include "../util.h" + +int main() { + int x = 0; + #include +} diff --git a/test/datastructures/fenwickTree.cpp b/test/datastructures/fenwickTree.cpp new file mode 100644 index 0000000..c1ef6bf --- /dev/null +++ b/test/datastructures/fenwickTree.cpp @@ -0,0 +1,58 @@ +#include "../util.h" +#include + +//void update(int i, ll val) +//void init(int n) +//prefix_sum(int i) + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 100; tries++) { + int n = Random::integer(10, 100); + init(n); + vector naive(n); + for (int operations = 0; operations < 1000; operations++) { + { + int i = Random::integer(0, n); + ll x = Random::integer(-1000, 1000); + update(i, x); + naive[i] += x; + } + { + queries++; + int i = Random::integer(0, n); + ll got = prefix_sum(i); + ll expected = 0; + for (int j = 0; j <= i; j++) expected += naive[j]; + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + } + } + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 1'000'000; +void performance_test() { + timer t; + t.start(); + init(N); + t.stop(); + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + int i = Random::integer(0, N); + int j = Random::integer(0, N); + ll x = Random::integer(-1000, 1000); + + t.start(); + update(i, x); + hash ^= prefix_sum(j); + t.stop(); + } + if (t.time > 500) 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/datastructures/fenwickTree2.cpp b/test/datastructures/fenwickTree2.cpp new file mode 100644 index 0000000..aa99576 --- /dev/null +++ b/test/datastructures/fenwickTree2.cpp @@ -0,0 +1,60 @@ +#include "../util.h" +#include + +//void update(int l, int r, ll val) +//void init(int n) +//prefix_sum(int i) + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 100; tries++) { + int n = Random::integer(10, 100); + vector naive(n);// = Random::integers(n, -1000, 1000); + init(naive); + for (int operations = 0; operations < 1000; operations++) { + { + auto [i, j] = Random::pair(0, n); + ll x = Random::integer(-1000, 1000); + update(i, j, x); + for (int k = i; k < j; k++) naive[k] += x; + } + { + queries++; + int i = Random::integer(0, n); + ll got = prefix_sum(i); + ll expected = 0; + for (int j = 0; j <= i; j++) expected += naive[j]; + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + } + } + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 1'000'000; +void performance_test() { + timer t; + vector tmp = Random::integers(N, -1000, 1000); + t.start(); + init(tmp); + t.stop(); + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + int i = Random::integer(0, N); + int j = Random::integer(0, N); + int k = Random::integer(0, N); + ll x = Random::integer(-1000, 1000); + + t.start(); + update(i, j, x); + hash ^= prefix_sum(k); + 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/datastructures/lazyPropagation.cpp b/test/datastructures/lazyPropagation.cpp new file mode 100644 index 0000000..7002061 --- /dev/null +++ b/test/datastructures/lazyPropagation.cpp @@ -0,0 +1,61 @@ +#include "../util.h" +constexpr ll inf = LL::INF; +#include + +constexpr int N = 1000'000; + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 100; tries++) { + int n = Random::integer(10, 100); + vector naive = Random::integers(n, -1000, 1000); + SegTree tree(naive); + for (int operations = 0; operations < 1000; operations++) { + { + int l = Random::integer(0, n + 1); + int r = Random::integer(0, n + 1); + //if (l > r) swap(l, r); + ll x = Random::integer(-1000, 1000); + tree.update(l, r, x); + for (int j = l; j < r; j++) naive[j] = x; + } + { + queries++; + int l = Random::integer(0, n + 1); + int r = Random::integer(0, n + 1); + //if (l > r) swap(l, r); + ll got = tree.query(l, r); + ll expected = 0; + for (int j = l; j < r; j++) expected += naive[j]; + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + } + } + } + cerr << "tested random queries: " << queries << endl; +} + +void performance_test() { + timer t; + t.start(); + vector tmp(N); + SegTree tree(tmp); + t.stop(); + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + auto [l1, r1] = Random::pair(0, N + 1); + auto [l2, r2] = Random::pair(0, N + 1); + ll x1 = Random::integer(-1000, 1000); + + t.start(); + tree.update(l1, r1, x1); + hash ^= tree.query(l2, r2); + t.stop(); + } + if (t.time > 2000) 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/datastructures/pbds.cpp b/test/datastructures/pbds.cpp new file mode 100644 index 0000000..9080332 --- /dev/null +++ b/test/datastructures/pbds.cpp @@ -0,0 +1,11 @@ +#include "../util.h" +#include + +int main() { + Tree t1, t2; + swap(t1, t2); + hashSet s1, s2; + swap(s1, s2); + hashMap m1, m2; + swap(m1, m2); +} \ No newline at end of file diff --git a/test/datastructures/segmentTree.cpp b/test/datastructures/segmentTree.cpp new file mode 100644 index 0000000..fbac13e --- /dev/null +++ b/test/datastructures/segmentTree.cpp @@ -0,0 +1,122 @@ +#include "../util.h" +#include + +constexpr int N = 1'000'000; + +//void update(int i, ll val) +//ll query(int l, int r) + +//point update + range query +void stress_test1() { + ll queries = 0; + for (int tries = 0; tries < 100; tries++) { + int n = Random::integer(10, 100); + vector naive = Random::integers(n, -1000, 1000); + SegTree tree(naive); + for (int operations = 0; operations < 1000; operations++) { + { + int i = Random::integer(0, n); + ll x = Random::integer(-1000, 1000); + tree.update(i, x); + naive[i] = x;//point assignment + } + { + queries++; + int l = Random::integer(0, n + 1); + int r = Random::integer(0, n + 1); + //if (l > r) swap(l, r); + ll got = tree.query(l, r); + ll expected = 0; + for (int j = l; j < r; j++) expected += naive[j];//range sum + if (got != expected) cerr << " got: " << got << ", expected: " << expected << FAIL; + } + } + } + cerr << " tested random queries: " << queries << endl; +} + +//point update + range query +void performance_test1() { + timer t; + t.start(); + vector tmp(N); + SegTree tree(tmp); + t.stop(); + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + int i = Random::integer(0, N); + auto [l, r] = Random::pair(0, N + 1); + ll x = Random::integer(-1000, 1000); + + t.start(); + tree.update(i, x); + hash ^= tree.query(l, r); + t.stop(); + } + if (t.time > 1000) cerr << " too slow: " << t.time << FAIL; + cerr << " tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +//void modify(int l, int r, T val) +//ll query(int i) + +//range update + point query +void stress_test2() { + ll queries = 0; + for (int tries = 0; tries < 100; tries++) { + int n = Random::integer(10, 100); + vector naive(n); + SegTree tree(naive); + naive = Random::integers(n, -1000, 1000); + copy(all(naive), tree.tree.begin() + n); + for (int operations = 0; operations < 1000; operations++) { + { + int l = Random::integer(0, n + 1); + int r = Random::integer(0, n + 1); + //if (l > r) swap(l, r); + ll x = Random::integer(-1000, 1000); + tree.modify(l, r, x); + for (int j = l; j < r; j++) naive[j] += x;//range add + } + { + queries++; + int i = Random::integer(0, n); + ll got = tree.query(i); + ll expected = naive[i];//point query + if (got != expected) cerr << " got: " << got << ", expected: " << expected << FAIL; + } + } + } + cerr << " tested random queries: " << queries << endl; +} + +//range update + point query +void performance_test2() { + timer t; + t.start(); + vector tmp(N); + SegTree tree(tmp); + t.stop(); + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + int i = Random::integer(0, N); + auto [l, r] = Random::pair(0, N + 1); + ll x = Random::integer(-1000, 1000); + + t.start(); + tree.modify(l, r, x); + hash ^= tree.query(i); + t.stop(); + } + if (t.time > 1000) cerr << " too slow: " << t.time << FAIL; + cerr << " tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + cerr << "point update + range query:" << endl; + stress_test1(); + performance_test1(); + cerr << "range update + point query" << endl; + stress_test2(); + performance_test2(); +} diff --git a/test/datastructures/sparseTable.cpp b/test/datastructures/sparseTable.cpp new file mode 100644 index 0000000..7577694 --- /dev/null +++ b/test/datastructures/sparseTable.cpp @@ -0,0 +1,51 @@ +#include "../util.h" +constexpr ll INF = LL::INF; +#include + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 1000; tries++) { + int n = Random::integer(1, 100); + vector naive = Random::integers(n, -1000, 1000); + SparseTable st; + st.init(&naive); + for (int operations = 0; operations < 1000; operations++) { + queries++; + int l = Random::integer(0, n+1); + int r = Random::integer(0, n+1); + + ll got = st.queryIdempotent(l, r); + ll expected = r <= l ? -1 : l; + for (int j = l; j < r; j++) { + if (naive[j] < naive[expected]) expected = j; + } + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + } + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 1'500'000; +void performance_test() { + timer t; + vector naive = Random::integers(N, -1000, 1000); + t.start(); + SparseTable st; + st.init(&naive); + t.stop(); + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + auto [l, r] = Random::pair(0, N+1); + + t.start(); + hash += st.queryIdempotent(l, r); + t.stop(); + } + if (t.time > 500) 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/datastructures/sparseTableDisjoint.cpp b/test/datastructures/sparseTableDisjoint.cpp new file mode 100644 index 0000000..77bb005 --- /dev/null +++ b/test/datastructures/sparseTableDisjoint.cpp @@ -0,0 +1,48 @@ +#include "../util.h" +#include + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 1000; tries++) { + int n = Random::integer(1, 100); + vector naive = Random::integers(n, -1000, 1000); + DisjointST st; + st.init(&naive); + for (int operations = 0; operations < 1000; operations++) { + queries++; + int l = Random::integer(0, n+1); + int r = Random::integer(0, n+1); + + ll got = st.query(l, r); + ll expected = 0; + for (int j = l; j < r; j++) expected += naive[j]; + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + } + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 1'250'000; +void performance_test() { + timer t; + vector naive = Random::integers(N, -1000, 1000); + t.start(); + DisjointST st; + st.init(&naive); + t.stop(); + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + auto [l, r] = Random::pair(0, N+1); + + t.start(); + hash += st.query(l, r); + t.stop(); + } + if (t.time > 500) 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/datastructures/stlHashMap.cpp b/test/datastructures/stlHashMap.cpp new file mode 100644 index 0000000..77976fd --- /dev/null +++ b/test/datastructures/stlHashMap.cpp @@ -0,0 +1,4 @@ +#include "../util.h" +#include + +int main() {} \ No newline at end of file diff --git a/test/datastructures/stlTree.cpp b/test/datastructures/stlTree.cpp new file mode 100644 index 0000000..7bacbee --- /dev/null +++ b/test/datastructures/stlTree.cpp @@ -0,0 +1,2 @@ +#include "../util.h" +#include diff --git a/test/datastructures/unionFind.cpp b/test/datastructures/unionFind.cpp new file mode 100644 index 0000000..2afdc86 --- /dev/null +++ b/test/datastructures/unionFind.cpp @@ -0,0 +1,109 @@ +#include "../util.h" +struct UF { + UF(int n) {init(n);} + #include +}; + +struct Naive { + vector> adj; + vector seen; + int counter; + Naive(int n) : adj(n), seen(n), counter(0) {} + + template + void dfs(int x, F&& f) { + counter++; + vector todo = {x}; + seen[x] = counter; + while (!todo.empty()) { + x = todo.back(); + todo.pop_back(); + f(x); + for (ll y : adj[x]) { + if (seen[y] != counter) { + seen[y] = counter; + todo.push_back(y); + } + } + } + } + + int findSet(int a) { + int res = a; + dfs(a, [&](int x){res = min(res, x);}); + return res; + } + + void unionSets(int a, int b) { + adj[a].push_back(b); + adj[b].push_back(a); + } + + int size(int a) { + int res = 0; + dfs(a, [&](int /**/){res++;}); + return res; + } +}; + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 200; tries++) { + int n = Random::integer(1, 100); + UF uf(n); + Naive naive(n); + for (int i = 0; i < n; i++) { + for (int j = 0; j < 10; j++) { + int a = Random::integer(0, n); + int b = Random::integer(0, n); + uf.unionSets(a, b); + naive.unionSets(a, b); + } + UF tmp = uf; + for (int j = 0; j < n; j++) { + { + auto got = tmp.size(j); + auto expected = naive.size(j); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + } + { + int a = Random::integer(0, n); + int b = Random::integer(0, n); + bool got = tmp.findSet(a) == tmp.findSet(b); + bool expected = naive.findSet(a) == naive.findSet(b); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + } + } + queries += n; + } + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 2'000'000; +void performance_test() { + timer t; + t.start(); + UF uf(N); + t.stop(); + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + int i = Random::integer(0, N); + int j = Random::integer(0, N); + int k = Random::integer(0, N); + int l = Random::integer(0, N); + + t.start(); + uf.unionSets(i, j); + hash += uf.size(k); + hash += uf.size(l); + t.stop(); + } + if (t.time > 500) 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/datastructures/waveletTree.cpp b/test/datastructures/waveletTree.cpp new file mode 100644 index 0000000..d294835 --- /dev/null +++ b/test/datastructures/waveletTree.cpp @@ -0,0 +1,75 @@ +#include "../util.h" +#include + +constexpr int N = 1000'000; + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 100; tries++) { + int n = Random::integer(10, 100); + vector naive = Random::integers(n, -1000, 1000); + WaveletTree tree(naive); + for (int operations = 0; operations < 1000; operations++) { + { + queries++; + int l = Random::integer(0, n + 1); + int r = Random::integer(0, n + 1); + //if (l > r) swap(l, r); + int x = Random::integer(-1, n); + ll got = tree.kth(l, r, x); + ll expected = -1; + if (x >= 0 && l + x < r) { + vector tmp(naive.begin() + l, naive.begin() + r); + std::sort(all(tmp)); + expected = tmp[x]; + } + if (got != expected) { + cerr << "kth, got: " << got << ", expected: " << expected << FAIL; + } + } + { + queries++; + int l = Random::integer(0, n + 1); + int r = Random::integer(0, n + 1); + //if (l > r) swap(l, r); + ll x = Random::integer(-1000, 1000); + ll got = tree.countSmaller(l, r, x); + ll expected = 0; + for (int j = l; j < r; j++) { + if (naive[j] < x) expected++; + } + if (got != expected) { + cerr << "count, got: " << got << ", expected: " << expected << FAIL; + } + } + } + } + cerr << "tested random queries: " << queries << endl; +} + +void performance_test() { + timer t; + vector tmp = Random::integers(N, -1000, 1000); + t.start(); + WaveletTree tree(tmp); + t.stop(); + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + auto [l1, r1] = Random::pair(0, N + 1); + auto [l2, r2] = Random::pair(0, N + 1); + int x1 = Random::integer(l1, r1 + 1); + ll x2 = Random::integer(-1000, 1000); + + t.start(); + hash ^= tree.kth(l1, r1, x1); + hash ^= tree.countSmaller(l2, r2, x2); + t.stop(); + } + if (t.time > 2000) 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/geometry.h b/test/geometry.h new file mode 100644 index 0000000..7886fe2 --- /dev/null +++ b/test/geometry.h @@ -0,0 +1,140 @@ +#include + +namespace details { + // Liegt p auf der Strecke a-b? + bool pointInLineSegment(pt a, pt b, pt p) { + if (cross(a, b, p) != 0) return false; + auto dist = norm(a - b); + return norm(a - p) < dist && norm(b - p) < dist; + } + + // Test auf Streckenschnitt zwischen a-b und c-d. + // (nur intern) + bool lineSegmentIntersection(pt a, pt b, pt c, pt d) { + if (cross(a, b, c) == 0 && cross(a, b, d) == 0) { + return pointInLineSegment(a,b,c) || + pointInLineSegment(a,b,d) || + pointInLineSegment(c,d,a) || + pointInLineSegment(c,d,b); + } + return ccw(a, b, c) * ccw(a, b, d) < 0 && + ccw(c, d, a) * ccw(c, d, b) < 0; + } +} + +namespace Random { + vector partition(ll n, std::size_t k){//min = 0; + n += k; + vector res = Random::distinct(k-1, 1, n); + sort(all(res)); + res.emplace_back(n); + ll last = 0; + for (std::size_t i = 0; i < k; i++) { + res[i] -= last; + last += res[i]; + res[i]--; + } + return res; + } + + vector convex(int n, ll dim) { + binomial_distribution binomial(n - 2, 0.5); + + while (true) { + int left = 1 + binomial(Random::rng); + int down = 1 + binomial(Random::rng); + auto x = Random::partition(2 * dim - 2, left); + auto y = Random::partition(2 * dim - 2, down); + for (auto& z : x) z = -z; + for (auto& z : y) z = -z; + for (auto z : Random::partition(2 * dim - 2, n - left)) x.push_back(z); + for (auto z : Random::partition(2 * dim - 2, n - down)) y.push_back(z); + auto itX = std::partition(x.begin(), x.end(), [](ll z){return z == 0;}); + auto itY = std::partition(y.begin(), y.end(), [](ll z){return z != 0;}); + if (distance(x.begin(), itX) + distance(itY, y.end()) > n) continue; + shuffle(itX, x.end(), Random::rng); + if (itX != x.begin()) shuffle(y.begin(), itY, Random::rng); + + vector dirs(n); + for (size_t i = 0; i < dirs.size(); i++) { + dirs[i] = pt(x[i], y[i]); + } + sortAround(0, dirs); + + vector res = {{0, 0}}; + ll maxX = 0; + ll maxY = 0; + for (auto dir : dirs) { + pt tmp(real(res.back()) + real(dir), + imag(res.back()) + imag(dir)); + maxX = std::max(maxX, real(tmp)); + maxY = std::max(maxY, imag(tmp)); + res.emplace_back(tmp); + } + res.pop_back(); + for (auto& point : res) { + point = pt(real(point) + dim - 1 - maxX, + imag(point) + dim - 1 - maxY); + } + bool strict = true; + for (int i = 0; i < n; i++) strict &= cross(res[i], res[(i + 1) % n], res[(i + 2) % n]) != 0; + if (strict) return res; + } + } + + vector polygon(int n, ll dim) { + while (true) { + vector ps = points(n, -dim, dim); + bool coolinear = false; + for (int i = 0; i < n; i++) { + for (int j = 0; j < i; j++) { + for (int k = 0; k < j; k++) { + coolinear |= cross(ps[i], ps[j], ps[k]) == 0; + } + } + } + if (coolinear) continue; + + bool changed; + do { + changed = false; + for (int i = 0; i < n && !changed; i++) { + for (int j = i + 1; j < n && !changed; j++) { + if (details::lineSegmentIntersection(ps[i], ps[(i+1) % n], ps[j], ps[(j+1) % n])) { + reverse(ps.begin() + i + 1, ps.begin() + j + 1); + changed = true; + } + } + } + } while (changed); + return ps; + } + } + + pt integerPoint(ll range) { + return pt(integer(-range, range), + integer(-range, range)); + } + + vector integerPoints(std::size_t n, ll range) { + vector res(n); + for (auto& p : res) p = integerPoint(range); + return res; + } + + array line(ll range) { + pt a = integerPoint(range); + pt b = a; + while (b == a) b = integerPoint(range); + return {a, b}; + } + + array triangle(ll range) { + pt a = integerPoint(range); + pt b = a; + while (b == a) b = integerPoint(range); + pt c = a; + while (ccw(a, b, c) == 0) c = integerPoint(range); + return {a, b, c}; + } +} \ No newline at end of file diff --git a/test/geometry/antipodalPoints.cpp b/test/geometry/antipodalPoints.cpp new file mode 100644 index 0000000..d20dfb6 --- /dev/null +++ b/test/geometry/antipodalPoints.cpp @@ -0,0 +1,70 @@ +#include "../util.h" +constexpr ll EPS = 0; +#define double ll +#define polar polar +#include +#undef polar +#undef double +#include +#include "../geometry.h" + +vector> naive(vector ps) { + ll n = sz(ps); + auto test = [&](int i, int j){ + if (dot(ps[j] - ps[i], ps[i - 1] - ps[i]) <= 0) return false; + if (dot(ps[j] - ps[i], ps[i + 1] - ps[i]) <= 0) return false; + return true; + }; + ps.push_back(ps[0]); + ps.push_back(ps[1]); + vector> res; + for (ll i = 1; i <= n; i++) { + for (ll j = 1; j < i; j++) { + if (test(i, j) && test(j, i)) res.emplace_back(i % n, j % n); + } + } + return res; +} + +void stress_test(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer(3, 30); + auto ps = Random::convex(n, range); + + auto got = antipodalPoints(ps); + for (auto& [a, b] : got) if (a > b) swap(a, b); + sort(all(got)); + + auto expected = naive(ps); + for (auto& [a, b] : expected) if (a > b) swap(a, b); + + for (auto x : expected) { + auto it = lower_bound(all(got), x); + if (it == got.end() || *it != x) cerr << "error" << FAIL; + } + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 99'000; +void performance_test() { + timer t; + + auto ps = Random::convex(N, 1'000'000'000); + + t.start(); + auto got = antipodalPoints(ps); + t.stop(); + + hash_t hash = sz(got); + if (t.time > 50) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + stress_test(100); + stress_test(1'000'000'000); + performance_test(); +} diff --git a/test/geometry/circle.cpp b/test/geometry/circle.cpp new file mode 100644 index 0000000..3d3d27d --- /dev/null +++ b/test/geometry/circle.cpp @@ -0,0 +1,116 @@ +#include "../util.h" +constexpr double EPS = 1e-6; +#define ll double +double gcd(double x, double /**/) {return x;} //hacky +#include +#undef ll +#include + +// Entfernung von Punkt p zur Geraden durch a-b. 2d und 3d +double distToLine(pt a, pt b, pt p) { + return abs(cross(p - a, b - a)) / abs(b - a); +} + +pt randomIntegerPT(ll range) { + return pt(Random::integer(-range, range), Random::integer(-range, range)); +} + +ll sq(ll x) { + return x*x; +} + +int expectedCount(ll x1, ll y1, ll r1, ll x2, ll y2, ll r2) { + if (x1 == x2 && y1 == y2){ + return r1 == r2 ? -1 : 0; + } else { + ll d = sq(x1 - x2) + sq(y1 - y2); + + if (d > sq(r1 + r2) || d < sq(r1 - r2)) { + return 0; + } else if (d == sq(r1 + r2) || d == sq(r1 - r2)) { + return 1; + } else{ + return 2; + } + } +} + +void test_circleIntersection(ll range) { + int queries = 0; + for (int tries = 0; tries < 1'000'000; tries++) { + auto c1 = randomIntegerPT(range); + auto c2 = c1; + while (c1 == c2) c2 = randomIntegerPT(range); + double r1 = Random::integer(1, range); + double r2 = Random::integer(1, range); + + auto got = circleIntersection(c1, r1, c2, r2); + + if (sz(got) != expectedCount(real(c1), imag(c1), r1, real(c2), imag(c2), r2)) cerr << "error: wrong count" << FAIL; + + for (int i = 0; i < sz(got); i++) { + for (int j = 0; j < i; j++) { + if (abs(got[i] - got[j]) < 1e-6) cerr << "error: identical" << FAIL; + } + } + + for (auto p : got) { + if (float_error(abs(c1 - p), r1) > 1e-6) cerr << "error: 1" << FAIL; + if (float_error(abs(c2 - p), r2) > 1e-6) cerr << "error: 2" << FAIL; + } + queries += sz(got); + } + cerr << "tested circleIntersection: " << queries << endl; +} + +void test_circleRayIntersection(ll range) { + int queries = 0; + for (int tries = 0; tries < 1'000'000; tries++) { + auto c = randomIntegerPT(range); + double r = Random::integer(1, range); + + pt orig = randomIntegerPT(range); + pt dir = 0; + while (abs(dir) < 0.5) dir = randomIntegerPT(range); + + auto got = circleRayIntersection(c, r, orig, dir); + + double dist = distToLine(orig, orig + dir, c); + int lineIntersections = 0; + if (dist <= r) lineIntersections = 2; + if (abs(dist - r) < 1e-9) lineIntersections = 1; + + int expected = 0; + if (abs(orig - c) < r) expected = 1; //starts inside + if (abs(orig - c) > r) { //starts outside + if (dot(dir, c - orig) >= 0) expected = lineIntersections; + else expected = 0; + } + if (abs(abs(orig - c) - r) < 1e-9) { //starts on circle + if (dot(dir, c - orig) >= 0) expected = lineIntersections; + else expected = 1; + } + + if (sz(got) != expected) cerr << "error: wrong count" << FAIL; + + for (int i = 0; i < sz(got); i++) { + for (int j = 0; j < i; j++) { + if (abs(got[i] - got[j]) < 1e-6) cerr << "error: identical" << FAIL; + } + } + + for (auto p : got) { + if (float_error(abs(c - p), r) > 1e-6) cerr << "error: 1" << FAIL; + if (distToLine(orig, orig + dir, p) > 1e-6) cerr << "error: 2" << FAIL; + } + queries += sz(got); + } + cerr << "tested circleIntersection: " << queries << endl; +} + +int main() { + test_circleIntersection(10); + test_circleIntersection(100); + test_circleRayIntersection(10); + test_circleRayIntersection(100); +} diff --git a/test/geometry/closestPair.cpp b/test/geometry/closestPair.cpp new file mode 100644 index 0000000..5959b21 --- /dev/null +++ b/test/geometry/closestPair.cpp @@ -0,0 +1,69 @@ +#include "../util.h" +constexpr ll EPS = 0; +#define double ll +#define polar polar +#include +#undef polar +#undef double +constexpr ll INF = LL::INF; +ll sq(ll x) {return x*x;} +ll isqrt(ll x) {return (ll)sqrtl(x);} +#include + +//strict convex hull +ll naive(const vector& ps) { + ll opt = LL::INF; + for (ll i = 0; i < sz(ps); i++) { + for (ll j = 0; j < i; j++) { + opt = min(opt, norm(ps[i] - ps[j])); + } + } + return opt; +} + +void stress_test(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer(2, 100); + auto ps = Random::points(n, -range, range); + auto got = shortestDist(ps); + auto expected = naive(ps); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 1'000'000; +void performance_test() { + timer t; + hash_t hash = 0; + double maxTime = 0; + + vector ps; + for (int i = 0; i*i <= N; i++) { + for (int j = 0; j*j <= N; j++) { + ps.emplace_back(i, j); + } + } + t.start(); + hash = shortestDist(ps); + t.stop(); + maxTime = max(maxTime, t.time); + + ps = Random::points(N, -1'000'000'000, 1'000'000'000); + t.reset(); + t.start(); + hash += shortestDist(ps); + t.stop(); + maxTime = max(maxTime, t.time); + + if (maxTime > 500) cerr << "too slow: " << maxTime << FAIL; + cerr << "tested performance: " << maxTime << "ms (hash: " << hash << ")" << endl; +} + +int main() { + stress_test(100); + stress_test(1'000'000'000); + performance_test(); +} diff --git a/test/geometry/closestPair.double.cpp b/test/geometry/closestPair.double.cpp new file mode 100644 index 0000000..2f8a1ab --- /dev/null +++ b/test/geometry/closestPair.double.cpp @@ -0,0 +1,66 @@ +#include "../util.h" +constexpr double EPS = 1e-9; +#define ll double +double gcd(double x, double /**/) {return x;} //hacky +#include +constexpr ll INF = LL::INF; +#include +#undef ll + +//strict convex hull +double naive(const vector& ps) { + double opt = LL::INF; + for (ll i = 0; i < sz(ps); i++) { + for (ll j = 0; j < i; j++) { + opt = min(opt, norm(ps[i] - ps[j])); + } + } + return opt; +} + +void stress_test(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer(2, 100); + auto ps = Random::points(n, -range, range); + auto got = shortestDist(ps); + auto expected = naive(ps); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 1'000'000; +void performance_test() { + timer t; + hash_t hash = 0; + double maxTime = 0; + + vector ps; + for (int i = 0; i*i <= N; i++) { + for (int j = 0; j*j <= N; j++) { + ps.emplace_back(i, j); + } + } + t.start(); + hash = shortestDist(ps); + t.stop(); + maxTime = max(maxTime, t.time); + + ps = Random::points(N, -1'000'000'000, 1'000'000'000); + t.reset(); + t.start(); + hash += shortestDist(ps); + t.stop(); + maxTime = max(maxTime, t.time); + + if (maxTime > 500) cerr << "too slow: " << maxTime << FAIL; + cerr << "tested performance: " << maxTime << "ms (hash: " << hash << ")" << endl; +} + +int main() { + stress_test(100); + stress_test(1'000'000'000); + performance_test(); +} diff --git a/test/geometry/convexHull.cpp b/test/geometry/convexHull.cpp new file mode 100644 index 0000000..788a634 --- /dev/null +++ b/test/geometry/convexHull.cpp @@ -0,0 +1,79 @@ +#include "../util.h" +constexpr ll EPS = 0; +#define double ll +#define polar polar +#include +#undef polar +#undef double +#include + +//strict convex hull +ll isConvexHull(const vector& ps, const vector& hull) { + ll n = sz(hull) - 1; + if (n == 0) { + for (pt p : ps) if (p != hull[0]) return 1; + return 0; + } else { + if (hull[0] != hull[n]) return 2; + //hull has no duplicates + for (ll i = 0; i < n; i++) { + for (ll j = 0; j < i; j++) { + if (hull[i] == hull[j]) return 3; + } + } + //hull is subset + for (pt p : hull) { + bool isP = false; + for (pt c : ps) isP |= c == p; + if (!isP) return 4; + } + //hull contains all points + for (pt p : hull) { + ll mi = 1; + for (ll i = 0; i < n; i++) { + mi = min(mi, cross(hull[i], hull[i + 1], p)); + } + if (mi < 0) return 5; //outside + if (mi > 0) continue; + bool isCorner = 4; + for (pt c : hull) isCorner |= c == p; + if (!isCorner) return 6; + } + // hull is convex + if (n <= 2) return 0; + for (ll i = 0; i < n; i++) { + if (cross(hull[i], hull[i + 1], hull[(i + 2) % n]) <= 0) return 7; + } + return 0; + } +} + +void stress_test(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer(1, 100); + auto ps = Random::points(n, -range, range); + auto got = convexHull(ps); + if (isConvexHull(ps, got) > 0) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 2'000'000; +void performance_test() { + timer t; + auto ps = Random::points(N, -1'000'000'000, 1'000'000'000); + t.start(); + auto a = convexHull(ps); + t.stop(); + hash_t hash = sz(a); + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + stress_test(100); + stress_test(1'000'000'000); + performance_test(); +} diff --git a/test/geometry/delaunay.cpp b/test/geometry/delaunay.cpp new file mode 100644 index 0000000..7f8ec30 --- /dev/null +++ b/test/geometry/delaunay.cpp @@ -0,0 +1,144 @@ +#include "../util.h" +using pt = complex; +// Kreuzprodukt, 0, falls kollinear. +auto cross(pt a, pt b) {return imag(conj(a) * b);} +auto cross(pt p, pt a, pt b) {return cross(a - p, b - p);} +#pragma GCC diagnostic ignored "-Wunused-variable" +#include + +vector convexHull(vector pts){ + sort(all(pts), [](const pt& a, const pt& b){ + return real(a) == real(b) ? imag(a) < imag(b) + : real(a) < real(b); + }); + pts.erase(unique(all(pts)), pts.end()); + int k = 0; + vector h(2 * sz(pts)); + auto half = [&](auto begin, auto end, int t) { + for (auto it = begin; it != end; it++) { + while (k > t && cross(h[k-2], h[k-1], *it) < 0) k--;//allow collinear points! + h[k++] = *it; + }}; + half(all(pts), 1);// Untere Hülle. + half(next(pts.rbegin()), pts.rend(), k);// Obere Hülle. + h.resize(k); + return h; +} + +lll area(const vector& poly) { //poly[0] == poly.back() + lll res = 0; + for (int i = 0; i + 1 < sz(poly); i++) + res += cross(poly[i], poly[i + 1]); + return res; +} + +// Liegt p auf der Strecke a-b? +bool pointInLineSegment(pt a, pt b, pt p) { + if (cross(a, b, p) != 0) return false; + auto dist = norm(a - b); + return norm(a - p) < dist && norm(b - p) < dist; +} + +// Test auf Streckenschnitt zwischen a-b und c-d. +// (nur intern) +bool lineSegmentIntersection(pt a, pt b, pt c, pt d) { + if (cross(a, b, c) == 0 && cross(a, b, d) == 0) { + return pointInLineSegment(a,b,c) || + pointInLineSegment(a,b,d) || + pointInLineSegment(c,d,a) || + pointInLineSegment(c,d,b); + } + return cross(a, b, c) * cross(a, b, d) < 0 && + cross(c, d, a) * cross(c, d, b) < 0; +} + +// 1 => c links von a->b +// 0 => a, b und c kolliniear +// -1 => c rechts von a->b +int ccw(pt a, pt b, pt c) { + auto orien = cross(b - a, c - a); + return (orien > 0) - (orien < 0); +} + +bool inOutCirc(pt a, pt b, pt c, pt p) { + lll p2 = norm(p); + lll A = norm(a)-p2; + lll B = norm(b)-p2; + lll C = norm(c)-p2; + return ccw(a, b, c) * (cross(p, a, b)*C + cross(p, b, c)*A + cross(p, c, a)*B) > 0; +} + + +void stress_test(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer(3, 30); + auto ps = Random::points(n, -range, range); + bool skip = true; + for (int i = 2; i < n; i++) skip &= cross(ps[i-2], ps[i-1], ps[i]) == 0; + if (skip) continue; + for (int i = 0; i < n; i++) { + for (int j = 0; j < i; j++) { + skip |= ps[i] == ps[j]; + } + } + if (skip) continue; + + auto hull = convexHull(ps); + lll expectedArea = area(hull); + hull.pop_back(); + + auto got = delaunay(ps); + if (sz(got) % 3 != 0) cerr << "error: not triangles" << FAIL; + if (sz(got) / 3 + sz(hull) - 3 + 1 != 2 * sz(ps) - 4) cerr << "error: wrong number" << FAIL; + + //all triangles should be oriented ccw + lll gotArea = 0; + for (int i = 0; i < sz(got); i += 3) gotArea += cross(got[i], got[i+1], got[i+2]); + if (gotArea != expectedArea) cerr << "error: wrong area" << FAIL; + + for (int i = 0; i < sz(got); i++) { + int ii = i + 1; + if (i / 3 != ii / 3) ii -= 3; + for (int j = 0; j < i; j++) { + int jj = j + 1; + if (j / 3 != jj / 3) jj -= 3; + + if (got[i] == got[j] && got[ii] == got[jj]) cerr << "error: dublicate" << FAIL; + if (lineSegmentIntersection(got[i], got[ii], got[j], got[jj])) cerr << "error: intersection" << FAIL; + } + bool seen = false; + for (pt p : ps) seen |= p == got[i]; + if (!seen) cerr << "error: invalid point" << FAIL; + } + for (int i = 0; i < sz(got); i += 3) { + for (pt p : ps) { + if (p == got[i]) continue; + if (p == got[i+1]) continue; + if (p == got[i+2]) continue; + if (inOutCirc(got[i], got[i+1], got[i+2], p)) cerr << "error: not delaunay" << FAIL; + } + } + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 100'000; +void performance_test() { + timer t; + auto ps = Random::points(N, -1'000'000'000, 1'000'000'000); + t.start(); + auto got = delaunay(ps); + t.stop(); + hash_t hash = sz(got); + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + stress_test(10); + stress_test(10'000); + stress_test(1'000'000'000); + performance_test(); +} diff --git a/test/geometry/formulas.cpp b/test/geometry/formulas.cpp new file mode 100644 index 0000000..d63d431 --- /dev/null +++ b/test/geometry/formulas.cpp @@ -0,0 +1,127 @@ +#include "../util.h" +constexpr ll EPS = 0; +#define double ll +#define polar polar +#include +#undef polar +#undef double + +void test_dot(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto p = Random::point(-range, range); + auto q = Random::point(-range, range); + + ll expected = real(p) * real(q) + imag(p) * imag(q); + ll got = dot(p, q); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested dot: " << queries << endl; +} + +void test_norm(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto p = Random::point(-range, range); + + ll expected = real(p) * real(p) + imag(p) * imag(p); + ll got = norm(p); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested norm: " << queries << endl; +} + +void test_cross(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto p = Random::point(-range, range); + auto q = Random::point(-range, range); + + ll expected = real(p) * imag(q) - imag(p) * real(q); + ll got = cross(p, q); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested cross1: " << queries << endl; + + queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto a = Random::point(-range, range); + auto b = Random::point(-range, range); + auto c = Random::point(-range, range); + + ll expected = cross(b - a, c - a); + ll got = cross(a, b, c); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested cross2: " << queries << endl; +} + +void test_ccw(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto a = Random::point(-range, range); + auto b = Random::point(-range, range); + auto c = Random::point(-range, range); + + ll expected = cross(a, b, c); + if (expected < 0) expected = -1; + if (expected > 0) expected = 1; + ll got = ccw(a, b, c); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested ccw: " << queries << endl; +} + +void test_isCoplanar(ll range) {(void) range;}// cant check this... + +void test_uniqueAngle(ll range) { + auto lessPt = [](pt a, pt b){ + if (real(a) != real(b)) return real(a) < real(b); + return imag(a) < imag(b); + }; + map seen(lessPt); + + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + pt expected = Random::point(-sqrt(range), sqrt(range)); + ll g = abs(gcd(real(expected), imag(expected))); + if (g == 0) continue; + expected /= g; + + pt rot = Random::point(-sqrt(range), sqrt(range)); + if (norm(rot) == 0) continue; + + pt got = uniqueAngle(expected * rot, pt(Random::integer(1, sqrt(range)), 0) * rot); + auto it = seen.emplace(got, expected).first; + + if (it->second != expected) cerr << "error: inconsistent" << FAIL; + queries++; + } + cerr << "tested uniqueAngle: " << queries << " (" << sz(seen) << ")" << endl; +} + +int main() { + test_dot(100); + test_dot(1'000'000'000); + test_norm(100); + test_norm(1'000'000'000); + test_cross(100); + test_cross(1'000'000'000); + test_ccw(100); + test_ccw(1'000'000'000); + test_isCoplanar(100); + test_isCoplanar(1'000'000'000); + test_uniqueAngle(100); + test_uniqueAngle(10'000); + test_uniqueAngle(1'000'000'000); +} diff --git a/test/geometry/linesAndSegments.cpp b/test/geometry/linesAndSegments.cpp new file mode 100644 index 0000000..2943a67 --- /dev/null +++ b/test/geometry/linesAndSegments.cpp @@ -0,0 +1,240 @@ +#include "../util.h" +constexpr double EPS = 1e-9; +#define ll double +double gcd(double x, double /**/) {return x;} //hacky +#include +#undef ll +#include + +#include "../geometry.h" + +void stress_pointOnLine(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto [a, b] = Random::line(range); + pt p = Random::integerPoint(range); + + bool expected = ccw(a, b, p) == 0; + bool got = pointOnLine(a, b, p); + + if (got != expected) cerr << "error" << FAIL; + queries++; + } + cerr << "tested pointOnLine: " << queries << endl; +} + +void stress_lineIntersection(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto [a, b] = Random::line(range); + auto [c, d] = Random::line(range); + if (ccw(a, b, c) == 0 && ccw(a, b, d) == 0) continue; + + bool expected = ccw(0, a-b, c-d) == 0; + bool got = lineIntersection(a, b, c, d); + + if (got != expected) cerr << "error" << FAIL; + queries++; + } + cerr << "tested lineIntersection: " << queries << endl; +} + +void stress_lineIntersection2(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto [a, b] = Random::line(range); + auto [c, d] = Random::line(range); + if (ccw(0, a-b, c-d) == 0) continue; + + auto got = lineIntersection2(a, b, c, d); + + if (distToLine(a, b, got) > 1e-6) cerr << "error: 1" << FAIL; + if (distToLine(a, b, got) > 1e-6) cerr << "error: 2" << FAIL; + queries++; + } + cerr << "tested lineIntersection2: " << queries << endl; +} + +void stress_distToLine(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto [a, b] = Random::line(range); + pt p = Random::integerPoint(range); + + auto got = distToLine(a, b, p); + auto expected = abs(p - projectToLine(a, b, p)); + + if (float_error(got, expected) > 1e-6) cerr << "error" << FAIL; + + queries++; + } + cerr << "tested distToLine: " << queries << endl; +} + +void stress_projectToLine(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto [a, b] = Random::line(range); + pt p = Random::integerPoint(range); + + auto got = projectToLine(a, b, p); + + if (distToLine(a, b, got) > 1e-6) cerr << "error: 1" << FAIL; + if (dot((b-a)/abs(b-a), (got-p)/abs(got-p)) > 1e-6) cerr << "error: 2" << FAIL; + + queries++; + } + cerr << "tested projectToLine: " << queries << endl; +} + +void stress_sortLine(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + pt dir = 0; + while (norm(dir) == 0) dir = Random::integerPoint(range); + int n = Random::integer(1, 30); + vector ps = Random::integerPoints(n, range); + + sortLine(dir, ps); + + for (int i = 1; i < n; i++) { + if (dot(dir, ps[i-1]) > dot(dir, ps[i])) cerr << "error" << FAIL; + } + queries+=n; + } + cerr << "tested sortLine: " << queries << endl; +} + +void stress_pointOnSegment(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto [a, b] = Random::line(range); + pt p = Random::integerPoint(range); + + bool expected = pointOnLine(a, b, p) && abs(a-p) <= abs(a-b) && abs(b-p) <= abs(a-b); + bool got = pointOnSegment(a, b, p); + + if (got != expected) cerr << "error" << FAIL; + queries++; + } + cerr << "tested pointOnSegment: " << queries << endl; +} + +void stress_distToSegment(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto [a, b] = Random::line(range); + pt p = Random::integerPoint(range); + + double expected = min(abs(p-a), abs(p-b)); + if (dot(b-a,p-a) >= 0 && dot(a-b,p-b) >= 0) expected = min(expected, distToLine(a, b, p)); + double got = distToSegment(a, b, p); + + if (float_error(got, expected) > 1e-6) cerr << "error" << FAIL; + queries++; + } + cerr << "tested distToSegment: " << queries << endl; +} + +void stress_segmentIntersection(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto [a, b] = Random::line(range); + auto [c, d] = Random::line(range); + + bool expected; + if (ccw(a, b, c) == 0 && ccw(a, b, d) == 0) { + expected = pointOnSegment(a,b,c) || + pointOnSegment(a,b,d) || + pointOnSegment(c,d,a) || + pointOnSegment(c,d,b); + } else { + expected = ccw(a, b, c) * ccw(a, b, d) <= 0 && + ccw(c, d, a) * ccw(c, d, b) <= 0; + } + bool got = segmentIntersection(a, b, c, d); + + if (got != expected) cerr << "error" << FAIL; + queries++; + } + cerr << "tested segmentIntersection: " << queries << endl; +} + +void stress_segmentIntersection2(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto [a, b] = Random::line(range); + auto [c, d] = Random::line(range); + + auto got = segmentIntersection2(a, b, c, d); + auto tmp = segmentIntersection(a, b, c, d); + + if (!got.empty() != tmp) cerr << "error: 1" << FAIL; + for (pt p : got) { + if (distToSegment(a, b, p) > 1e-6) cerr << "error: 2" << FAIL; + if (distToSegment(a, b, p) > 1e-6) cerr << "error: 3" << FAIL; + } + if (tmp) { + double gotDist = abs(got.front() - got.back()); + double expectedDist = 0; + array tmp2 = {a, b, c, d}; + for (int i = 0; i < 4; i++) { + for (int j = 0; j < i; j++) { + if (!pointOnSegment(a, b, tmp2[i])) continue; + if (!pointOnSegment(c, d, tmp2[i])) continue; + if (!pointOnSegment(a, b, tmp2[j])) continue; + if (!pointOnSegment(c, d, tmp2[j])) continue; + expectedDist = max(expectedDist, abs(tmp2[i] - tmp2[j])); + } + } + if (float_error(gotDist, expectedDist) > 1e-6) cerr << "error: 4" << FAIL; + } + queries++; + } + cerr << "tested segmentIntersection2: " << queries << endl; +} + +void stress_distBetweenSegments(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto [a, b] = Random::line(range); + auto [c, d] = Random::line(range); + + double expected = 0; + if (!segmentIntersection(a, b, c, d)) { + expected = min({distToSegment(a, b, c), distToSegment(a, b, d), + distToSegment(c, d, a), distToSegment(c, d, b)}); + } + double got = distBetweenSegments(a, b, c, d); + + if (float_error(got, expected) > 1e-6) cerr << "error" << FAIL; + queries++; + } + cerr << "tested distBetweenSegments: " << queries << endl; +} + +int main() { + stress_pointOnLine(100); + stress_pointOnLine(10'000); + stress_pointOnLine(1'000'000'000); + stress_lineIntersection(100); + stress_lineIntersection(1'000'000'000); + stress_lineIntersection2(100); + stress_lineIntersection2(1'000'000); + stress_distToLine(100); + stress_distToLine(1'000'000'000); + stress_projectToLine(100); + stress_projectToLine(1'000'000); + stress_sortLine(100); + stress_sortLine(1'000'000'000); + stress_pointOnSegment(100); + stress_pointOnSegment(1'000'000'000); + stress_distToSegment(100); + stress_distToSegment(1'000'000'000); + stress_segmentIntersection(100); + stress_segmentIntersection(1'000'000'000); + stress_segmentIntersection2(100); + stress_segmentIntersection2(1'000'000'000); + stress_distBetweenSegments(100); + stress_distBetweenSegments(1'000'000'000); +} diff --git a/test/geometry/polygon.cpp b/test/geometry/polygon.cpp new file mode 100644 index 0000000..1dd46ca --- /dev/null +++ b/test/geometry/polygon.cpp @@ -0,0 +1,296 @@ +#include "../util.h" +constexpr ll EPS = 0; +constexpr double INF = LD::INF; +#define double ll +#define polar polar +#include +#undef polar +#undef double +double abs(pt p) { + return hypot(real(p), imag(p)); +} +// Liegt p auf der Strecke a-b? +bool pointOnLineSegment(pt a, pt b, pt p) { + if (cross(a, b, p) != 0) return false; + auto dist = norm(a - b); + return norm(a - p) <= dist && norm(b - p) <= dist; +} +// Entfernung von Punkt p zur Strecke a-b. +double distToSegment(pt a, pt b, pt p) { + if (a == b) return abs(p - a); + if (dot(p - a, b - a) <= 0) return abs(p - a); + if (dot(p - b, b - a) >= 0) return abs(p - b); + return abs(cross(p - a, b - a)) / abs(b - a); +} +#pragma GCC diagnostic ignored "-Wunused-variable" +#include +#include "../geometry.h" + +void test_area(ll range) { + int queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer(3, 30); + auto ps = Random::polygon(n, range); + ps.push_back(ps[0]); + + ll expected = 0; + for (int i = 0; i < n; i++) { + expected += cross(0, ps[i], ps[i+1]); + } + double got = area(ps) * 2; + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested area: " << queries << endl; +} + +bool ptLess(pt a, pt b) { + if (real(a) != real(b)) return real(a) < real(b); + return imag(a) < imag(b); +} + +void test_windingNumber(ll range) { + int queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer(3, 8); + auto ps = Random::polygon(n, range); + ps.push_back(ps[0]); + + for (int i = 0; i < 100; i++) { + auto p = Random::point(-range, range); + + ll expected = 0; + bool onBorder = false; + for (int j = 0; j < n; j++) { + int cur = details::lineSegmentIntersection(p, p + pt(1, 2'000'000'007), ps[j], ps[j+1]); + if (ptLess(ps[j], ps[j+1])) expected -= cur; + else expected += cur; + onBorder |= pointOnLineSegment(ps[j], ps[j+1], p); + } + if (onBorder) continue; + if (area(ps) < 0) expected = -expected; + + bool got = windingNumber(p, ps); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + } + queries += n; + } + cerr << "tested windingNumber: " << queries << endl; +} + +void test_inside(ll range) { + int queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer(3, 30); + auto ps = Random::polygon(n, range); + ps.push_back(ps[0]); + + for (int i = 0; i < 100; i++) { + auto p = Random::point(-range, range); + + ll count = 0; + bool onBorder = false; + for (int j = 0; j < n; j++) { + count += details::lineSegmentIntersection(p, p + pt(1, 2'000'000'007), ps[j], ps[j+1]); + onBorder |= pointOnLineSegment(ps[j], ps[j+1], p); + } + bool expected = (count % 2) && !onBorder; + bool got = inside(p, ps); + + if (got != expected) cerr << "error" << FAIL; + } + queries += n; + } + cerr << "tested inside: " << queries << endl; +} + +void test_insideConvex(ll range) { + int queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer(3, 30); + auto ps = Random::convex(n, range); + + for (int i = 0; i < 100; i++) { + auto p = Random::point(-range, range); + + bool expected = true; + for (int j = 0; j < n; j++) expected &= cross(p, ps[j], ps[(j+1) % n]) > 0; + + bool got = insideConvex(p, ps); + + if (got != expected) { + for (pt pp : ps) cerr << pp << " "; + cerr << endl; + cerr << p << endl; + } + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + } + queries += n; + } + cerr << "tested insideConvex: " << queries << endl; +} + +// convex hull without duplicates, h[0] != h.back() +// apply comments if border counts as inside +bool insideOrOnConvex(pt p, const vector& hull) { + int l = 0, r = sz(hull) - 1; + if (cross(hull[0], hull[r], p) > 0) return false; + while (l + 1 < r) { + int m = (l + r) / 2; + if (cross(hull[0], hull[m], p) >= 0) l = m; + else r = m; + } + return cross(hull[l], hull[r], p) >= 0; +} + +void test_minkowski(ll range) { + int queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer(3, 30); + auto A = Random::convex(n, range); + int m = Random::integer(3, 30); + auto B = Random::convex(n, range); + + auto got = minkowski(A, B); + bool convex = true; + for (int i = 0; i < sz(got); i++) convex &= cross(got[i], got[(i+1) % sz(got)], got[(i+2) % sz(got)]) >= 0; + if (!convex) cerr << "error: not convex" << FAIL; + + for (pt a : A) { + for (pt b : B) { + if (!insideOrOnConvex(a + b, got)) cerr << "error: not sum" << FAIL; + } + } + queries += n + m; + } + cerr << "tested minkowski: " << queries << endl; +} + +double naive_dist(const vector& ps, const vector& qs) { + //check if intersect + double res = LD::INF; + bool intersect = true; + for (int i = 0; i < sz(qs); i++) { + bool sep = true; + for (pt p : ps) { + res = min(res, distToSegment(qs[i], qs[(i+1) % sz(qs)], p)); + sep &= cross(qs[i], qs[(i+1) % sz(qs)], p) <= 0; + } + if (sep) intersect = false; + } + for (int i = 0; i < sz(ps); i++) { + bool sep = true; + for (pt q : qs) { + res = min(res, distToSegment(ps[i], ps[(i+1) % sz(ps)], q)); + sep &= cross(ps[i], ps[(i+1) % sz(ps)], q) <= 0; + } + if (sep) intersect = false; + } + if (intersect) return 0; + return res; +} + +void test_dist(ll range) { + int queries = 0; + int pos = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer(3, 10); + auto A = Random::convex(n, range / 3); + int m = Random::integer(3, 10); + auto B = Random::convex(n, range / 3); + + pt offset = Random::point(range / 3, 2 * range / 3); + for (pt& p : B) p += offset; + + auto got = dist(A, B); + auto expected = naive_dist(A, B); + + if (float_error(got, expected) > 1e-6) cerr << "got: " << got << ", expected: " << expected << FAIL; + if (got > 0) pos++; + + queries += n + m; + } + cerr << "tested dist: " << queries << " (" << pos << ")" << endl; +} + +void test_extremal(ll range) { + int queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer(3, 30); + auto ps = Random::convex(n, range); + ps.push_back(ps[0]); + + for (int i = 0; i < 100; i++) { + auto dir = Random::point(-range, range); + int tmp = extremal(ps, dir); + if (tmp < 0 || tmp >= n) cerr << "error: out of range" << FAIL; + + auto got = ps[tmp]; + bool extremal = true; + for (pt p : ps) extremal &= dot(dir, p) <= dot(dir, got); + + if (!extremal) cerr << "error: not extremal" << FAIL; + queries += n; + } + } + cerr << "tested extremal: " << queries << endl; +} + +void test_intersect(ll range) { + int queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer(3, 10); + auto ps = Random::convex(n, range); + ps.push_back(ps[0]); + + for (int i = 0; i < 100; i++) { + pt a = Random::point(-range, range); + pt b = a; + while (b == a) b = Random::point(-range, range); + + auto got = intersectLine(ps, a, b); + + vector expected; + for (int j = 0; j < n; j++) { + if (cross(ps[j], a, b) > 0 && cross(ps[j+1], a, b) < 0) expected.push_back(j); + if (cross(ps[j], a, b) < 0 && cross(ps[j+1], a, b) > 0) expected.push_back(j); + if (cross(ps[j], a, b) == 0) { + if (cross(ps[j+1], a, b) != 0 || + cross(ps[(j+n-1) % n], a, b) != 0) { + expected.push_back(j); + } + } + } + if (sz(expected) > 1 && expected[0] == expected[1]) expected.pop_back(); + + sort(all(got)); + sort(all(expected)); + + if (got != expected) cerr << "error" << FAIL; + + queries += n; + } + } + cerr << "tested intersect: " << queries << endl; +} + +int main() { + test_area(100); + test_area(1'000'000'000); + test_windingNumber(100); + test_windingNumber(1'000'000'000); + test_inside(100); + test_inside(1'000'000'000); + test_insideConvex(100); + test_insideConvex(1'000'000'000); + test_minkowski(100); + test_minkowski(500'000'000); + test_dist(100); + test_dist(1'000'000'000); + test_extremal(100); + test_extremal(1'000'000'000); + test_intersect(100); + test_intersect(1'000'000'000); +} diff --git a/test/geometry/segmentIntersection.cpp b/test/geometry/segmentIntersection.cpp new file mode 100644 index 0000000..9862be5 --- /dev/null +++ b/test/geometry/segmentIntersection.cpp @@ -0,0 +1,88 @@ +#include "../util.h" +constexpr ll EPS = 0; +#define double ll +#define polar polar +#include +#undef polar +#undef double + +// Liegt p auf der Strecke a-b? +bool pointOnLineSegment(pt a, pt b, pt p) { + if (cross(a, b, p) != 0) return false; + double dist = norm(a - b); + return norm(a - p) <= dist && norm(b - p) <= dist; +} + +// Test auf Streckenschnitt zwischen a-b und c-d. +bool lineSegmentIntersection(pt a, pt b, pt c, pt d) { + if (ccw(a, b, c) == 0 && ccw(a, b, d) == 0) + return pointOnLineSegment(a,b,c) || + pointOnLineSegment(a,b,d) || + pointOnLineSegment(c,d,a) || + pointOnLineSegment(c,d,b); + return ccw(a, b, c) * ccw(a, b, d) <= 0 && + ccw(c, d, a) * ccw(c, d, b) <= 0; +} + +#include + +vector randomSegs(int n, ll range) { + auto ps = Random::points(n, -range, range); + vector segs(n); + for (int i = 0; i < n; i++) { + pt b; + do { + b = Random::point(-pow(range, 0.8), pow(range, 0.8)); + } while(norm(b) == 0); + segs[i] = {ps[i], ps[i] + b, i}; + } + return segs; +} + +bool naive(vector& segs) { + for (ll i = 0; i < sz(segs); i++) { + for (ll j = 0; j < i; j++) { + if (lineSegmentIntersection(segs[i].a, segs[i].b, segs[j].a, segs[j].b)) return true; + } + } + return false; +} + +void stress_test(ll range) { + ll queries = 0; + ll intersection = 0; + ll notIntersection = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer(2, 100); + auto segs = randomSegs(n, range); + auto [a, b] = intersect(segs); + bool got = a >= 0; + if (got != (b >= 0)) cerr << "error: invalid ans" << FAIL; + auto expected = naive(segs); + if (got != expected) cerr << "error: intersection not found" << FAIL; + if (got && !lineSegmentIntersection(segs[a].a, segs[a].b, segs[b].a, segs[b].b)) cerr << "error: no intersection" << FAIL; + queries += n; + intersection += got; + notIntersection += !got; + } + cerr << "tested random queries: " << queries << "(" << intersection << ":" << notIntersection << ")" << endl; +} + +constexpr int N = 1'000'000; +void performance_test() { + timer t; + auto segs = randomSegs(N, 1'000'000'000); + + t.start(); + hash_t hash = intersect(segs).first; + t.stop(); + + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + stress_test(100); + stress_test(1'000'000'000); + performance_test(); +} diff --git a/test/geometry/sortAround.cpp b/test/geometry/sortAround.cpp new file mode 100644 index 0000000..a27edc8 --- /dev/null +++ b/test/geometry/sortAround.cpp @@ -0,0 +1,83 @@ +#include "../util.h" +constexpr ll EPS = 0; +#define double ll +#define polar polar +#include +#undef polar +#undef double +#include + +//expected order: +//1 8 7 +//2 . 6 +//3 4 5 +void test_tiny() { + vector expected = { + {-1, 1}, + {-1, 0}, + {-1,-1}, + { 0,-1}, + { 1,-1}, + { 1, 0}, + { 1, 1}, + { 0, 1}, + }; + auto got = expected; + for (int i = 0; i < 100'000; i++) { + shuffle(all(got), Random::rng); + sortAround(0, got); + if (got != expected) cerr << "error" << FAIL; + } + cerr << "tested tiny" << endl; +} + +void stress_test(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer(2, 100); + auto ps = Random::points(n, -range, range); + + auto contains = [&](pt p){ + for (pt pp : ps) if (pp == p) return true; + return false; + }; + + pt c; + do { + c = Random::point(-range, range); + } while (contains(c)); + + sortAround(c, ps); + + auto isLeft = [&](pt p){return real(p - c) < 0 || (real(p - c) == 0 && imag(p - c) < 0);}; + auto isCCW = [&](pt a, pt b){return cross(c, a, b) > 0;}; + if (!is_partitioned(all(ps), isLeft)) cerr << "error 1" << FAIL; + auto mid = partition_point(all(ps), isLeft); + if (!is_sorted(ps.begin(), mid, isCCW)) cerr << "error 2" << FAIL; + if (!is_sorted(mid, ps.end(), isCCW)) cerr << "error 3" << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 2'000'000; +void performance_test() { + timer t; + auto ps = Random::points(N, -1'000'000'000, 1'000'000'000); + + t.start(); + sortAround(0, ps); + t.stop(); + + hash_t hash = 0; + for (pt p : ps) hash += real(p) * imag(p); + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + test_tiny(); + stress_test(100); + stress_test(1'000'000'000); + performance_test(); +} diff --git a/test/geometry/triangle.cpp b/test/geometry/triangle.cpp new file mode 100644 index 0000000..dc620ee --- /dev/null +++ b/test/geometry/triangle.cpp @@ -0,0 +1,146 @@ +#include "../util.h" +constexpr double EPS = 1e-6; +#define ll double +double gcd(double x, double /**/) {return x;} //hacky +#include +#undef ll +ll sgn(double x) { + return (x > EPS) - (x < -EPS); +} +#include +#include "../geometry.h" + +// Entfernung von Punkt p zur Geraden durch a-b. 2d und 3d +double distToLine(pt a, pt b, pt p) { + return abs(cross(p - a, b - a)) / abs(b - a); +} + +void test_centroid(ll range) { + int queries = 0; + for (int tries = 0; tries < 1'000'000; tries++) { + auto [a, b, c] = Random::triangle(range); + + pt center = centroid(a, b, c); + + if (distToLine(2.0*a, c+b, 2.0*center) > 1e-6) cerr << "error: 1" << FAIL; + if (distToLine(2.0*b, c+a, 2.0*center) > 1e-6) cerr << "error: 2" << FAIL; + if (distToLine(2.0*c, a+b, 2.0*center) > 1e-6) cerr << "error: 3" << FAIL; + queries++; + } + cerr << "tested centroid: " << queries << endl; +} + +void test_area(ll range) { + int queries = 0; + for (int tries = 0; tries < 1'000'000; tries++) { + auto [a, b, c] = Random::triangle(range); + + auto gotA = 2*area(a, b, c); + auto gotB = 2*area(abs(a-b), abs(b-c), abs(c-a)); + auto expected = llround(gotA); + + if (float_error(gotA, expected) > 1e-6) cerr << "error: 1" << FAIL; + if (float_error(gotB, expected) > 1e-3) cerr << "error: 2" << FAIL; + queries++; + } + cerr << "tested area: " << queries << endl; +} + +void test_inCenter(ll range) { + int queries = 0; + for (int tries = 0; tries < 1'000'000; tries++) { + auto [a, b, c] = Random::triangle(range); + + pt center = inCenter(a, b, c); + + double da = distToLine(a, b, center); + double db = distToLine(b, c, center); + double dc = distToLine(c, a, center); + + double avg = (da + db + dc) / 3.0; + + if (float_error(da, avg) > 1e-6) cerr << "error: 1" << FAIL; + if (float_error(db, avg) > 1e-6) cerr << "error: 2" << FAIL; + if (float_error(dc, avg) > 1e-6) cerr << "error: 3" << FAIL; + queries++; + } + cerr << "tested inCenter: " << queries << endl; +} + +void test_circumCenter(ll range) { + int queries = 0; + for (int tries = 0; tries < 1'000'000; tries++) { + auto [a, b, c] = Random::triangle(range); + + pt center = circumCenter(a, b, c); + + double da = abs(center - a); + double db = abs(center - b); + double dc = abs(center - c); + + double avg = (da + db + dc) / 3.0; + + if (float_error(da, avg) > 1e-6) cerr << "error: 1" << FAIL; + if (float_error(db, avg) > 1e-6) cerr << "error: 2" << FAIL; + if (float_error(dc, avg) > 1e-6) cerr << "error: 3" << FAIL; + queries++; + } + cerr << "tested circumCenter: " << queries << endl; +} + +void test_insideOutCenter(ll range) { + int queries = 0; + for (int tries = 0; tries < 1'000'000; tries++) { + auto [a, b, c] = Random::triangle(range); + pt p = Random::integerPoint(range); + + pt center = circumCenter(a, b, c); + + double da = abs(center - a); + double db = abs(center - b); + double dc = abs(center - c); + double dp = abs(center - p); + + double avg = (da + db + dc) / 3.0; + + int expected = dp < avg ? 1 : -1; + if (float_error(dp, avg) < 1e-9) expected = 0; + + if (insideOutCenter(a, b, c, p) != expected) cerr << "error" << FAIL; + + queries++; + } + cerr << "tested insideOutCenter: " << queries << endl; +} + +void test_similar(ll range) { + int queries = 0; + for (int tries = 0; tries < 1'000'000; tries++) { + auto [a, b, c] = Random::triangle(sqrt(range)); + pt rot = Random::integerPoint(sqrt(range)); + pt add = Random::integerPoint(range); + + pt d = rot * a + add; + pt e = rot * b + add; + pt f = rot * c + add; + + if (!similar(a, b, c, d, e, f)) cerr << "error" << FAIL; + queries++; + } + cerr << "tested similar: " << queries << endl; +} + +int main() { + test_centroid(100); + test_centroid(1'000'000'000); + test_area(100); + test_area(1'000'000'000); + test_inCenter(100); + test_inCenter(1'000'000'000); + test_circumCenter(100); + test_circumCenter(1'000'000'000); + test_insideOutCenter(100); + test_insideOutCenter(1'000'000'000); + test_similar(100); + test_similar(1'000'000'000); +} diff --git a/test/graph/2sat.cpp b/test/graph/2sat.cpp new file mode 100644 index 0000000..fc3186e --- /dev/null +++ b/test/graph/2sat.cpp @@ -0,0 +1,133 @@ +#include "../util.h" +#include +#define static vector> adj; static // hacky... +#include +#undef static +#undef adj + +struct RandomClause { + int a, b; + int type; + RandomClause(int n) : + a(Random::integer(0, 2*n)), + b(Random::integer(0, 2*n)), + type(Random::integer(0, 8)) {} + + bool eval(vector& sol) const { + bool ba = sol[a]; + bool bb = sol[b]; + if (type == 0) return !ba || bb; + if (type == 1) return ba == bb; + if (type == 2) return ba || bb; + if (type == 3) return ba != bb; + if (type == 4) return ba && bb; + if (type == 5) return !(ba && bb); + + if (type == 6) return ba; + if (type == 7) return !ba; + return false; + } + + void add(sat2& sat) const { + int va = a; + int vb = b; + if (type == 0) sat.addImpl(va, vb); + if (type == 1) sat.addEquiv(va, vb); + if (type == 2) sat.addOr(va, vb); + if (type == 3) sat.addXor(va, vb); + if (type == 4) sat.addAnd(va, vb); + if (type == 5) sat.addNand(va, vb); + + if (type == 6) sat.addTrue(va); + if (type == 7) sat.addFalse(va); + } + + friend ostream& operator<<(ostream& os, const RandomClause& c) { + if (c.a & 1) os << "-"; + os << (c.a >> 1); + if (c.type == 0) os << "=>"; + if (c.type == 1) os << "=="; + if (c.type == 2) os << "or"; + if (c.type == 3) os << "xor"; + if (c.type == 4) os << "and"; + if (c.type == 5) os << "nand"; + + if (c.type == 6) return os; + if (c.type == 7) return os << "==F"; + + if (c.b & 1) os << "-"; + os << (c.b >> 1); + return os; + } +}; + +bool naive(int n, const vector& clauses) { + for (ll i = 0; i < (1ll << n); i++) { + vector tmp(2*n); + for (ll j = 0; j < n; j++) { + tmp[(2*j) + ((i >> j) & 1)] = 1; + } + bool ok = true; + for (auto& c : clauses) ok &= c.eval(tmp); + if (ok) return true; + } + return false; +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 200'000; tries++) { + int n = Random::integer(1, 12); + int m = Random::integer(0, 30); + + vector clauses; + for (int i = 0; i < m; i++) clauses.emplace_back(n); + + sat2 sat(n); + for (auto& c : clauses) c.add(sat); + adj = sat.adj; + + bool got = sat.solve(); + bool expected = naive(n, clauses); + + if (got) { + for (int i = 0; i < 2*n; i+=2) { + if (sat.sol[i] < 0) cerr << "error: invalid vars" << FAIL; + if (sat.sol[i+1] < 0) cerr << "error: invalid vars" << FAIL; + if (sat.sol[i] == sat.sol[i+1]) cerr << "error: inconsistent vars" << FAIL; + } + for (auto& c : clauses) { + if (!c.eval(sat.sol)) { + cerr << "error: inconsistent" << FAIL; + } + } + } + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 200'000; +constexpr int M = 500'000; +void performance_test() { + timer t; + vector clauses; + for (int i = 0; i < M; i++) clauses.emplace_back(N); + t.start(); + sat2 sat(N); + for (auto& c : clauses) c.add(sat); + t.stop(); + adj = sat.adj; + t.start(); + hash_t hash = sat.solve(); + t.stop(); + if (t.time > 500) 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/graph/LCA_sparse.cpp b/test/graph/LCA_sparse.cpp new file mode 100644 index 0000000..f6eb345 --- /dev/null +++ b/test/graph/LCA_sparse.cpp @@ -0,0 +1,63 @@ +#include "../util.h" +#include +#include +namespace expected { +#include +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 200'000; tries++) { + int n = Random::integer(2, 30); + Graph g(n); + g.tree(); + + vector> adj(n); + g.forEdges([&](int a, int b){ + adj[a].push_back(b); + adj[b].push_back(a); + }); + + LCA lca; + lca.init(adj, 0); + + expected::adj = adj; + expected::init(); + + for (int i = 0; i < n; i++) { + for (int j = 0; j <= i; j++) { + auto got = lca.getLCA(i, j); + auto expected = expected::get_lca(i, j); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + } + } + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 1'000'000; +void performance_test() { + timer t; + Graph g(N); + g.tree(); + vector> adj(N); + g.forEdges([&](int a, int b){ + adj[a].push_back(b); + adj[b].push_back(a); + }); + + hash_t hash = 0; + t.start(); + LCA lca; + lca.init(adj, 0); + for (int i = 1; i < N; i++) hash += lca.getLCA(i-1, i); + t.stop(); + if (t.time > 1000) 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/graph/TSP.cpp b/test/graph/TSP.cpp new file mode 100644 index 0000000..f9aab2e --- /dev/null +++ b/test/graph/TSP.cpp @@ -0,0 +1,67 @@ +#include "../util.h" +struct edge { + ll dist; + int to; +}; +constexpr ll INF = LL::INF; +#include + +vector naive() { + int n = sz(dist); + vector todo(n - 1); + iota(all(todo), 1); + vector res; + ll best = LL::INF; + do { + int last = 0; + ll cur = 0; + for (int x : todo) { + cur += dist[last][x]; + last = x; + } + cur += dist[last][0]; + if (cur < best) { + best = cur; + res = todo; + res.insert(res.begin(), 0); + res.push_back(0); + } + } while (next_permutation(all(todo))); + return res; +} + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 100'000; i++) { + int n = Random::integer(1, 9); + dist.assign(n, {}); + for (auto& v : dist) v = Random::integers(n, 0, 1000'000'000); + + auto expected = naive(); + auto got = TSP(); + + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 19; +void performance_test() { + timer t; + dist.assign(N, {}); + for (auto& v : dist) v = Random::integers(N, 0, 1000'000'000); + t.start(); + auto got = TSP(); + t.stop(); + + hash_t hash = 0; + for (int x : got) hash += x; + if (t.time > 1000) 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/graph/articulationPoints.bcc.cpp b/test/graph/articulationPoints.bcc.cpp new file mode 100644 index 0000000..15f5cf2 --- /dev/null +++ b/test/graph/articulationPoints.bcc.cpp @@ -0,0 +1,78 @@ +#include "../util.h" +struct edge { + ll from, to, id; +}; +#define Edge edge +#include +#undef Edge +#include + +vector> naiveBCC(int m) { + init(m); + + vector seen(sz(adj), -1); + int run = 0; + for (int i = 0; i < sz(adj); i++) { + for (auto e : adj[i]) { + run++; + seen[i] = run; + vector todo = {e.to}; + seen[e.to] = run; + while (!todo.empty()) { + int c = todo.back(); + todo.pop_back(); + for (auto ee : adj[c]) { + if (seen[ee.to] == run) continue; + seen[ee.to] = run; + todo.push_back(ee.to); + } + } + for (auto ee : adj[i]) { + if (seen[ee.to] == run) unionSets(ee.id, e.id); + } + } + } + vector> res(m); + for (int i = 0; i < m; i++) { + res[findSet(i)].push_back(i); + } + for (auto& v : res) sort(all(v)); + res.erase(remove_if(all(res), [](const vector& v){return sz(v) <= 1;}), res.end()); + sort(all(res)); + return res; +} + +void stress_test_bcc() { + ll queries = 0; + for (int tries = 0; tries < 200'000; tries++) { + int n = Random::integer(1, 30); + int m = Random::integer(0, max(1, min(300, n*(n-1) / 2 + 1))); + Graph g(n); + g.erdosRenyi(m); + + adj.assign(n, {}); + int nextId = 0; + g.forEdges([&](int a, int b){ + adj[a].push_back({a, b, nextId}); + adj[b].push_back({b, a, nextId}); + nextId++; + }); + + auto expected = naiveBCC(nextId); + find(); + vector> got(sz(bcc)); + for (int i = 0; i < sz(bcc); i++) { + for (auto e : bcc[i]) got[i].push_back(e.id); + sort(all(got[i])); + } + sort(all(got)); + + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +int main() { + stress_test_bcc(); +} diff --git a/test/graph/articulationPoints.bridges.cpp b/test/graph/articulationPoints.bridges.cpp new file mode 100644 index 0000000..a1b89d2 --- /dev/null +++ b/test/graph/articulationPoints.bridges.cpp @@ -0,0 +1,64 @@ +#include "../util.h" +struct edge { + ll from, to, id; +}; +#define Edge edge +#include +#undef Edge + +vector naiveBridges(const vector>& edges) { + vector res(sz(edges)); + + vector seen(sz(adj), -1); + for (int i = 0; i < sz(edges); i++) { + auto [a, b] = edges[i]; + vector todo = {a}; + seen[a] = i; + while (!todo.empty() && seen[b] != i) { + int c = todo.back(); + todo.pop_back(); + for (auto e : adj[c]) { + if (e.id == i) continue; + if (seen[e.to] == i) continue; + seen[e.to] = i; + todo.push_back(e.to); + } + } + res[i] = seen[b] != i; + } + return res; +} + +void stress_test_bridges() { + ll queries = 0; + for (int tries = 0; tries < 200'000; tries++) { + int n = Random::integer(1, 30); + int m = Random::integer(0, max(1, min(300, n*(n-1) / 2 + 1))); + Graph g(n); + g.erdosRenyi(m); + + adj.assign(n, {}); + vector> edges; + g.forEdges([&](int a, int b){ + adj[a].push_back({a, b, sz(edges)}); + adj[b].push_back({b, a, sz(edges)}); + edges.emplace_back(a, b); + }); + + auto expected = naiveBridges(edges); + find(); + vector got(sz(edges)); + for (auto e : bridges) { + if (got[e.id]) cerr << "error: duclicate" << FAIL; + got[e.id] = true; + } + + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +int main() { + stress_test_bridges(); +} diff --git a/test/graph/articulationPoints.cpp b/test/graph/articulationPoints.cpp new file mode 100644 index 0000000..2567a09 --- /dev/null +++ b/test/graph/articulationPoints.cpp @@ -0,0 +1,85 @@ +#include "../util.h" +struct edge { + ll from, to, id; +}; +#define Edge edge +#include +#undef Edge + +vector naiveArt() { + vector res(sz(adj)); + + vector seen(sz(adj), -1); + for (int i = 0; i < sz(adj); i++) { + if (adj[i].empty()) continue; + seen[i] = i; + vector todo = {adj[i][0].to}; + seen[todo[0]] = i; + while (!todo.empty()) { + int c = todo.back(); + todo.pop_back(); + for (auto e : adj[c]) { + if (seen[e.to] == i) continue; + seen[e.to] = i; + todo.push_back(e.to); + } + } + for (auto e : adj[i]) { + if (seen[e.to] != i) res[i] = true; + } + } + return res; +} + +void stress_test_art() { + ll queries = 0; + for (int tries = 0; tries < 200'000; tries++) { + int n = Random::integer(1, 30); + int m = Random::integer(0, max(1, min(300, n*(n-1) / 2 + 1))); + Graph g(n); + g.erdosRenyi(m); + + adj.assign(n, {}); + int nextId = 0; + g.forEdges([&](int a, int b){ + adj[a].push_back({a, b, nextId}); + adj[b].push_back({b, a, nextId}); + nextId++; + }); + + auto expected = naiveArt(); + find(); + vector got = isArt; + + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 500'000; +constexpr int M = 2'000'000; +void performance_test() { + timer t; + Graph g(N); + g.erdosRenyi(M); + adj.assign(N, {}); + int nextId = 0; + g.forEdges([&](int a, int b){ + adj[a].push_back({a, b, nextId}); + adj[b].push_back({b, a, nextId}); + nextId++; + }); + + t.start(); + find(); + t.stop(); + hash_t hash = sz(bridges) + sz(bcc); + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + stress_test_art(); + performance_test(); +} diff --git a/test/graph/bellmannFord.cpp b/test/graph/bellmannFord.cpp new file mode 100644 index 0000000..92f1fef --- /dev/null +++ b/test/graph/bellmannFord.cpp @@ -0,0 +1,70 @@ +#include "../util.h" +constexpr ll INF = LL::INF; +struct edge { + int from, to; + ll cost; +}; +#include +namespace floydWarshall { +#include +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer(2, 30); + int m = Random::integer(n-1, max(n, min(500, n*(n-1) / 2 + 1))); + vector potential = Random::integers(n, 0, 1'000'000'000'000ll); + + vector edges; + floydWarshall::dist.assign(n, vector(n, INF)); + for (int i = 0; i < n; i++) floydWarshall::dist[i][i] = 0; + + Graph g(n); + g.erdosRenyi(m); + g.forEdges([&](int a, int b){ + ll w = Random::integer(1, 100'000'000'000ll); + w = potential[b] + w - potential[a]; + edges.push_back({a, b, w}); + floydWarshall::dist[a][b] = min(floydWarshall::dist[a][b], w); + }); + + floydWarshall::floydWarshall(); + for (int i = 0; i < n; i++) { + auto got = bellmannFord(n, edges, i); + auto expected = floydWarshall::dist[i]; + + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 5'000; +constexpr int M = 20'000; +void performance_test() { + timer t; + Graph g(N); + g.erdosRenyi(M); + vector edges; + g.forEdges([&](int a, int b){ + ll w1 = Random::integer(1, 1'000'000'000'000ll); + ll w2 = Random::integer(1, 1'000'000'000'000ll); + edges.push_back({a, b, w1}); + edges.push_back({b, a, w2}); + }); + + t.start(); + auto got = bellmannFord(N, edges, 0); + t.stop(); + hash_t hash = 0; + for (auto x : got) hash += x; + if (t.time > 500) 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/graph/bitonicTSP.cpp b/test/graph/bitonicTSP.cpp new file mode 100644 index 0000000..7c448a2 --- /dev/null +++ b/test/graph/bitonicTSP.cpp @@ -0,0 +1,49 @@ +#include "../util.h" +namespace got { +#include +} +namespace expected { +#include +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 200'000; tries++) { + int n = Random::integer(1, 30); + + vector> dist(n); + for (auto& v : dist) v = Random::reals(n, 0, 1e18); + + got::dist = dist; + expected::dist = dist; + + auto got = got::bitonicTSP(); + auto expected = got::bitonicTSP(); + + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +//this is an easy graph... +constexpr int N = 5'000; +void performance_test() { + timer t; + got::dist = vector>(N); + for (auto& v : got::dist) v = Random::reals(N, 0, 1e18); + + + t.start(); + auto got = got::bitonicTSP(); + t.stop(); + hash_t hash = 0; + for (auto x : got) hash += x; + if (t.time > 500) 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/graph/bitonicTSPsimple.cpp b/test/graph/bitonicTSPsimple.cpp new file mode 100644 index 0000000..c79a0ef --- /dev/null +++ b/test/graph/bitonicTSPsimple.cpp @@ -0,0 +1,49 @@ +#include "../util.h" +namespace got { +#include +} +namespace expected { +#include +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 200'000; tries++) { + int n = Random::integer(1, 30); + + vector> dist(n); + for (auto& v : dist) v = Random::reals(n, 0, 1e18); + + got::dist = dist; + expected::dist = dist; + + auto got = got::bitonicTSP(); + auto expected = got::bitonicTSP(); + + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +//this is an easy graph... +constexpr int N = 2'000; +void performance_test() { + timer t; + got::dist = vector>(N); + for (auto& v : got::dist) v = Random::reals(N, 0, 1e18); + + + t.start(); + auto got = got::bitonicTSP(); + t.stop(); + hash_t hash = 0; + for (auto x : got) hash += x; + if (t.time > 500) 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/graph/blossom.cpp b/test/graph/blossom.cpp new file mode 100644 index 0000000..714b029 --- /dev/null +++ b/test/graph/blossom.cpp @@ -0,0 +1,76 @@ +#include "../util.h" +namespace tutte { +void gauss(int n, ll mod); +#include +#include +#include +} +#include + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 5'000; tries++) { + int n = Random::integer(1, 30); + int m = Random::integer(0, max(1, n*(n-1) / 2 + 1)); + + GM blossom(n); + srand(Random::rng()); + tutte::adj.assign(n, {}); + + Graph g(n); + g.erdosRenyi(m); + g.forEdges([&](int a, int b){ + tutte::adj[a].push_back(b); + tutte::adj[b].push_back(a); + + blossom.adj[a].push_back(b); + blossom.adj[b].push_back(a); + }); + + ll got = blossom.match(); + ll expected = tutte::max_matching(); + + vector seen(n); + ll got2 = 0; + for (int i = 0; i < n; i++) { + int j = blossom.pairs[i]; + if (j >= n) continue; + if (blossom.pairs[j] != i) cerr << "error: inconsitent" << FAIL; + if (j == i) cerr << "error: invalid" << FAIL; + if (j < i) continue; + if (seen[i] || seen[j]) cerr << "error: invalid" << FAIL; + seen[i] = seen[j] = true; + got2++; + } + + if (got != got2) cerr << "got: " << got << ", got2: " << got2 << FAIL; + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +//this is an easy graph... +constexpr int N = 100'000; +constexpr int M = 500'000; +void performance_test() { + timer t; + Graph g(N); + g.erdosRenyi(M); + GM blossom(N); + g.forEdges([&](int a, int b){ + blossom.adj[a].push_back(b); + blossom.adj[b].push_back(a); + }); + + t.start(); + hash_t hash = blossom.match(); + t.stop(); + if (t.time > 200) 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/graph/bronKerbosch.cpp b/test/graph/bronKerbosch.cpp new file mode 100644 index 0000000..1ccd493 --- /dev/null +++ b/test/graph/bronKerbosch.cpp @@ -0,0 +1,73 @@ +#include "../util.h" +#include + +vector naiveCliques; + +void naive(bits mask = {}, int l = 0) { + bool maximal = true; + for (ll i = 0; i < l; i++) { + if (mask[i]) continue; + if ((adj[i] & mask) == mask) maximal = false; + } + for (; l < sz(adj); l++) { + if ((adj[l] & mask) == mask) { + maximal = false; + mask[l] = 1; + naive(mask, l + 1); + mask[l] = 0; + } + } + if (maximal and mask.any()) naiveCliques.push_back(mask); +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 200'000; tries++) { + int n = Random::integer(2, 15); + int m = Random::integer(0, max(n, min(500, n*(n-1) / 2 + 1))); + + Graph g(n); + g.erdosRenyi(m); + adj.assign(n, {}); + g.forEdges([&](int a, int b){ + addEdge(a, b); + }); + + bronKerbosch(); + naiveCliques.clear(); + naive(); + + sort(all(cliques), [](bits a, bits b){return a.to_ullong() < b.to_ullong();}); + sort(all(naiveCliques), [](bits a, bits b){return a.to_ullong() < b.to_ullong();}); + + if (cliques != naiveCliques) cerr << "got: " << sz(cliques) << ", expected: " << sz(naiveCliques) << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 55; +constexpr int M = N*(N-1) / 2 - 2*N; +void performance_test() { + timer t; + + Graph g(N); + g.erdosRenyi(M); + adj.assign(N, {}); + g.forEdges([&](int a, int b){ + addEdge(a, b); + }); + + t.start(); + bronKerbosch(); + t.stop(); + + hash_t hash = sz(cliques); + if (t.time > 500) 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/graph/centroid.cpp b/test/graph/centroid.cpp new file mode 100644 index 0000000..41d9d0f --- /dev/null +++ b/test/graph/centroid.cpp @@ -0,0 +1,77 @@ +#include "../util.h" +vector> adj; +#include + +int subtreeSize(int c, int p) { + int res = 1; + for (int x : adj[c]) { + if (x == p) continue; + res += subtreeSize(x, c); + } + return res; +} + +vector naive() { + vector res; + for (int i = 0; i < sz(adj); i++) { + bool isCentroid = true; + for (int j : adj[i]) isCentroid &= 2*subtreeSize(j, i) <= sz(adj); + if (isCentroid) res.push_back(i); + } + return res; +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer(1, 50); + Graph g(n); + g.tree(); + + adj.assign(n, {}); + g.forEdges([&](int a, int b){ + adj[a].push_back(b); + adj[b].push_back(a); + }); + + auto expected = naive(); + sort(all(expected)); + + for (int i = 0; i < n; i++) { + auto [a, b] = find_centroid(i); + vector got; + if (a >= 0) got.push_back(a); + if (b >= 0) got.push_back(b); + sort(all(got)); + + if (got != expected) cerr << "error" << FAIL; + } + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 2'000'000; +void performance_test() { + timer t; + Graph g(N); + g.tree(); + + adj.assign(N, {}); + g.forEdges([&](int a, int b){ + adj[a].push_back(b); + adj[b].push_back(a); + }); + + t.start(); + auto [gotA, gotB] = find_centroid(); + t.stop(); + hash_t hash = gotA + gotB; + if (t.time > 500) 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/graph/cycleCounting.cpp b/test/graph/cycleCounting.cpp new file mode 100644 index 0000000..8e53aec --- /dev/null +++ b/test/graph/cycleCounting.cpp @@ -0,0 +1,79 @@ +#include "../util.h" +#include +#include + +int naive(const vector>& edges, int n) { + int res = 0; + for (int i = 1; i < (1ll << sz(edges)); i++) { + vector deg(n); + init(n); + int cycles = 0; + for (int j = 0; j < sz(edges); j++) { + if (((i >> j) & 1) != 0) { + auto [a, b] = edges[j]; + deg[a]++; + deg[b]++; + if (findSet(a) != findSet(b)) { + unionSets(a, b); + } else { + cycles++; + } + } + } + bool ok = cycles == 1; + for (auto d : deg) ok &= d == 0 || d == 2; + if (ok) res++; + } + return res; +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 50'000; tries++) { + int n = Random::integer(1, 8); + int m = Random::integer(0, min(15, n*(n-1) / 2 + 1)); + + Graph g(n); + g.erdosRenyi(m); + vector> edges; + cycles cyc(n); + g.forEdges([&](int a, int b){ + edges.emplace_back(a, b); + cyc.addEdge(a, b); + }); + + int expected = naive(edges, n); + int got = cyc.count(); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 100; +constexpr int M = 20; +void performance_test() { + timer t; + + Graph g(N); + g.tree(); + g.erdosRenyi(M); + cycles cyc(N); + g.forEdges([&](int a, int b){ + cyc.addEdge(a, b); + }); + + t.start(); + hash_t hash = cyc.count(); + cerr << sz(cyc.base) << endl; + t.stop(); + + if (t.time > 1000) 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/graph/dijkstra.cpp b/test/graph/dijkstra.cpp new file mode 100644 index 0000000..c0cfb7e --- /dev/null +++ b/test/graph/dijkstra.cpp @@ -0,0 +1,64 @@ +#include "../util.h" +constexpr ll INF = LL::INF; +#include +struct edge { + int from, to; + ll cost; +}; +#include + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer(2, 30); + int m = Random::integer(n-1, max(n, min(500, n*(n-1) / 2 + 1))); + + vector> adj(n); + vector edges; + + Graph g(n); + g.erdosRenyi(m); + g.forEdges([&](int a, int b){ + ll w = Random::integer(1, 1'000'000'000'000ll); + adj[a].push_back({w, b}); + edges.push_back({a, b, w}); + }); + + for (int i = 0; i < n; i++) { + auto got = dijkstra(adj, i); + auto expected = bellmannFord(n, edges, i); + + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 500'000; +constexpr int M = 3'000'000; +void performance_test() { + timer t; + Graph g(N); + g.erdosRenyi(M); + vector> adj(N); + g.forEdges([&](int a, int b){ + ll w1 = Random::integer(1, 1'000'000'000'000ll); + ll w2 = Random::integer(1, 1'000'000'000'000ll); + adj[a].push_back({w1, b}); + adj[b].push_back({w2, a}); + }); + + t.start(); + auto got = dijkstra(adj, 0); + t.stop(); + hash_t hash = 0; + for (auto x : got) hash += x; + if (t.time > 1000) 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/graph/dinicScaling.cpp b/test/graph/dinicScaling.cpp new file mode 100644 index 0000000..967d6b1 --- /dev/null +++ b/test/graph/dinicScaling.cpp @@ -0,0 +1,61 @@ +#include "../util.h" +namespace dinic { +#include +} + +namespace pushRelabel { +#include +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 20'000; tries++) { + int n = Random::integer(2, 30); + int m = Random::integer(n-1, max(n, min(500, n*(n-1) / 2 + 1))); + + dinic::adj.assign(n, {}); + pushRelabel::adj.assign(n, {}); + + Graph g(n); + g.erdosRenyi(m); + g.forEdges([](int a, int b){ + ll w = Random::integer(1, 1'000'000'000'000ll); + dinic::addEdge(a, b, w); + pushRelabel::addEdge(a, b, w); + }); + + ll got = dinic::maxFlow(0, n - 1); + ll expected = pushRelabel::maxFlow(0, n - 1); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 50000; +constexpr int M = 200000; +void performance_test() { + using namespace dinic; + timer t; + Graph g(N); + g.erdosRenyi(M); + adj.assign(N, {}); + g.forEdges([](int a, int b){ + ll w1 = Random::integer(1, 1'000'000'000'000ll); + ll w2 = Random::integer(1, 1'000'000'000'000ll); + addEdge(a, b, w1); + addEdge(b, a, w2); + }); + + t.start(); + hash_t hash = maxFlow(0, N - 1); + t.stop(); + if (t.time > 2000) 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/graph/euler.cpp b/test/graph/euler.cpp new file mode 100644 index 0000000..6666040 --- /dev/null +++ b/test/graph/euler.cpp @@ -0,0 +1,87 @@ +#include "../util.h" +struct Euler { + Euler(int n) : idx(n), validIdx(n) {} +#include +}; + +Euler eulerGraph(int n, int m) { + Euler res(n); + + Graph g(n); + g.tree(); + g.forEdges([&](int a, int b) { + res.addEdge(a, b); + }); + + for (int i = n-1; i < m; i++) { + int a = Random::integer(0, n); + int b = Random::integer(0, n); + res.addEdge(a, b); + } + int last = -1; + for (int i = 0; i < n; i++) { + if (sz(res.idx[i]) % 2 != 0) { + if (last >= 0) { + res.addEdge(last, i); + last = -1; + } else { + last = i; + } + } + } + if (last >= 0) cerr << "FAIL" << FAIL; + + return res; +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 200'000; tries++) { + int n = Random::integer(1, 30); + int m = Random::integer(n-1, 200); + + auto g = eulerGraph(n, m); + + vector> expected(n); + for (int i = 0; i < n; i++) { + for (int j : g.idx[i]) { + expected[i].push_back(g.to[j]); + } + sort(all(expected[i])); + } + + g.euler(0); + vector> got(n); + if (g.cycle.front() != g.cycle.back()) cerr << "error: not cyclic" << FAIL; + for (int i = 1; i < sz(g.cycle); i++) { + int a = g.cycle[i-1]; + int b = g.cycle[i]; + got[a].push_back(b); + got[b].push_back(a); + } + for (auto& v : got) sort(all(v)); + + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 100'000; +constexpr int M = 1'000'000; +void performance_test() { + timer t; + auto g = eulerGraph(N, M); + t.start(); + g.euler(0); + t.stop(); + hash_t hash = 0; + for (int x : g.cycle) hash += x; + if (t.time > 500) 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/graph/floydWarshall.cpp b/test/graph/floydWarshall.cpp new file mode 100644 index 0000000..a93a9ea --- /dev/null +++ b/test/graph/floydWarshall.cpp @@ -0,0 +1,90 @@ +#include "../util.h" +constexpr ll INF = LL::INF; +struct edge { + int from, to; + ll cost; +}; +#include +namespace floydWarshall { +#include +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer(2, 30); + int m = Random::integer(n-1, max(n, min(500, n*(n-1) / 2 + 1))); + vector potential = Random::integers(n, 0, 1'000'000'000'000ll); + + vector edges; + floydWarshall::dist.assign(n, vector(n, INF)); + for (int i = 0; i < n; i++) floydWarshall::dist[i][i] = 0; + + Graph g(n); + g.erdosRenyi(m); + g.forEdges([&](int a, int b){ + ll w = Random::integer(1, 100'000'000'000ll); + w = potential[b] + w - potential[a]; + edges.push_back({a, b, w}); + floydWarshall::dist[a][b] = min(floydWarshall::dist[a][b], w); + }); + + vector> orig = floydWarshall::dist; + + floydWarshall::floydWarshall(); + for (int i = 0; i < n; i++) { + for (int j = 0; j < 10; j++) { + int k = Random::integer(0, n); + auto path = floydWarshall::getPath(i, k); + if (path.empty() != (floydWarshall::dist[i][k] == INF)) cerr << "error: reconstruction" << FAIL; + if (path.empty()) continue; + if (path.front() != i) cerr << "error: start" << FAIL; + if (path.back() != k) cerr << "error: end" << FAIL; + for (int l = 1; l < sz(path); l++) { + if (floydWarshall::dist[i][path[l-1]] + + orig[path[l-1]][path[l]] + + floydWarshall::dist[path[l]][k] != + floydWarshall::dist[i][k]) cerr << "error: edge" << FAIL; + } + } + } + + for (int i = 0; i < n; i++) { + auto got = floydWarshall::dist[i]; + auto expected = bellmannFord(n, edges, i); + + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 500; +constexpr int M = 20'000; +void performance_test() { + timer t; + Graph g(N); + g.erdosRenyi(M); + floydWarshall::dist.assign(N, vector(N, INF)); + for (int i = 0; i < N; i++) floydWarshall::dist[i][i] = 0; + g.forEdges([&](int a, int b){ + ll w1 = Random::integer(1, 1'000'000'000'000ll); + ll w2 = Random::integer(1, 1'000'000'000'000ll); + floydWarshall::dist[a][b] = w1; + floydWarshall::dist[b][a] = w2; + }); + + t.start(); + floydWarshall::floydWarshall(); + t.stop(); + hash_t hash = 0; + for (auto x : floydWarshall::dist[42]) hash += x; + if (t.time > 500) 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/graph/havelHakimi.cpp b/test/graph/havelHakimi.cpp new file mode 100644 index 0000000..71476ec --- /dev/null +++ b/test/graph/havelHakimi.cpp @@ -0,0 +1,65 @@ +#include "../util.h" +#include + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 200'000; tries++) { + int n = Random::integer(1, 30); + int m = Random::integer(0, n*(n-1) / 2 + 1); + Graph g(n); + g.erdosRenyi(m); + + vector expected(n); + for (int i = 0; i < n; i++) expected[i] = g.deg(i); + + auto res = havelHakimi(expected); + if (sz(res) != n) cerr << "error: wrong number of nodes" << FAIL; + vector> rev(n); + vector got(n); + for (int i = 0; i < n; i++) { + got[i] = sz(res[i]); + for (int j : res[i]) { + if (j < 0 || j >= n) cerr << "error: invalid edge" << FAIL; + rev[j].push_back(i); + } + } + + for (int i = 0; i < n; i++) { + sort(all(res[i])); + sort(all(rev[i])); + if (res[i] != rev[i]) cerr << "error: graph is directed" << FAIL; + for (int j : res[i]) if (j == i) cerr << "error: graph has loop" << FAIL; + for (int j = 1; j < sz(res[i]); j++) { + if (res[i][j] == res[i][j-1]) cerr << "error: multiedge" << FAIL; + } + } + + if (expected != got) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 200'000; +constexpr int M = 1'000'000; +void performance_test() { + timer t; + Graph g(N); + g.erdosRenyi(M); + + vector expected(N); + for (int i = 0; i < N; i++) expected[i] = g.deg(i); + + t.start(); + auto res = havelHakimi(expected); + t.stop(); + hash_t hash = 0; + for (auto& v : res) hash += sz(v); + if (t.time > 500) 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/graph/hopcroftKarp.cpp b/test/graph/hopcroftKarp.cpp new file mode 100644 index 0000000..05599dd --- /dev/null +++ b/test/graph/hopcroftKarp.cpp @@ -0,0 +1,74 @@ +#include "../util.h" +namespace kuhn { +#include +} +namespace hk { +#include +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 50'000; tries++) { + int n = Random::integer(1, 30); + int m = Random::integer(0, max(1, n*(n-1) / 2 + 1)); + + kuhn::adj.assign(2*n, {}); + hk::adj.assign(2*n, {}); + + Graph g(n); + g.erdosRenyi(m); + g.forEdges([&](int a, int b){ + kuhn::adj[a].push_back(n+b); + kuhn::adj[b+n].push_back(a); + + hk::adj[a].push_back(n+b); + hk::adj[b+n].push_back(a); + }); + + ll got = hk::hopcroft_karp(n); + ll expected = kuhn::kuhn(n); + + vector seen(2*n); + ll got2 = 0; + for (int i = 0; i < n; i++) { + int j = hk::pairs[i]; + if (j < 0) continue; + if (hk::pairs[j] != i) cerr << "error: inconsitent" << FAIL; + if (j == i) cerr << "error: invalid" << FAIL; + if (j < i) continue; + if (seen[i] || seen[j]) cerr << "error: invalid" << FAIL; + seen[i] = seen[j] = true; + got2++; + } + + if (got != got2) cerr << "got: " << got << ", got2: " << got2 << FAIL; + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +//this is an easy graph... +constexpr int N = 100'000; +constexpr int M = 500'000; +void performance_test() { + timer t; + Graph g(N); + g.erdosRenyi(M); + hk::adj.assign(2*N, {}); + g.forEdges([&](int a, int b){ + hk::adj[a].push_back(N+b); + hk::adj[b+N].push_back(a); + }); + + t.start(); + hash_t hash = hk::hopcroft_karp(N); + t.stop(); + if (t.time > 300) 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/graph/kruskal.cpp b/test/graph/kruskal.cpp new file mode 100644 index 0000000..f6245b9 --- /dev/null +++ b/test/graph/kruskal.cpp @@ -0,0 +1,91 @@ +#include "../util.h" +#include + +struct edge { + int from, to; + ll cost; + bool operator<(const edge& o) const { + return cost > o.cost; + } +}; +ll kruskal(vector& edges, int n) { + init(n); + #define Edge edge + #include + #undef Edge + return cost; +} + +ll prim(vector& edges, int n) { + vector>> adj(n); + for (auto [a, b, d] : edges) { + adj[a].emplace_back(d, b); + adj[b].emplace_back(d, a); + } + priority_queue> todo; + vector seen(n); + ll res = 0; + for (ll i = 0; i < n; i++) { + if (seen[i]) continue; + todo.push({0, i}); + while (!todo.empty()) { + auto [d, c] = todo.top(); + todo.pop(); + if (seen[c]) continue; + seen[c] = true; + res += d; + for (auto e : adj[c]) { + todo.push(e); + } + } + } + return res; +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer(2, 30); + int m = Random::integer(0, max(n, min(500, n*(n-1) / 2 + 1))); + + + Graph g(n); + g.erdosRenyi(m); + vector edges; + g.forEdges([&](int a, int b){ + ll w = Random::integer(-1'000'000'000ll, 1'000'000'000ll); + edges.push_back({a, b, w}); + }); + + ll got = kruskal(edges, n); + ll expected = prim(edges, n); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 500'000; +constexpr int M = 3'000'000; +void performance_test() { + timer t; + Graph g(N); + g.erdosRenyi(M); + vector edges; + g.forEdges([&](int a, int b){ + ll w = Random::integer(-1'000'000'000ll, 1'000'000'000ll); + edges.push_back({a, b, w}); + }); + + t.start(); + hash_t hash = kruskal(edges, N); + t.stop(); + if (t.time > 1000) 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/graph/matching.cpp b/test/graph/matching.cpp new file mode 100644 index 0000000..b8fbc6c --- /dev/null +++ b/test/graph/matching.cpp @@ -0,0 +1,62 @@ +#include "../util.h" +namespace tutte { +void gauss(int n, ll mod); +#include +#include +#include +} +#include + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 5'000; tries++) { + int n = Random::integer(1, 30); + int m = Random::integer(0, max(1, n*(n-1) / 2 + 1)); + + GM blossom(n); + srand(Random::rng()); + tutte::adj.assign(n, {}); + + Graph g(n); + g.erdosRenyi(m); + g.forEdges([&](int a, int b){ + tutte::adj[a].push_back(b); + tutte::adj[b].push_back(a); + + blossom.adj[a].push_back(b); + blossom.adj[b].push_back(a); + }); + + ll got = tutte::max_matching(); + ll expected = blossom.match(); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 125; +constexpr int M = 5'000; +void performance_test() { + timer t; + Graph g(N); + g.erdosRenyi(M); + srand(Random::rng()); + tutte::adj.assign(N, {}); + g.forEdges([&](int a, int b){ + tutte::adj[a].push_back(b); + tutte::adj[b].push_back(a); + }); + + t.start(); + hash_t hash = tutte::max_matching(); + t.stop(); + if (t.time > 500) 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/graph/maxCarBiMatch.cpp b/test/graph/maxCarBiMatch.cpp new file mode 100644 index 0000000..6d7fad0 --- /dev/null +++ b/test/graph/maxCarBiMatch.cpp @@ -0,0 +1,74 @@ +#include "../util.h" +namespace kuhn { +#include +} +namespace hk { +#include +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 50'000; tries++) { + int n = Random::integer(1, 30); + int m = Random::integer(0, max(1, n*(n-1) / 2 + 1)); + + kuhn::adj.assign(2*n, {}); + hk::adj.assign(2*n, {}); + + Graph g(n); + g.erdosRenyi(m); + g.forEdges([&](int a, int b){ + kuhn::adj[a].push_back(n+b); + kuhn::adj[b+n].push_back(a); + + hk::adj[a].push_back(n+b); + hk::adj[b+n].push_back(a); + }); + + ll got = kuhn::kuhn(n); + ll expected = hk::hopcroft_karp(n); + + vector seen(2*n); + ll got2 = 0; + for (int i = 0; i < n; i++) { + int j = kuhn::pairs[i]; + if (j < 0) continue; + if (kuhn::pairs[j] != i) cerr << "error: inconsitent" << FAIL; + if (j == i) cerr << "error: invalid" << FAIL; + if (j < i) continue; + if (seen[i] || seen[j]) cerr << "error: invalid" << FAIL; + seen[i] = seen[j] = true; + got2++; + } + + if (got != got2) cerr << "got: " << got << ", got2: " << got2 << FAIL; + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +//this is an easy graph... +constexpr int N = 10'000; +constexpr int M = 100'000; +void performance_test() { + timer t; + Graph g(N); + g.erdosRenyi(M); + kuhn::adj.assign(2*N, {}); + g.forEdges([&](int a, int b){ + kuhn::adj[a].push_back(N+b); + kuhn::adj[b+N].push_back(a); + }); + + t.start(); + hash_t hash = kuhn::kuhn(N); + t.stop(); + if (t.time > 200) 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/graph/maxWeightBipartiteMatching.cpp b/test/graph/maxWeightBipartiteMatching.cpp new file mode 100644 index 0000000..d245405 --- /dev/null +++ b/test/graph/maxWeightBipartiteMatching.cpp @@ -0,0 +1,59 @@ +#include "../util.h" +#pragma GCC diagnostic ignored "-Wshadow" +namespace matching { + constexpr int N_LEFT = 1000; + constexpr int N_RIGHT = 1000; + constexpr double INF = LD::INF; + #include +} +namespace mcmf { + #include +} + + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 20'000; tries++) { + auto [l, r] = Random::pair(1, 30); + mcmf::MinCostFlow mcmf(l+r+2, 0, 1); + + for (int i = 0; i < l; i++) mcmf.addEdge(0, 2 + i, 1, 0); + for (int i = 0; i < r; i++) mcmf.addEdge(2 + l + i, 1, 1, 0); + for (int i = 0; i < l; i++) { + for (int j = 0; j < r; j++) { + matching::costs[i][j] = Random::integer(-100, 100); + mcmf.addEdge(2 + i, 2 + l + j, 1, -matching::costs[i][j]); + } + } + + double got = matching::match(l, r); + mcmf.mincostflow(); + ll expected = -mcmf.mincost; + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += l + r; + } + cerr << "tested random queries: " << queries << endl; +} + +void performance_test() { + using namespace matching; + timer t; + + for (int i = 0; i < N_LEFT; i++) { + for (int j = 0; j < N_RIGHT; j++) { + costs[i][j] = Random::integer(-100, 100); + } + } + + t.start(); + hash_t hash = match(N_LEFT, N_RIGHT); + t.stop(); + if (t.time > 1000) 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/graph/minCostMaxFlow.cpp b/test/graph/minCostMaxFlow.cpp new file mode 100644 index 0000000..8c92aa7 --- /dev/null +++ b/test/graph/minCostMaxFlow.cpp @@ -0,0 +1,68 @@ +#include "../util.h" +#pragma GCC diagnostic ignored "-Wshadow" +namespace matching { + constexpr int N_LEFT = 1000; + constexpr int N_RIGHT = 1000; + constexpr double INF = LD::INF; + #include +} +namespace mcmf { + #include +} + + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 20'000; tries++) { + auto [l, r] = Random::pair(1, 30); + mcmf::MinCostFlow mcmf(l+r+2, 0, 1); + + for (int i = 0; i < l; i++) mcmf.addEdge(0, 2 + i, 1, 0); + for (int i = 0; i < r; i++) mcmf.addEdge(2 + l + i, 1, 1, 0); + for (int i = 0; i < l; i++) { + for (int j = 0; j < r; j++) { + matching::costs[i][j] = Random::integer(-100, 100); + mcmf.addEdge(2 + i, 2 + l + j, 1, -matching::costs[i][j]); + } + } + + mcmf.mincostflow(); + ll got = -mcmf.mincost; + double expected = matching::match(l, r); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += l + r; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 1'000; +constexpr int M = 10'000; +void performance_test() { + using namespace mcmf; + timer t; + + Graph g(N); + g.erdosRenyi(M); + MinCostFlow mcmf(N, 0, 1); + vector potential = Random::integers(N, 0, 1'000'000ll); + g.forEdges([&](int a, int b){ + ll c = Random::integer(1, 1000'000); + ll cost = Random::integer(0, 1000'000); + mcmf.addEdge(a, b, c, potential[b] + cost - potential[a]); + mcmf.addEdge(b, a, c, potential[a] + cost - potential[b]); + }); + + t.start(); + mcmf.mincostflow(); + t.stop(); + + hash_t hash = mcmf.mincost; + if (t.time > 500) 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/graph/pushRelabel.cpp b/test/graph/pushRelabel.cpp new file mode 100644 index 0000000..ac3b079 --- /dev/null +++ b/test/graph/pushRelabel.cpp @@ -0,0 +1,61 @@ +#include "../util.h" +namespace dinic { +#include +} + +namespace pushRelabel { +#include +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 20'000; tries++) { + int n = Random::integer(2, 30); + int m = Random::integer(n-1, max(n, min(500, n*(n-1) / 2 + 1))); + + dinic::adj.assign(n, {}); + pushRelabel::adj.assign(n, {}); + + Graph g(n); + g.erdosRenyi(m); + g.forEdges([](int a, int b){ + ll w = Random::integer(1, 1'000'000'000'000ll); + dinic::addEdge(a, b, w); + pushRelabel::addEdge(a, b, w); + }); + + ll got = pushRelabel::maxFlow(0, n - 1); + ll expected = dinic::maxFlow(0, n - 1); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 50000; +constexpr int M = 200000; +void performance_test() { + using namespace pushRelabel; + timer t; + Graph g(N); + g.erdosRenyi(M); + adj.assign(N, {}); + g.forEdges([](int a, int b){ + ll w1 = Random::integer(1, 1'000'000'000'000ll); + ll w2 = Random::integer(1, 1'000'000'000'000ll); + addEdge(a, b, w1); + addEdge(b, a, w2); + }); + + t.start(); + hash_t hash = maxFlow(0, N - 1); + t.stop(); + if (t.time > 300) 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/graph/scc.cpp b/test/graph/scc.cpp new file mode 100644 index 0000000..123050f --- /dev/null +++ b/test/graph/scc.cpp @@ -0,0 +1,92 @@ +#include "../util.h" +#include +#include + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer(1, 30); + int m = Random::integer(0, max(1, min(100, n*(n-1) / 2 + 1))); + Graph g(n); + g.erdosRenyi(m); + + adj.assign(n, {}); + g.forEdges([](int a, int b){ + adj[a].push_back(b); + }); + scc(); + + vector tmp(n); + for (int i = 0; i < sz(sccs); i++) { + for (int x : sccs[i]) { + if (tmp[x]) cerr << "error: duclicate" << FAIL; + if (idx[x] != i) cerr << "error: inconsistent" << FAIL; + tmp[x] = true; + } + } + for (int i = 0; i < n; i++) { + if (!tmp[i]) cerr << "error: missing" << FAIL; + } + + init(n); + vector seen(n); + int tmpCounter = 0; + auto reach = [&](int a, int b) { + tmpCounter++; + seen[a] = tmpCounter; + vector todo = {a}; + while (seen[b] != tmpCounter && !todo.empty()) { + a = todo.back(); + todo.pop_back(); + g.forOut(a, [&](int /**/, int x){ + if (seen[x] != tmpCounter) { + seen[x] = tmpCounter; + todo.push_back(x); + } + }); + } + return seen[b] == tmpCounter; + }; + for (int a = 0; a < n; a++) { + for (int b = 0; b < a; b++) { + if (findSet(a) == findSet(b)) continue; + if (reach(a, b) && reach(b, a)) unionSets(a, b); + } + } + + for (int a = 0; a < n; a++) { + for (int b = 0; b <= a; b++) { + bool got = idx[a] == idx[b]; + bool expected = findSet(a) == findSet(b); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + } + } + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 500'000; +constexpr int M = 2'000'000; +void performance_test() { + timer t; + Graph g(N); + g.erdosRenyi(M); + adj.assign(N, {}); + g.forEdges([](int a, int b){ + adj[a].push_back(b); + }); + + t.start(); + scc(); + t.stop(); + hash_t hash = 0; + for (int x : idx) hash += x; + if (t.time > 500) 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/graph/stoerWagner.cpp b/test/graph/stoerWagner.cpp new file mode 100644 index 0000000..2003f09 --- /dev/null +++ b/test/graph/stoerWagner.cpp @@ -0,0 +1,81 @@ +#include "../util.h" +constexpr ll INF = LL::INF; + +namespace stoerWagner { +#include + void addEdge(int u, int v, ll c) { + adj[u].push_back({u, v, c}); + adj[v].push_back({v, u, c}); + } +} + +namespace pushRelabel { +#include + ll minCut() { + ll res = INF; + for (int i = 0; i < sz(adj); i++) { + for (int j = 0; j < i; j++) { + if (i == j) continue; + res = min(res, maxFlow(i, j)); + for (auto& v : adj) { + for (auto& e : v) { + e.f = 0; + } + } + } + } + return res; + } +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 5'000; tries++) { + int n = Random::integer(2, 30); + int m = Random::integer(n-1, max(n, min(500, n*(n-1) / 2 + 1))); + + stoerWagner::adj.assign(n, {}); + pushRelabel::adj.assign(n, {}); + + Graph g(n); + g.erdosRenyi(m); + g.forEdges([](int a, int b){ + ll w = Random::integer(1, 1'000'000'000'000ll); + stoerWagner::addEdge(a, b, w); + pushRelabel::addEdge(a, b, w); + pushRelabel::addEdge(b, a, w); + }); + + ll got = stoerWagner::stoer_wagner(); + ll expected = pushRelabel::minCut(); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 200; +constexpr int M = 10000; +void performance_test() { + using namespace stoerWagner; + timer t; + Graph g(N); + g.erdosRenyi(M); + adj.assign(N, {}); + g.forEdges([](int a, int b){ + ll w = Random::integer(1, 1'000'000'000'000ll); + addEdge(a, b, w); + }); + + t.start(); + hash_t hash = stoer_wagner(); + t.stop(); + if (t.time > 2000) 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/graph/treeIsomorphism.cpp b/test/graph/treeIsomorphism.cpp new file mode 100644 index 0000000..97f4df4 --- /dev/null +++ b/test/graph/treeIsomorphism.cpp @@ -0,0 +1,126 @@ +#include "../util.h" +struct tree { + tree(int n) : adj(n) {} + #include + #include + + pair treeLabel() { + auto [a, b] = find_centroid(0); + if (a >= 0) a = treeLabel(a); + if (b >= 0) b = treeLabel(b); + if (a > b) swap(a, b); + return {a, b}; + } +}; + +void stress_test_eq() { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer(1, 50); + Graph g(n); + g.tree(); + + tree t(n); + + g.forEdges([&](int a, int b){ + t.adj[a].push_back(b); + t.adj[b].push_back(a); + }); + auto [gotA, gotB] = t.treeLabel(); + + g.permutate(); + t.adj.assign(n, {}); + g.forEdges([&](int a, int b){ + t.adj[a].push_back(b); + t.adj[b].push_back(a); + }); + auto [expectedA, expectedB] = t.treeLabel(); + + if (gotA != expectedA) cerr << "got: " << gotA << ", expected: " << expectedA << FAIL; + if (gotB != expectedB) cerr << "got: " << gotB << ", expected: " << expectedB << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +void test_tiny() { + vector expected = {1,1,1,1,2,3,6,11,23}; //#A000055 + for (int i = 1; i < sz(expected); i++) { + set> got; + tree t(i); + + int labeled = 1; + for (int j = 3; j < i; j++) labeled *= i; + for (int j = 0; j < 10 * labeled; j++) { + Graph g(i); + g.tree(); + + t.adj.assign(i, {}); + g.forEdges([&](int a, int b){ + t.adj[a].push_back(b); + t.adj[b].push_back(a); + }); + + got.insert(t.treeLabel()); + } + if (sz(got) != expected[i]) cerr << i << ", got: " << sz(got) << ", expected: " << expected[i] << FAIL; + } + cerr << "tested tiny: " << sz(expected) << endl; +} + +void stress_test_neq() { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer(20, 50); + Graph g(n); + g.tree(); + + tree t(n); + + g.forEdges([&](int a, int b){ + t.adj[a].push_back(b); + t.adj[b].push_back(a); + }); + auto [gotA, gotB] = t.treeLabel(); + + g.clear().tree(); + t.adj.assign(n, {}); + g.forEdges([&](int a, int b){ + t.adj[a].push_back(b); + t.adj[b].push_back(a); + }); + auto [expectedA, expectedB] = t.treeLabel(); + + if (gotA == expectedA && gotA >= 0) cerr << "error: " << n << ", " << tries << FAIL; + if (gotB == expectedB) cerr << "error: " << n << ", " << tries << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 500'000; +void performance_test() { + timer t; + Graph g(N); + g.tree(); + + tree tt(N); + g.forEdges([&](int a, int b){ + tt.adj[a].push_back(b); + tt.adj[b].push_back(a); + }); + + t.start(); + auto [gotA, gotB] = tt.treeLabel(); + t.stop(); + hash_t hash = gotA + gotB; + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + stress_test_eq(); + test_tiny(); + stress_test_neq(); + performance_test(); +} diff --git a/test/math/berlekampMassey.cpp b/test/math/berlekampMassey.cpp new file mode 100644 index 0000000..58fd143 --- /dev/null +++ b/test/math/berlekampMassey.cpp @@ -0,0 +1,68 @@ +#include "../util.h" +#include +#include + +struct RandomRecurence { + vector f, c, cache; + RandomRecurence(int n) : f(Random::integers(n, 0, mod)), c(Random::integers(n, 0, mod)), cache(f) {} + RandomRecurence(const vector& f_, const vector& c_) : c(c_), cache(f_) { + if (cache.size() < c.size()) cerr << "wrong size" << FAIL; + cache.resize(c.size()); + f = cache; + } + + ll operator()(ll k){ + while (sz(cache) <= k) { + ll cur = 0; + for (ll i = 0; i < sz(c); i++) { + cur += (c[i] * cache[sz(cache) - i - 1]) % mod; + } + cur %= mod; + cache.push_back(cur); + } + return cache[k]; + } +}; + +void stress_test() { + int queries = 0; + for (int i = 0; i < 50'000; i++) { + int n = Random::integer(1, 10); + RandomRecurence expected(n); + + ll k = Random::integer(2*n, 100); + vector s(k); + for (ll j = 0; j < k; j++) s[j] = expected(j); + + auto res = BerlekampMassey(s); + RandomRecurence got(s, res); + + for (ll j = 0; j < 3*k; j++) { + if (got(j) != expected(j)) cerr << "got: " << got(j) << ", expected: " << expected(j) << FAIL; + } + + queries += k; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 5'000; +void performance_test() { + timer t; + RandomRecurence f(N); + f(2*N); + t.start(); + auto res = BerlekampMassey(f.cache); + t.stop(); + hash_t hash = 0; + for (ll x : res) hash += x; + if (t.time > 500) 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/math/bigint.cpp b/test/math/bigint.cpp new file mode 100644 index 0000000..3fc4ac1 --- /dev/null +++ b/test/math/bigint.cpp @@ -0,0 +1,122 @@ +#include "../util.h" +#include + +template +struct modInt { + ll value = 0; + modInt() {} + modInt(const bigint& x) { + stringstream a; + a << x; + string b = a.str(); + for (ll i = b[0] == '-' ? 1 : 0; i < sz(b); i++) { + value *= 10; + value += b[i] - '0'; + value %= MOD; + } + if (b[0] == '-') value = (MOD - value) % MOD; + } + + modInt(ll x) : value(((x % MOD) + MOD) % MOD) {} + + modInt operator+(modInt o) const {return value + o.value;} + modInt operator-(modInt o) const {return value - o.value;} + modInt operator*(modInt o) const {return value * o.value;} + + modInt& operator+=(modInt o) {return *this = *this + o;} + modInt& operator-=(modInt o) {return *this = *this - o;} + modInt& operator*=(modInt o) {return *this = *this * o;} + + ll& operator*() {return value;} + bool operator==(const modInt& o) const {return value == o.value;} + bool operator!=(const modInt& o) const {return value != o.value;} +}; + +constexpr ll MOD = 1'394'633'899; +constexpr ll POOL = 8; + +void stress_test() { + int queries = 0; + for (int tries = 0; tries < 1000; tries++) { + vector> expectedPool(POOL); + vector gotPool(POOL); + for (int i = 0; i < POOL; i++) { + ll x = Random::integer(-1'000'000'000'000'000'000ll, 1'000'000'000'000'000'000ll); + expectedPool[i] = x; + gotPool[i] = x; + if (expectedPool[i] != modInt(gotPool[i])) cerr << "error: 0" << FAIL; + } + for (int i = 0; i < 200; i++) { + int a = Random::integer(0, POOL); + int b = Random::integer(0, POOL); + int o = Random::integer(0, 3); + + if (Random::integer(0, 2) == 0) {//x= + auto tmpExpected = expectedPool[a]; + auto tmpGot = gotPool[a]; + + if (o == 0) { + tmpExpected += expectedPool[b]; + tmpGot += gotPool[b]; + } + if (o == 1) { + tmpExpected -= expectedPool[b]; + tmpGot -= gotPool[b]; + } + if (o == 2) { + tmpExpected -= expectedPool[b]; + tmpGot -= gotPool[b]; + } + + if (tmpExpected != modInt(tmpGot)) { + cerr << gotPool[a]; + if (o == 0) cerr << "+"; + if (o == 1) cerr << "-"; + if (o == 2) cerr << "*"; + cerr << gotPool[b] << "=" << tmpGot << endl; + cerr << "error: 1" << FAIL; + } + + expectedPool[b] = tmpExpected; + gotPool[b] = tmpGot; + } else {//x + int c = Random::integer(0, POOL); + + modInt tmpExpected; + bigint tmpGot; + + if (o == 0) { + tmpExpected = expectedPool[a] + expectedPool[b]; + tmpGot = gotPool[a] + gotPool[b]; + } + if (o == 1) { + tmpExpected = expectedPool[a] - expectedPool[b]; + tmpGot = gotPool[a] - gotPool[b]; + } + if (o == 2) { + tmpExpected = expectedPool[a] * expectedPool[b]; + tmpGot = gotPool[a] * gotPool[b]; + } + + if (tmpExpected != modInt(tmpGot)) { + cerr << gotPool[a]; + if (o == 0) cerr << "+"; + if (o == 1) cerr << "-"; + if (o == 2) cerr << "*"; + cerr << gotPool[b] << "=" << tmpGot << endl; + cerr << "error: 2" << FAIL; + } + + expectedPool[c] = tmpExpected; + gotPool[c] = tmpGot; + } + queries++; + } + } + cerr << "tested random queries: " << queries << endl; +} + +int main() { + stress_test(); +} + diff --git a/test/math/binomial0.cpp b/test/math/binomial0.cpp new file mode 100644 index 0000000..00c04d4 --- /dev/null +++ b/test/math/binomial0.cpp @@ -0,0 +1,31 @@ +#include "../util.h" +#include +#include +constexpr ll mod = 1'394'633'899; +#include + + +void stress_test() { + vector last = {1}; + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + for (ll j = 0; j <= i; j++) { + ll got = calc_binom(i, j); + ll expected = last[j]; + if (got != expected) cerr << "calc_binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL; + } + queries += sz(last); + + last.push_back(1); + for (ll j = i; j > 0; j--) { + last[j] = (last[j] + last[j - 1]) % mod; + } + } + cerr << "tested queries: " << queries << endl; +} + +int main() { + precalc(); + stress_test(); +} + diff --git a/test/math/binomial1.cpp b/test/math/binomial1.cpp new file mode 100644 index 0000000..f6fe20b --- /dev/null +++ b/test/math/binomial1.cpp @@ -0,0 +1,27 @@ +#include "../util.h" +#include + + +void stress_test() { + vector last = {1}; + ll queries = 0; + for (ll i = 0; i <= 61; i++) { + for (ll j = 0; j <= i; j++) { + ll got = calc_binom(i, j); + ll expected = last[j]; + if (got != expected) cerr << "calc_binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL; + } + queries += sz(last); + + last.push_back(1); + for (ll j = i; j > 0; j--) { + last[j] = last[j] + last[j - 1]; + } + } + cerr << "tested queries: " << queries << endl; +} + +int main() { + stress_test(); +} + diff --git a/test/math/binomial2.cpp b/test/math/binomial2.cpp new file mode 100644 index 0000000..b55c8af --- /dev/null +++ b/test/math/binomial2.cpp @@ -0,0 +1,29 @@ +#include "../util.h" +#include +#include + + +void stress_test() { + vector last = {1}; + ll queries = 0; + for (ll i = 0; i <= 1000; i++) { + for (ll j = 0; j <= i; j++) { + ll got = calc_binom(i, j); + ll expected = last[j]; + if (got != expected) cerr << "calc_binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL; + } + queries += sz(last); + + last.push_back(1); + for (ll j = i; j > 0; j--) { + last[j] = (last[j] + last[j - 1]) % mod; + } + } + cerr << "tested queries: " << queries << endl; +} + +int main() { + primeSieve(); + stress_test(); +} + diff --git a/test/math/binomial3.cpp b/test/math/binomial3.cpp new file mode 100644 index 0000000..4a99689 --- /dev/null +++ b/test/math/binomial3.cpp @@ -0,0 +1,31 @@ +#include "../util.h" +#include +#include +#include + + +constexpr ll mod = 503; + +void stress_test() { + vector last = {1}; + ll queries = 0; + for (ll i = 0; i < mod; i++) { + for (ll j = 0; j <= i; j++) { + ll got = calc_binom(i, j, mod); + ll expected = last[j]; + if (got != expected) cerr << "calc_binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL; + } + queries += sz(last); + + last.push_back(1); + for (ll j = i; j > 0; j--) { + last[j] = (last[j] + last[j - 1]) % mod; + } + } + cerr << "tested queries: " << queries << endl; +} + +int main() { + stress_test(); +} + diff --git a/test/math/chineseRemainder.cpp b/test/math/chineseRemainder.cpp new file mode 100644 index 0000000..26e71de --- /dev/null +++ b/test/math/chineseRemainder.cpp @@ -0,0 +1,47 @@ +#include "../util.h" +#include +#include + +struct NAIVE { + vector> added; + void add(ll a, ll m) { + added.emplace_back(a, m); + } + ll sol() const { + ll n = 1; + for (auto [_, x] : added) n = lcm(n, x); + for (ll i = 0; i < n; i++) { + bool ok = true; + for (auto [a, m] : added) { + ok &= (i % m) == a; + } + if (ok) return i; + } + return -1; + } +}; + +void stress_test() { + ll queries = 0; + ll withSol = 0; + for (ll i = 0; i < 100'000; i++) { + CRT crt; + NAIVE naive; + for (ll j = 0; j < 3; j++) { + int m = Random::integer(1, 50); + int a = Random::integer(0, m); + crt.add(a, m); + naive.add(a, m); + } + if (crt.hasSol != (naive.sol() >= 0)) cerr << "error" << FAIL; + if (crt.hasSol && crt.sol != naive.sol()) cerr << "got: " << (ll)crt.sol << ", expected: " << naive.sol() << FAIL; + queries += crt.M; + withSol += crt.hasSol; + } + cerr << "tested queries: " << queries << "(" << withSol << ")" << endl; +} + +int main() { + stress_test(); +} + diff --git a/test/math/cycleDetection.cpp b/test/math/cycleDetection.cpp new file mode 100644 index 0000000..bf57aed --- /dev/null +++ b/test/math/cycleDetection.cpp @@ -0,0 +1,47 @@ +#include "../util.h" +#include +#include + +pair naive(ll x0, function f) { + map seen; + ll d = 0; + while (seen.find(x0) == seen.end()) { + seen[x0] = d; + d++; + x0 = f(x0); + } + return {seen[x0], d - seen[x0]}; +} + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 1000'000; i++) { + int m = Random::integer(1, 100); + int c = Random::integer(0, m); + auto f = [&](ll x){return (x*x + c) % m;}; + int x0 = Random::integer(0, m); + auto got = cycleDetection(x0, f); + auto expected = naive(x0, f); + if (got != expected) cerr << "error: " << got.first << " " << got.second << " " << expected.first << " " << expected.second << FAIL; + queries += got.second; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr ll M = 18'086'183; +void performance_test() { + timer t; + auto f = [&](ll x){return (1337*x + 42) % M;}; + t.start(); + auto [a, b] = cycleDetection(42, f); + t.stop(); + hash_t hash = a + b; + if (t.time > 500) 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/math/discreteLogarithm.cpp b/test/math/discreteLogarithm.cpp new file mode 100644 index 0000000..0f9eecf --- /dev/null +++ b/test/math/discreteLogarithm.cpp @@ -0,0 +1,64 @@ +#include "../util.h" +#include +#include + +ll overwrite = 0; +ll getMemory(ll /**/) {return overwrite - 1;} //dlog code adds one... +#define sqrtl getMemory +#include +#undef sqrtl + +template +void stress_test(F&& f) { + ll work = 0; + for (ll tries = 0; tries < 3'000; tries++) { + ll p = Random::prime(1'000); + overwrite = f(p); + ll a = Random::integer(1, p); + vector naive(p); + for (ll i = 0, j = 1; i < p; i++, j = (j * a) % p) { + naive[j] = true; + } + for (ll b = 0; b < p; b++) { + ll got = dlog(a, b, p); + if (got < -1 || got >= p) cerr << "error: out of range" << FAIL; + if ((got >= 0) != naive[b]) { + cerr << a << " " << b << " " << p << endl; + cerr << got << endl; + cerr << "error" << FAIL; + } + if (got >= 0 && powMod(a, got, p) != b) { + cerr << a << "^" << got << " = " << powMod(a, got, p) << " != " << b << " % " << p << endl; + cerr << "error: wrong" << FAIL; + } + work++; + } + } + cerr << "stress tested: " << work << endl; +} + +constexpr int N = 25; +constexpr ll mod = 1'394'633'899; +void performance_test() { + timer t; + hash_t hash = 0; + overwrite = sqrt(mod); + for (int operations = 0; operations < N; operations++) { + ll a = Random::integer(1, mod); + ll b = Random::integer(0, mod); + t.start(); + hash += dlog(a, b, mod); + t.stop(); + } + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + + +int main() { + stress_test([](ll p){return sqrtl(p);}); + stress_test([](ll p){return min(10, p - 1);}); + stress_test([](ll p){return min(p - 1, sqrtl(p) + 100);}); + performance_test(); +} + diff --git a/test/math/discreteNthRoot.cpp b/test/math/discreteNthRoot.cpp new file mode 100644 index 0000000..d595e6d --- /dev/null +++ b/test/math/discreteNthRoot.cpp @@ -0,0 +1,78 @@ +#include "../util.h" +#define ll lll +#include +#undef ll +#include +#include + +ll phi(ll pk, ll p, ll /*k*/) {return pk - pk / p;} +ll phi(ll n) { // O(sqrt(n)) + ll res = 1; + for (ll p = 2; p * p <= n; p++) { + if (n % p == 0) { + ll pk = 1; + ll k = 0; + do { + n /= p; + pk *= p; + k++; + } while (n % p == 0); + res *= phi(pk, p, k); + }} + if (n > 1) res *= phi(n, n, 1); + return res; +} + +#include +#include +#include + +//x^a=b mod m +ll naiveRoot(ll a, ll b, ll m) { + for (ll i = 0; i < m; i++) { + if (powMod(i, a, m) == b) return i; + } + return -1; +} + +void stress_test() { + int queries = 0; + int found = 0; + for (int tries = 0; tries < 50'000; tries++) { + ll p = Random::prime(0, 1000); + ll a = Random::integer(1, p); + ll b = Random::integer(1, p); + + ll got = root(a, b, p); + ll expected = naiveRoot(a, b, p); + + if (got < -1 || got >= p) cerr << "error: out of range" << FAIL; + if (got >= 0 && powMod(got, a, p) != b) cerr << "error: wrong" << FAIL; + if ((got >= 0) != (expected >= 0)) cerr << "error" << FAIL; + queries++; + if (expected >= 0) found++; + } + cerr << "tested random queries: " << queries << " (" << found << ")" << endl; +} + +constexpr int N = 50; +constexpr ll mod = 1'394'633'899; +void performance_test() { + timer t; + hash_t hash = 0; + for (int i = 0; i < N; i++) { + ll a = Random::integer(1, mod); + ll b = Random::integer(1, mod); + t.start(); + hash += root(a, b, mod); + t.stop(); + } + if (t.time > 500) 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/math/divisors.cpp b/test/math/divisors.cpp new file mode 100644 index 0000000..2402d2a --- /dev/null +++ b/test/math/divisors.cpp @@ -0,0 +1,65 @@ +#include "../util.h" +#define ll lll +#include +#undef ll +#include + +bool isSquare(ll x) { + ll r = sqrtl(x); + while (r*r > x) r--; + while ((r+1)*(r+1) <= x) r++; + return r*r==x; +} + +#include + +ll naive(ll x) { + ll res = 0; + for (ll i = 1; i*i <= x; i++) { + if (x % i == 0) { + res++; + if (i*i != x) res++; + } + } + return res; +} + +void stress_test() { + ll work = 0; + for (ll i = 0; i < 1'000; i++) { + ll x = Random::integer(1, 1'000'000'000'000); + auto got = countDivisors(x); + auto expected = naive(x); + if (got != expected) cerr << "error: " << x << FAIL; + work += sqrt(x); + } + for (ll i = 0; i < 100'000; i++) { + ll x = Random::integer(1, 1'000'000); + auto got = countDivisors(x); + auto expected = naive(x); + if (got != expected) cerr << "error: " << x << FAIL; + work += sqrt(x); + } + cerr << "stress tested: " << work << endl; +} + +constexpr int N = 200; +void performance_test() { + timer t; + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll x = Random::integer(1e18 / 2, 1e18); + t.start(); + hash += countDivisors(x); + t.stop(); + } + if (t.time > 500) 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/math/extendedEuclid.cpp b/test/math/extendedEuclid.cpp new file mode 100644 index 0000000..597f722 --- /dev/null +++ b/test/math/extendedEuclid.cpp @@ -0,0 +1,41 @@ +#include "../util.h" +#include + +void stress_test() { + if (extendedEuclid(0, 0)[0] != 0) cerr << "error: extendedEuclid(0, 0)" << FAIL; + ll queries = 0; + timer t; + for (int i = 0; i < 1'000'000; i++) { + ll a = Random::integer(0, 1'000'000'000); + ll b = 0; + { + t.start(); + auto [got, x, y] = extendedEuclid(a, b); + t.stop(); + ll expected = std::gcd(a, b); + if (got != expected) cerr << "gcd(" << a << ", " << b << "), got: " << got << ", expected: " << expected << FAIL; + if (abs(x) >= max(2, abs(b))) cerr << "invalid x" << FAIL; + if (abs(y) >= max(2, abs(a))) cerr << "invalid y" << FAIL; + if (a*x + b*y != expected) cerr << "invalid x or y" << FAIL; + } + b = Random::integer(0, 1'000'000'000); + { + t.start(); + auto [got, x, y] = extendedEuclid(a, b); + t.stop(); + ll expected = std::gcd(a, b); + if (got != expected) cerr << "gcd(" << a << ", " << b << "), got: " << got << ", expected: " << expected << FAIL; + if (abs(x) >= max(2, abs(b))) cerr << "invalid x" << FAIL; + if (abs(y) >= max(2, abs(a))) cerr << "invalid y" << FAIL; + if (a*x + b*y != expected) cerr << "invalid x or y" << FAIL; + } + queries++; + } + cerr << "tested random queries: " << queries << endl; + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms" << endl; +} + +int main() { + stress_test(); +} diff --git a/test/math/gauss.cpp b/test/math/gauss.cpp new file mode 100644 index 0000000..37bacce --- /dev/null +++ b/test/math/gauss.cpp @@ -0,0 +1,118 @@ +#include "../util.h" +constexpr double EPS = 1e-9; +constexpr int UNIQUE = 1; +constexpr int INCONSISTENT = 2; +constexpr int MULTIPLE = 3; +vector> mat; +#include + +vector> inverseMat(const vector>& m) { + int n = sz(m); + mat = m; + for (int i = 0; i < n; i++) { + if (sz(mat[i]) != n) cerr << "error: no square matrix" << FAIL; + mat[i].resize(2*n); + mat[i][n+i] = 1; + } + gauss(n);//the unique cetc. checks are not usefull since we dont solve an lgs... + vector> res(m); + for (int i = 0; i < n; i++) { + res[i] = vector(mat[i].begin() + n, mat[i].end()); + for (int j = 0; j < n; j++) { + if (j != i && mat[i][j] != 0) cerr << "error: not full rank?" << FAIL; + if (j == i && mat[i][j] == 0) cerr << "error: not full rank?" << FAIL; + } + } + return res; +} + +vector> mul(const vector>& a, const vector>& b) { + int n = sz(a); + int m = sz(b[0]); + int x = sz(b); + if (sz(a[0]) != sz(b)) cerr << "error: wrong dimensions" << FAIL; + vector> res(n, vector(m)); + for (int i = 0; i < n; i++) { + for (int j = 0; j < m; j++) { + for (int k = 0; k < x; k++) { + res[i][j] += a[i][k] * b[k][j]; + } + } + } + return res; +} + +void test_tiny() { + mat = { + {1, 2, 3, 4}, + {0, 5, 6, 7}, + {0, 0, 8, 9}, + }; + if (gauss(sz(mat)) != UNIQUE) cerr << "error: 1" << FAIL; + + mat = { + {-1, 1, 0, -1}, + { 2, 6, 0, 10}, + { 1, -2, 0, 0}, + }; + if (gauss(sz(mat)) != MULTIPLE) cerr << "error: 2" << FAIL; + + mat = { + {-1, 1, 0, -1}, + { 2, 6, 0, 10}, + { 1, -2, 0, 1}, + }; + if (gauss(sz(mat)) != INCONSISTENT) cerr << "error: 3" << FAIL; +} + +void stress_test_inv() { + ll queries = 0; + for (int tries = 0; tries < 20'000; tries++) { + int n = Random::integer(1, 30); + + vector> m(n); + for (auto& v : m) v = Random::reals(n, 0, 1'000); + // m hopefully has full rank... + + auto inv = inverseMat(m); + + auto prod = mul(m, inv); + + for (int i = 0; i < n; i++) { + for (int j = 0; j < n; j++) { + if (i == j && abs(prod[i][j] - 1) >= EPS) cerr << "error: not inverted " << prod[i][j] << FAIL; + if (i != j && abs(prod[i][j] - 0) >= EPS) cerr << "error: not inverted " << prod[i][j] << FAIL; + } + } + + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 250; +void performance_test() { + timer t; + + vector> m(N); + for (auto& v : m) v = Random::reals(N, 0, 1'000); + mat = m; + + t.start(); + gauss(N); + t.stop(); + hash_t hash = 0; + for (int i = 0; i < N; i++) { + for (int j = 0; j < N; j++) { + hash += mat[i][j]; + } + } + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + test_tiny(); + stress_test_inv(); + performance_test(); +} diff --git a/test/math/gcd-lcm.cpp b/test/math/gcd-lcm.cpp new file mode 100644 index 0000000..294095b --- /dev/null +++ b/test/math/gcd-lcm.cpp @@ -0,0 +1,46 @@ +#include "../util.h" +#include + +void stress_test() { + if (::gcd(0, 0) != 0) cerr << "error: gcd(0, 0)" << FAIL; + if (::lcm(0, 0) != 0) cerr << "error: lcm(0, 0)" << FAIL; + ll queries = 0; + timer t; + for (int i = 0; i < 1'000'000; i++) { + ll a = Random::integer(0, 1'000'000'000); + ll b = 0; + { + ll got = ::gcd(a, b); + ll expected = std::gcd(a, b); + if (got != expected) cerr << "gcd(" << a << ", " << b << "), got: " << got << ", expected: " << expected << FAIL; + } + { + ll got = ::lcm(a, b); + ll expected = std::lcm(a, b); + if (got != expected) cerr << "lcm(" << a << ", " << b << "), got: " << got << ", expected: " << expected << FAIL; + } + b = Random::integer(0, 1'000'000'000); + { + t.start(); + ll got = ::gcd(a, b); + t.stop(); + ll expected = std::gcd(a, b); + if (got != expected) cerr << "gcd(" << a << ", " << b << "), got: " << got << ", expected: " << expected << FAIL; + } + { + t.start(); + ll got = ::lcm(a, b); + t.stop(); + ll expected = std::lcm(a, b); + if (got != expected) cerr << "lcm(" << a << ", " << b << "), got: " << got << ", expected: " << expected << FAIL; + } + queries++; + } + cerr << "tested random queries: " << queries << endl; + if (t.time > 750) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms" << endl; +} + +int main() { + stress_test(); +} diff --git a/test/math/goldenSectionSearch.cpp b/test/math/goldenSectionSearch.cpp new file mode 100644 index 0000000..565a21c --- /dev/null +++ b/test/math/goldenSectionSearch.cpp @@ -0,0 +1,74 @@ +#include "../util.h" +#include + +struct RandomFunction { + ld min; + vector> polys; + RandomFunction(ld l, ld r) : min(Random::real(l, r)) { + do { + polys.emplace_back( + Random::real(0, 1e9), + 2 * Random::integer(1, 5) + ); + } while(false && Random::integer(4) != 0); + } + + ld operator()(ld x){ + ld res = 0; + for (auto [m, p] : polys) { + res += m * pow(x - min, p); + } + return res; + } + + friend ostream& operator<<(ostream& os, const RandomFunction& f) { + string plus = ""; + for (auto [m, p] : f.polys) { + os << setprecision(15) << plus << m << "*(x-" << f.min << ")**" << p; + plus = "+"; + } + return os; + } +}; + +void stress_test() { + int queries = 0; + for (int i = 0; i < 50'000; i++) { + ld l = Random::real(-200, 200); + ld r = Random::real(-200, 200); + if (l > r) swap(l, r); + + RandomFunction f(l, r); + + ld got = gss(l, r, f); + ld expected = f.min; + if (float_error(got, expected) > 1e-6) { + cerr << f << endl; + cerr << "got: " << got << ", expected: " << expected << FAIL; + } + queries++; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 10'000; +void performance_test() { + timer t; + RandomFunction f(-200, 200); + f.polys.resize(1); + + hash_t hash = 0; + for (int i = 0; i < N; i++) { + t.start(); + hash += gss(-200, 200, f); + t.stop(); + } + if (t.time > 1000) 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/math/inversions.cpp b/test/math/inversions.cpp new file mode 100644 index 0000000..d2a54b7 --- /dev/null +++ b/test/math/inversions.cpp @@ -0,0 +1,43 @@ +#include "../util.h" +#include +#include + +ll naive(const vector& v) { + ll res = 0; + for (ll i = 0; i < sz(v); i++) { + for (ll j = 0; j < i; j++) { + if (v[j] > v[i]) res++; + } + } + return res; +} + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 100'000; i++) { + int n = Random::integer(1, 100); + auto v = Random::integers(n, -50, 50); + ll got = inversions(v); + ll expected = naive(v); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 200'000; +void performance_test() { + timer t; + auto v = Random::integers(N, -10'000, 10'000); + t.start(); + hash_t hash = inversions(v); + t.stop(); + if (t.time > 500) 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/math/inversionsMerge.cpp b/test/math/inversionsMerge.cpp new file mode 100644 index 0000000..85ab0d2 --- /dev/null +++ b/test/math/inversionsMerge.cpp @@ -0,0 +1,46 @@ +#include "../util.h" +#include + +ll naive(const vector& v) { + ll res = 0; + for (ll i = 0; i < sz(v); i++) { + for (ll j = 0; j < i; j++) { + if (v[j] > v[i]) res++; + } + } + return res; +} + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 100'000; i++) { + int n = Random::integer(1, 100); + vector v(n); + for (ll j = 0; j < n; j++) v[j] = (j-10) * 100000 + Random::integer(0, 10000);//values must be unique ): + shuffle(all(v), Random::rng); + ll expected = naive(v); + ll got = mergeSort(v); + if (got != expected) { + cerr << "got: " << got << ", expected: " << expected << FAIL; + } + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 2'000'000; //10 times faster +void performance_test() { + timer t; + auto v = Random::integers(N, -10'000, 10'000); + t.start(); + hash_t hash = mergeSort(v); + t.stop(); + if (t.time > 500) 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/math/kthperm.cpp b/test/math/kthperm.cpp new file mode 100644 index 0000000..16691b9 --- /dev/null +++ b/test/math/kthperm.cpp @@ -0,0 +1,38 @@ +#include "../util.h" +#include +#include + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int n = Random::integer(1, 100); + vector expected(n); + iota(all(expected), 0); + ll k = 0; + do { + auto got = kthperm(n, k); + if (got != expected) cerr << "error" << FAIL; + k++; + } while (k < 100 && next_permutation(all(expected))); + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 500'000; +void performance_test() { + timer t; + t.start(); + auto got = kthperm(N, 4'168'751'907'498'170ll); + t.stop(); + hash_t hash = 0; + for (ll i = 0; i < N; i++) hash += i * got[i]; + if (t.time > 500) 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/math/kthperm_permIndex.cpp b/test/math/kthperm_permIndex.cpp new file mode 100644 index 0000000..d84524e --- /dev/null +++ b/test/math/kthperm_permIndex.cpp @@ -0,0 +1,21 @@ +#include "../util.h" +#include +#include +#include + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + ll n = Random::integer(20, 1000); + ll expected = Random::integer(0, 1'000'000'000'000'000'000); + ll got = permIndex(kthperm(n, expected)); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +int main() { + stress_test(); +} + diff --git a/test/math/legendre.cpp b/test/math/legendre.cpp new file mode 100644 index 0000000..f210b57 --- /dev/null +++ b/test/math/legendre.cpp @@ -0,0 +1,43 @@ +#include "../util.h" +#define ll lll +#include +#undef ll +#include + +void stress_test() { + ll work = 0; + for (ll i = 0; i < 5'000; i++) { + ll p = Random::prime(5'000); + vector isSquare(p); + for (ll j = 1; j < p; j++) isSquare[(j*j) % p] = true; + for (ll j = 0; j < p; j++) { + auto got = legendre(j, p); + auto expected = j == 0 ? 0 : (isSquare[j] ? 1 : -1); + if (got != expected) cerr << "error: " << j << " " << p << FAIL; + } + work += p; + } + cerr << "stress tested: " << work << endl; +} + +constexpr int N = 1'000'000; +constexpr ll mod = 1'394'633'899; +void performance_test() { + timer t; + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll j = Random::integer(mod); + t.start(); + hash += legendre(j, mod); + 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/math/lgsFp.cpp b/test/math/lgsFp.cpp new file mode 100644 index 0000000..08f8f84 --- /dev/null +++ b/test/math/lgsFp.cpp @@ -0,0 +1,118 @@ +#include "../util.h" +#include +vector> mat; +#include + +constexpr ll mod = 1'000'000'007; + +vector> inverseMat(const vector>& m) { + int n = sz(m); + mat = m; + for (int i = 0; i < n; i++) { + if (sz(mat[i]) != n) cerr << "error: no square matrix" << FAIL; + mat[i].resize(2*n); + mat[i][n+i] = 1; + } + gauss(n, mod); + vector> res(m); + for (int i = 0; i < n; i++) { + res[i] = vector(mat[i].begin() + n, mat[i].end()); + for (int j = 0; j < n; j++) { + if (j != i && mat[i][j] != 0) cerr << "error: not full rank?" << FAIL; + if (j == i && mat[i][j] != 1) cerr << "error: not full rank?" << FAIL; + } + } + return res; +} + +vector> mul(const vector>& a, const vector>& b) { + int n = sz(a); + int m = sz(b[0]); + int x = sz(b); + if (sz(a[0]) != sz(b)) cerr << "error: wrong dimensions" << FAIL; + vector> res(n, vector(m)); + for (int i = 0; i < n; i++) { + for (int j = 0; j < m; j++) { + for (int k = 0; k < x; k++) { + res[i][j] += a[i][k] * b[k][j]; + res[i][j] %= mod; + } + } + } + return res; +} + +//this should just not crash... +void test_square() { + ll queries = 0; + hash_t hash = 0; + for (int tries = 0; tries < 1'000; tries++) { + int n = Random::integer(1, 30); + + vector> m(n); + for (auto& v : m) v = Random::integers(n, 0, mod); + mat = m; + gauss(n, mod); + + for (int i = 0; i < n; i++) { + for (int j = 0; j < n; j++) { + hash += mat[i][j]; + } + } + + queries += n; + } + cerr << "tested sqaures: " << queries << " (hash: " << hash << ")" << endl;; +} + +void stress_test_inv() { + ll queries = 0; + for (int tries = 0; tries < 20'000; tries++) { + int n = Random::integer(1, 30); + + vector> m(n); + for (auto& v : m) v = Random::integers(n, 0, mod); + // m hopefully has full rank... + + auto inv = inverseMat(m); + + auto prod = mul(m, inv); + + for (int i = 0; i < n; i++) { + for (int j = 0; j < n; j++) { + if (i == j && prod[i][j] != 1) cerr << "error: not inverted" << FAIL; + if (i != j && prod[i][j] != 0) cerr << "error: not inverted" << FAIL; + } + } + + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 250; +void performance_test() { + timer t; + + vector> m(N); + for (auto& v : m) v = Random::integers(N, 0, mod); + mat = m; + + t.start(); + gauss(N, mod); + t.stop(); + hash_t hash = 0; + for (int i = 0; i < N; i++) { + for (int j = 0; j < N; j++) { + hash += mat[i][j]; + } + } + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + test_square(); + stress_test_inv(); + performance_test(); +} diff --git a/test/math/linearCongruence.cpp b/test/math/linearCongruence.cpp new file mode 100644 index 0000000..ba8eeac --- /dev/null +++ b/test/math/linearCongruence.cpp @@ -0,0 +1,53 @@ +#include "../util.h" +#include +#include +#include + +ll naive(ll a, ll b, ll m) { + for (ll x = 0; x < m; x++) { + if ((a * x) % m == b) return x; + } + return -1; +} + +void stress_test() { + ll work = 0; + ll positive = 0; + for (ll tries = 0; tries < 500'000; tries++) { + ll m = Random::integer(0, 1'000); + ll a = Random::integer(0, m); + ll b = Random::integer(0, m); + + ll got = solveLinearCongruence(a, b, m); + ll expected = naive(a, b, m); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << endl; + work++; + if (got >= 0) positive++; + } + cerr << "stress tested: " << work << " (" << positive << ")" << endl; +} + +constexpr int N = 500'000; +void performance_test() { + timer t; + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll m = Random::integer(0, 1'0000'000'000); + ll a = Random::integer(0, m); + ll b = Random::integer(0, m); + + t.start(); + hash += solveLinearCongruence(a, b, m); + t.stop(); + } + if (t.time > 500) 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/math/linearRecurence.cpp b/test/math/linearRecurence.cpp new file mode 100644 index 0000000..a5290e5 --- /dev/null +++ b/test/math/linearRecurence.cpp @@ -0,0 +1,54 @@ +#include "../util.h" +#include + +struct RandomRecurence { + vector f, c, cache; + RandomRecurence(int n) : f(Random::integers(n, 0, mod)), c(Random::integers(n, 0, mod)), cache(f) {} + + ll operator()(ll k){ + while (sz(cache) <= k) { + ll cur = 0; + for (ll i = 0; i < sz(c); i++) { + cur += (c[i] * cache[sz(cache) - i - 1]) % mod; + } + cur %= mod; + cache.push_back(cur); + } + return cache[k]; + } +}; + +void stress_test() { + int queries = 0; + for (int i = 0; i < 10'000; i++) { + int n = Random::integer(1, 10); + RandomRecurence f(n); + for (int j = 0; j < 100; j++) { + ll k = Random::integer(0, 1000); + + ll got = kthTerm(f.f, f.c, k); + ll expected = f(k); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 1'000; +void performance_test() { + timer t; + RandomRecurence f(N); + t.start(); + hash_t hash = kthTerm(f.f, f.c, 1e18); + t.stop(); + if (t.time > 500) 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/math/linearSieve.cpp b/test/math/linearSieve.cpp new file mode 100644 index 0000000..8ea822b --- /dev/null +++ b/test/math/linearSieve.cpp @@ -0,0 +1,71 @@ +#include "../util.h" +namespace expected { +#include +} +#pragma GCC diagnostic ignored "-Wunused-parameter" +#include + +void stress_test() { + expected::primeSieve(); + expected::primes.resize(primes.size()); + if (expected::primes != primes) cerr << "error: primes" << FAIL; + int queries = 0; + for (int i = 1; i < 1'000'000; i++) { + auto got = sieved[i]; + auto expected = naive(i); + if (got != expected) cerr << i << ", got: " << got << ", expected: " << expected << FAIL; + queries++; + } + for (int i = 0; i < 1'000'000; i++) { + ll x = Random::integer(2, N); + auto got = sieved[x]; + auto expected = naive(x); + if (got != expected) cerr << x << ", got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested queries: " << queries << endl; +} + +void test_tiny() { + if (mu( 3, 3, 1) != -1) cerr << "error: 1" << FAIL; + if (mu( 9, 3, 2) != 0) cerr << "error: 2" << FAIL; + if (mu(27, 3, 3) != 0) cerr << "error: 3" << FAIL; + + if (phi( 3, 3, 1) != 2) cerr << "error: 4" << FAIL; + if (phi( 9, 3, 2) != 6) cerr << "error: 5" << FAIL; + if (phi(27, 3, 3) != 18) cerr << "error: 6" << FAIL; + + if (div( 3, 3, 1) != 2) cerr << "error: 7" << FAIL; + if (div( 9, 3, 2) != 3) cerr << "error: 8" << FAIL; + if (div(27, 3, 3) != 4) cerr << "error: 9" << FAIL; + + if (divSum( 3, 3, 1) != 4) cerr << "error: 10" << FAIL; + if (divSum( 9, 3, 2) != 13) cerr << "error: 11" << FAIL; + if (divSum(27, 3, 3) != 40) cerr << "error: 12" << FAIL; + + if (square( 3, 3, 1) != 1) cerr << "error: 13" << FAIL; + if (square( 9, 3, 2) != 9) cerr << "error: 14" << FAIL; + if (square(27, 3, 3) != 9) cerr << "error: 15" << FAIL; + + if (squareFree( 3, 3, 1) != 3) cerr << "error: 13" << FAIL; + if (squareFree( 9, 3, 2) != 3) cerr << "error: 14" << FAIL; + if (squareFree(27, 3, 3) != 3) cerr << "error: 15" << FAIL; + cerr << "tested tiny" << endl; +} + +void performance_test() { + timer t; + t.start(); + sieve(); + hash_t hash = sz(primes); + t.stop(); + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + performance_test(); + stress_test(); + test_tiny(); +} + diff --git a/test/math/longestIncreasingSubsequence.cpp b/test/math/longestIncreasingSubsequence.cpp new file mode 100644 index 0000000..407dafe --- /dev/null +++ b/test/math/longestIncreasingSubsequence.cpp @@ -0,0 +1,76 @@ +#include "../util.h" +constexpr ll INF = LL::INF; +#include +#define lis unstrictLis +#define lower_bound upper_bound +#include +#undef lower_bound +#undef lis + +template +bool isLis(const vector& a, const vector& lis) { + for (int i = 1; i < sz(lis); i++) { + if (lis[i-1] >= lis[i]) return false; + if (a[lis[i-1]] > a[lis[i]]) return false; + if (STRICT && a[lis[i-1]] == a[lis[i]]) return false; + } + return true; +} + +template +vector naive(const vector& a) { + vector res; + for (ll i = 1; i < (1ll << sz(a)); i++) { + vector tmp; + for (ll j = 0; j < sz(a); j++) { + if (((i >> j) & 1) != 0) tmp.push_back(j); + } + if (sz(tmp) >= sz(res) && isLis(a, tmp)) res = tmp; + } + return res; +} + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int n = Random::integer(1, 12); + auto a = Random::integers(n, -10, 10); + auto expected = naive(a); + auto got = lis(a); + if (got != expected) cerr << "error: strict" << FAIL; + queries += n; + } + for (ll i = 0; i < 10'000; i++) { + int n = Random::integer(1, 12); + auto a = Random::integers(n, -10, 10); + auto expected = naive(a); + auto got = unstrictLis(a); + if (got != expected) cerr << "error: not strict" << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 1'000'000; +void performance_test() { + timer t; + auto a = Random::integers(N, -10'000, 10'000); + auto b = Random::integers(N, -10'000, 10'000); + sort(all(b)); + auto c = Random::integers(N, -10'000, 10'000); + sort(all(c)); + reverse(all(c)); + hash_t hash = 0; + t.start(); + hash += lis(a).size(); + hash += lis(b).size(); + hash += lis(c).size(); + t.stop(); + if (t.time > 500) 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/math/matrixPower.cpp b/test/math/matrixPower.cpp new file mode 100644 index 0000000..4dfb0a8 --- /dev/null +++ b/test/math/matrixPower.cpp @@ -0,0 +1,116 @@ +#include "../util.h" + +constexpr ll mod = 1'394'633'899; + +struct mat { + vector> m; + mat(int dim = 0, int diag = 1) : m(dim, vector(dim)) { + for (int i = 0; i < dim; i++) m[i][i] = diag; + } + mat(const vector c) : m(sz(c), vector(sz(c))) { + m[0] = c; + for (ll i = 1; i < sz(c); i++) { + m[i][i-1] = 1; + } + } + + mat operator*(const mat& o) const { + int dim = sz(m); + mat res(dim, 0); + for (int i = 0; i < dim; i++) { + for (int j = 0; j < dim; j++) { + for (int k = 0; k < dim; k++) { + res.m[i][j] += m[i][k] * o.m[k][j]; + res.m[i][j] %= mod; + } + } + } + return res; + } + + vector operator*(const vector& o) const { + int dim = sz(m); + vector res(dim); + for (int i = 0; i < dim; i++) { + for (int j = 0; j < dim; j++) { + res[i] += m[i][j] * o[j]; + res[i] %= mod; + } + } + return res; + } +}; + +#include + +struct RandomRecurence { + vector f, c, cache; + RandomRecurence(int n) : f(Random::integers(n, 0, mod)), c(Random::integers(n, 0, mod)), cache(f) {} + + ll operator()(ll k){ + while (sz(cache) <= k) { + ll cur = 0; + for (ll i = 0; i < sz(c); i++) { + cur += (c[i] * cache[sz(cache) - i - 1]) % mod; + } + cur %= mod; + cache.push_back(cur); + } + return cache[k]; + } +}; + +void stress_test() { + int queries = 0; + for (int i = 0; i < 10'000; i++) { + int n = Random::integer(1, 10); + RandomRecurence f(n); + precalc(mat(f.c)); + auto tmp = f.f; + reverse(all(tmp)); + + for (int j = 0; j < 100; j++) { + ll k = Random::integer(0, 1000); + + vector got = calc(k, tmp); + vector expected(sz(f.f)); + for (ll l = 0; l < n; l++) expected[n - 1 - l] = f(k + l); + + if (got != expected) cerr << "error" << FAIL; + queries++; + } + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 100; +constexpr int M = 500; +void performance_test() { + timer t; + RandomRecurence f(N); + auto tmp = f.f; + reverse(all(tmp)); + + t.start(); + precalc(mat(f.c)); + t.stop(); + if (t.time > 500) cerr << "too slow precalc: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms" << endl; + + t.reset(); + hash_t hash = 0; + for (int i = 0; i < M; i++) { + ll k = Random::integer(1e17,1e18); + t.start(); + hash += calc(k, tmp).back(); + 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/math/millerRabin.base32.cpp b/test/math/millerRabin.base32.cpp new file mode 100644 index 0000000..742d353 --- /dev/null +++ b/test/math/millerRabin.base32.cpp @@ -0,0 +1,137 @@ +#include "../util.h" +#define ll lll +#include +#undef ll + +//this is hacky... +#define bool }\ +constexpr auto bases64 = c20::to_array(ignore::bases32);\ +bool +namespace ignore { +#include +#undef bool + +bool naive(ll x) { + for (ll i = 2; i*i <= x; i++) { + if (x % i == 0) return false; + } + return x > 1; +} + +ll mul(const map& facts) { + ll res = 1; + for (auto [p, c] : facts) { + for (int i = 0; i < c; i++) res *= p; + } + if (abs(res) > (1ll << 62)) cerr << "invalid number: " << res << FAIL; + return res; +} + +void extra_tests() { + vector> test = { + {{-1, 1}, {1, 1}}, + {{-2, 1}, {1, 1}}, + {{-7, 1}, {1, 1}}, + {{-19812365821, 1}, {1, 1}}, + {}, // 1 + {{2, 1}}, + {{3, 1}}, + {{2, 2}}, + {{5, 1}}, + {{2, 1}, {3, 1}}, + {{2, 2}, {3, 1}}, + {{2, 1}, {3, 2}}, + {{2, 2}, {3, 2}}, + {{2, 62}}, + {{2, 18}, {5, 18}}, + {{352523, 1}, {352817, 1}}, + {{41, 1}, {71, 1}, {421, 1}, {811, 1}}, + {{11, 1}, {17, 1}, {31, 1}, {61, 1}, {73, 1}, {66361, 1}}, + {{500000003, 1}, {1999999973, 1}}, + {{65537, 2}}, + {{999665081, 1}, {999716071, 1}}, + {{550177, 1}, {1100353, 1}, {1650529, 1}}, + {{459397, 1}, {918793, 1}, {1378189, 1}}, + {{37, 1}, {109, 1}}, + {{31, 1}, {151, 1}}, + {{239, 1}, {1429, 1}}, + {{89, 1}, {1093, 1}}, + {{2, 3}, {15800133918749317, 1}}, + {{12251, 1}, {85751, 1}}, + {{3, 1}, {5, 3}, {131, 1}, {6855593, 1}}, + {{5, 1}, {1927962474784631, 1}}, + {{197279, 1}, {1775503, 1}}, + {{3716371, 1}, {14865481, 1}}, + {{3, 1}, {5, 1}, {3075593, 1}, {3075593, 1}}, + {{4880401, 1}, {9760801, 1}}, + {{2822159, 1}, {11288633, 1}}, + {{3290341, 1}, {6580681, 1}}, + {{611557, 1}, {1834669, 1}}, + {{9227, 1}, {894923, 1}, {968731, 1}}, + {{3, 4}, {13, 1}, {62633, 2}}, + {{2, 2}, {3, 1}, {5, 1}, {167, 2}, {299197, 2}}, + {{332721269, 1}, {560937673, 1}}, + {{30702523, 1}, {122810089, 1}}, + {{24786439, 1}, {123932191, 1}}, + {{382500329, 1}, {1530001313, 1}}, + {{2, 4}, {5, 4}, {13, 1}, {30839, 2}}, + {{3, 1}, {385417, 1}, {7985344259, 1}}, + {{2, 4}, {3, 1}, {5, 1}, {7, 2}, {61, 1}, {179, 2}, {1381, 2}}, + {{627838711, 1}, {1212379867, 1}}, + {{3, 5}, {5, 3}, {41, 2}, {157321, 2}}, + {{5, 2}, {13, 1}}, + {{3, 1}, {5, 5}}, + {{2, 1}, {73, 1}, {193, 1}}, + {{5, 2}, {13, 1}, {19, 1}, {73, 1}}, + {{2, 3}, {3, 1}, {407521, 1}}, + {{2, 1}, {3, 1}, {299210837, 1}}, + {{2, 8}, {3, 4}, {5, 2}, {7, 2}, {11, 1}, {13, 1}, {17, 1}, {19, 1}, {23, 1}, {29, 1}, {3137, 1}}, + }; + + timer t; + for (auto factors : test) { + ll x = mul(factors); + if (x >= 1ll << 32) continue; + t.start(); + auto got = isPrime(x); + t.stop(); + bool expected = sz(factors) == 1 && factors.begin()->second == 1; + if (got != expected) cerr << "error: " << x << FAIL; + } + if (t.time > 10) cerr << "too slow" << FAIL; + cerr << "stress tested: " << t.time << "ms" << endl; +} + +void stress_test() { + ll work = 0; + for (ll i = 0; i < 10'000; i++) { + ll x = Random::integer(1, 1ll << 32); + auto got = isPrime(x); + auto expected = naive(x); + if (got != expected) cerr << "error: " << x << FAIL; + work += sqrt(x); + } + cerr << "stress tested: " << work << endl; +} + +constexpr int N = 200'000; +void performance_test() { + timer t; + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll x = Random::integer(1ll << 31, 1ll << 32); + t.start(); + hash += isPrime(x); + t.stop(); + } + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + + +int main() { + extra_tests(); + stress_test(); + performance_test(); +} + diff --git a/test/math/millerRabin.cpp b/test/math/millerRabin.cpp new file mode 100644 index 0000000..fd98586 --- /dev/null +++ b/test/math/millerRabin.cpp @@ -0,0 +1,129 @@ +#include "../util.h" +#define ll lll +#include +#undef ll +#include + +bool naive(ll x) { + for (ll i = 2; i*i <= x; i++) { + if (x % i == 0) return false; + } + return x > 1; +} + +ll mul(const map& facts) { + ll res = 1; + for (auto [p, c] : facts) { + for (int i = 0; i < c; i++) res *= p; + } + if (abs(res) > (1ll << 62)) cerr << "invalid number: " << res << FAIL; + return res; +} + +void extra_tests() { + vector> test = { + {{-1, 1}, {1, 1}}, + {{-2, 1}, {1, 1}}, + {{-7, 1}, {1, 1}}, + {{-19812365821, 1}, {1, 1}}, + {}, // 1 + {{2, 1}}, + {{3, 1}}, + {{2, 2}}, + {{5, 1}}, + {{2, 1}, {3, 1}}, + {{2, 2}, {3, 1}}, + {{2, 1}, {3, 2}}, + {{2, 2}, {3, 2}}, + {{2, 62}}, + {{2, 18}, {5, 18}}, + {{352523, 1}, {352817, 1}}, + {{41, 1}, {71, 1}, {421, 1}, {811, 1}}, + {{11, 1}, {17, 1}, {31, 1}, {61, 1}, {73, 1}, {66361, 1}}, + {{500000003, 1}, {1999999973, 1}}, + {{65537, 2}}, + {{999665081, 1}, {999716071, 1}}, + {{550177, 1}, {1100353, 1}, {1650529, 1}}, + {{459397, 1}, {918793, 1}, {1378189, 1}}, + {{37, 1}, {109, 1}}, + {{31, 1}, {151, 1}}, + {{239, 1}, {1429, 1}}, + {{89, 1}, {1093, 1}}, + {{2, 3}, {15800133918749317, 1}}, + {{12251, 1}, {85751, 1}}, + {{3, 1}, {5, 3}, {131, 1}, {6855593, 1}}, + {{5, 1}, {1927962474784631, 1}}, + {{197279, 1}, {1775503, 1}}, + {{3716371, 1}, {14865481, 1}}, + {{3, 1}, {5, 1}, {3075593, 1}, {3075593, 1}}, + {{4880401, 1}, {9760801, 1}}, + {{2822159, 1}, {11288633, 1}}, + {{3290341, 1}, {6580681, 1}}, + {{611557, 1}, {1834669, 1}}, + {{9227, 1}, {894923, 1}, {968731, 1}}, + {{3, 4}, {13, 1}, {62633, 2}}, + {{2, 2}, {3, 1}, {5, 1}, {167, 2}, {299197, 2}}, + {{332721269, 1}, {560937673, 1}}, + {{30702523, 1}, {122810089, 1}}, + {{24786439, 1}, {123932191, 1}}, + {{382500329, 1}, {1530001313, 1}}, + {{2, 4}, {5, 4}, {13, 1}, {30839, 2}}, + {{3, 1}, {385417, 1}, {7985344259, 1}}, + {{2, 4}, {3, 1}, {5, 1}, {7, 2}, {61, 1}, {179, 2}, {1381, 2}}, + {{627838711, 1}, {1212379867, 1}}, + {{3, 5}, {5, 3}, {41, 2}, {157321, 2}}, + {{5, 2}, {13, 1}}, + {{3, 1}, {5, 5}}, + {{2, 1}, {73, 1}, {193, 1}}, + {{5, 2}, {13, 1}, {19, 1}, {73, 1}}, + {{2, 3}, {3, 1}, {407521, 1}}, + {{2, 1}, {3, 1}, {299210837, 1}}, + {{2, 8}, {3, 4}, {5, 2}, {7, 2}, {11, 1}, {13, 1}, {17, 1}, {19, 1}, {23, 1}, {29, 1}, {3137, 1}}, + }; + + timer t; + for (auto factors : test) { + ll x = mul(factors); + t.start(); + auto got = isPrime(x); + t.stop(); + bool expected = sz(factors) == 1 && factors.begin()->second == 1; + if (got != expected) cerr << "error: " << x << FAIL; + } + if (t.time > 10) cerr << "too slow" << FAIL; + cerr << "stress tested: " << t.time << "ms" << endl; +} + +void stress_test() { + ll work = 0; + for (ll i = 0; i < 10'000; i++) { + ll x = Random::integer(1, 1'000'000'000'000); + auto got = isPrime(x); + auto expected = naive(x); + if (got != expected) cerr << "error: " << x << FAIL; + work += sqrt(x); + } + cerr << "stress tested: " << work << endl; +} + +constexpr int N = 200'000; +void performance_test() { + timer t; + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll x = Random::integer(1e18 / 2, 1e18); + t.start(); + hash += isPrime(x); + t.stop(); + } + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + + +int main() { + extra_tests(); + stress_test(); + performance_test(); +} + diff --git a/test/math/modExp.cpp b/test/math/modExp.cpp new file mode 100644 index 0000000..ebb38eb --- /dev/null +++ b/test/math/modExp.cpp @@ -0,0 +1,42 @@ +#include "../util.h" +#include + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int a = Random::integer(1, 100); + int n = Random::integer(2, 100); + ll expected = 1; + ll k = 0; + do { + auto got = powMod(a, k, n); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + k++; + expected = (expected * a) % n; + } while (k < 100); + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 1'000'000; +void performance_test() { + timer t; + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll a = Random::integer(0, 1'000'000'000); + ll b = Random::integer(0, 1'000'000'000); + ll n = Random::integer(2, 1'000'000'000); + t.start(); + hash += powMod(a, b, n); + 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/math/modMulIterativ.cpp b/test/math/modMulIterativ.cpp new file mode 100644 index 0000000..4f794c5 --- /dev/null +++ b/test/math/modMulIterativ.cpp @@ -0,0 +1,57 @@ +#include "../util.h" +#include + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int a = Random::integer(1, 100); + int n = Random::integer(2, 100); + ll expected = 0; + ll k = 0; + do { + auto got = mulMod(a, k, n); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + k++; + expected = (expected + a) % n; + } while (k < 100); + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +void stress_test_large() { + ll queries = 0; + for (ll i = 0; i < 1000'000; i++) { + ll a = Random::integer(0, 1'000'000'000'000'000'000); + ll b = Random::integer(0, 1'000'000'000'000'000'000); + ll n = Random::integer(2, 1'000'000'000'000'000'000); + ll expected = (lll)a * b % n; + auto got = mulMod(a, b, n); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 500'000; +void performance_test() { + timer t; + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll a = Random::integer(0, 1'000'000'000'000'000'000); + ll b = Random::integer(0, 1'000'000'000'000'000'000); + ll n = Random::integer(2, 1'000'000'000'000'000'000); + t.start(); + hash += mulMod(a, b, n); + 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(); + stress_test_large(); + performance_test(); +} + diff --git a/test/math/modPowIterativ.cpp b/test/math/modPowIterativ.cpp new file mode 100644 index 0000000..2cf0eb4 --- /dev/null +++ b/test/math/modPowIterativ.cpp @@ -0,0 +1,42 @@ +#include "../util.h" +#include + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int a = Random::integer(1, 100); + int n = Random::integer(2, 100); + ll expected = 1; + ll k = 0; + do { + auto got = powMod(a, k, n); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + k++; + expected = (expected * a) % n; + } while (k < 100); + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 1'000'000; +void performance_test() { + timer t; + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll a = Random::integer(0, 1'000'000'000); + ll b = Random::integer(0, 1'000'000'000); + ll n = Random::integer(2, 1'000'000'000); + t.start(); + hash += powMod(a, b, n); + 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/math/multInv.cpp b/test/math/multInv.cpp new file mode 100644 index 0000000..93763c5 --- /dev/null +++ b/test/math/multInv.cpp @@ -0,0 +1,40 @@ +#include "../util.h" +#include +#include + +void stress_test() { + ll queries = 0; + for (int i = 0; i < 10'000'000; i++) { + ll n = Random::integer(2, 1'000'000'000); + ll x = 0; + do { + x = Random::integer(0, n); + } while (gcd(x, n) != 1); + ll y = multInv(x, n); + ll got = (x*y) % n; + if (got != 1) cerr << "got: " << got << ", expected: 1" << FAIL; + queries++; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 1'000'000; +void performance_test() { + timer t; + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll a = Random::integer(0, 1'000'000'000); + ll b = Random::integer(2, 1'000'000'000); + t.start(); + hash += multInv(a, b); + 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/math/permIndex.cpp b/test/math/permIndex.cpp new file mode 100644 index 0000000..61d34c8 --- /dev/null +++ b/test/math/permIndex.cpp @@ -0,0 +1,39 @@ +#include "../util.h" +#include +#include + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int n = Random::integer(1, 100); + vector cur(n); + iota(all(cur), 0); + ll expected = 0; + do { + auto got = permIndex(cur); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + expected++; + } while (expected < 100 && next_permutation(all(cur))); + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 500'000; +void performance_test() { + timer t; + vector cur(N); + iota(all(cur), 0); + reverse(cur.end() - 10, cur.end()); + t.start(); + auto hash = permIndex(cur); + t.stop(); + if (t.time > 500) 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/math/piLegendre.cpp b/test/math/piLegendre.cpp new file mode 100644 index 0000000..c3513bf --- /dev/null +++ b/test/math/piLegendre.cpp @@ -0,0 +1,40 @@ +#include "../util.h" +#include +namespace legendre { + #include +} +namespace lehmer { + #include +} + +void stress_test() { + int queries = 0; + for (int i = 0; i < 1'000; i++) { + ll x = Random::integer(0, 1'000'000'000); + auto got = legendre::pi(x); + auto expected = lehmer::pi(x); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested random queries: " << queries << endl; +} + +void performance_test() { + timer t; + hash_t hash = 0; + for (int i = 0; i < 1; i++) { + ll x = Random::integer(0, 1000'000'000'000); + t.start(); + hash += legendre::pi(x); + t.stop(); + } + if (t.time > 1500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + lehmer::init(); + performance_test(); + stress_test(); +} + diff --git a/test/math/piLehmer.cpp b/test/math/piLehmer.cpp new file mode 100644 index 0000000..d84466f --- /dev/null +++ b/test/math/piLehmer.cpp @@ -0,0 +1,42 @@ +#include "../util.h" +#include +namespace legendre { + #include +} +namespace lehmer { + #include +} + +void stress_test() { + int queries = 0; + for (int i = 0; i < 1'000; i++) { + ll x = Random::integer(0, 1'000'000'000); + auto got = lehmer::pi(x); + auto expected = legendre::pi(x); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested random queries: " << queries << endl; +} + +void performance_test() { + timer t; + hash_t hash = 0; + t.start(); + lehmer::init(); + t.stop(); + for (int i = 0; i < 1; i++) { + ll x = Random::integer(0, 1000'000'000'000); + t.start(); + hash += lehmer::pi(x); + t.stop(); + } + if (t.time > 1500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + performance_test(); + stress_test(); +} + diff --git a/test/math/primeSieve.cpp b/test/math/primeSieve.cpp new file mode 100644 index 0000000..78a50d2 --- /dev/null +++ b/test/math/primeSieve.cpp @@ -0,0 +1,47 @@ +#include "../util.h" +#include + +bool naive(ll x) { + for (ll i = 2; i*i <= x; i++) { + if (x % i == 0) return false; + } + return x > 1; +} + +void stress_test() { + int queries = 0; + vector found; + for (int i = -5; i < 1'000'000; i++) { + auto got = isPrime(i); + auto expected = naive(i); + if (got != expected) cerr << "error: " << i << FAIL; + if (got) found.push_back(i); + queries++; + } + primes.resize(sz(found)); + if (primes != found) cerr << "error: primes" << FAIL; + for (int i = 0; i < 1'000'000; i++) { + ll x = Random::integer(2, N); + auto got = isPrime(x); + auto expected = naive(x); + if (got != expected) cerr << "error: " << x << FAIL; + queries++; + } + cerr << "tested queries: " << queries << endl; +} + +void performance_test() { + timer t; + t.start(); + primeSieve(); + hash_t hash = sz(primes); + t.stop(); + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + performance_test(); + stress_test(); +} + diff --git a/test/math/primitiveRoot.cpp b/test/math/primitiveRoot.cpp new file mode 100644 index 0000000..cd0b388 --- /dev/null +++ b/test/math/primitiveRoot.cpp @@ -0,0 +1,82 @@ +#include "../util.h" +#define ll lll +#include +#undef ll +#include +#include + +ll phi(ll pk, ll p, ll /*k*/) {return pk - pk / p;} +ll phi(ll n) { // O(sqrt(n)) + ll res = 1; + for (ll p = 2; p * p <= n; p++) { + if (n % p == 0) { + ll pk = 1; + ll k = 0; + do { + n /= p; + pk *= p; + k++; + } while (n % p == 0); + res *= phi(pk, p, k); + }} + if (n > 1) res *= phi(n, n, 1); + return res; +} + +#include + +bool naiveIsPrimitive(ll g, ll n) { + if (gcd(g, n) != 1) return false; + vector seen(n); + ll c = g; + for (ll i = 0; i < n; i++) { + seen[c] = true; + c = (c * g) % n; + } + ll res = 0; + for (bool x : seen) if (x) res++; + return res == phi(n); +} + +void stress_test() { + int queries = 0; + for (int tries = 0; tries < 20'000; tries++) { + ll a = Random::integer(1, 3); + ll p = Random::prime(0, 1000); + ll k = p == 2 ? 1 : Random::integer(1, log(100'000) / log(p) + 1); + + ll x = a; + for (int i = 0; i < k; i++) x *= p; + + ll got = findPrimitive(x); + + if (got < 0 || got >= x) cerr << "error: out of range" << FAIL; + if (!naiveIsPrimitive(got, x)) cerr << "error: wrong" << got << " " << x << FAIL; + queries++; + } + cerr << "tested random queries: " << queries << endl; +} + +void stress_test2() { + int queries = 0; + for (int x = 2; x < 5'000; x++) { + map facts; + factor(x, facts); + if (x % 2 == 0) facts.erase(facts.find(2)); + bool expected = sz(facts) == 1; + if (x % 4 == 0) expected = false; + if (x == 2 || x == 4) expected = true; + + bool got = findPrimitive(x) >= 0; + + if (got != expected) cerr << "error" << FAIL; + queries++; + } + cerr << "tested random queries: " << queries << endl; +} + +int main() { + stress_test(); + stress_test2(); +} + diff --git a/test/math/rho.cpp b/test/math/rho.cpp new file mode 100644 index 0000000..5e4792a --- /dev/null +++ b/test/math/rho.cpp @@ -0,0 +1,117 @@ +#include "../util.h" +#define ll lll +#include +#undef ll +#include +#include + +map factor(ll n) { + map facts; + factor(n, facts); + return facts; +} + +ll mul(const map& facts) { + ll res = 1; + for (auto [p, c] : facts) { + for (int i = 0; i < c; i++) res *= p; + } + if (res < 1 || res > (1ll << 62)) cerr << "invalid number: " << res << FAIL; + return res; +} + +void stress_test() { + vector> test = { + {}, // 1 + {{2, 1}}, + {{3, 1}}, + {{2, 2}}, + {{5, 1}}, + {{2, 1}, {3, 1}}, + {{2, 2}, {3, 1}}, + {{2, 1}, {3, 2}}, + {{2, 2}, {3, 2}}, + {{2, 62}}, + {{2, 18}, {5, 18}}, + {{352523, 1}, {352817, 1}}, + {{41, 1}, {71, 1}, {421, 1}, {811, 1}}, + {{11, 1}, {17, 1}, {31, 1}, {61, 1}, {73, 1}, {66361, 1}}, + {{500000003, 1}, {1999999973, 1}}, + {{65537, 2}}, + {{999665081, 1}, {999716071, 1}}, + {{550177, 1}, {1100353, 1}, {1650529, 1}}, + {{459397, 1}, {918793, 1}, {1378189, 1}}, + {{37, 1}, {109, 1}}, + {{31, 1}, {151, 1}}, + {{239, 1}, {1429, 1}}, + {{89, 1}, {1093, 1}}, + {{2, 3}, {15800133918749317, 1}}, + {{12251, 1}, {85751, 1}}, + {{3, 1}, {5, 3}, {131, 1}, {6855593, 1}}, + {{5, 1}, {1927962474784631, 1}}, + {{197279, 1}, {1775503, 1}}, + {{3716371, 1}, {14865481, 1}}, + {{3, 1}, {5, 1}, {3075593, 1}, {3075593, 1}}, + {{4880401, 1}, {9760801, 1}}, + {{2822159, 1}, {11288633, 1}}, + {{3290341, 1}, {6580681, 1}}, + {{611557, 1}, {1834669, 1}}, + {{9227, 1}, {894923, 1}, {968731, 1}}, + {{3, 4}, {13, 1}, {62633, 2}}, + {{2, 2}, {3, 1}, {5, 1}, {167, 2}, {299197, 2}}, + {{332721269, 1}, {560937673, 1}}, + {{30702523, 1}, {122810089, 1}}, + {{24786439, 1}, {123932191, 1}}, + {{382500329, 1}, {1530001313, 1}}, + {{2, 4}, {5, 4}, {13, 1}, {30839, 2}}, + {{3, 1}, {385417, 1}, {7985344259, 1}}, + {{2, 4}, {3, 1}, {5, 1}, {7, 2}, {61, 1}, {179, 2}, {1381, 2}}, + {{627838711, 1}, {1212379867, 1}}, + {{3, 5}, {5, 3}, {41, 2}, {157321, 2}}, + {{5, 2}, {13, 1}}, + {{3, 1}, {5, 5}}, + {{2, 1}, {73, 1}, {193, 1}}, + {{5, 2}, {13, 1}, {19, 1}, {73, 1}}, + {{2, 3}, {3, 1}, {407521, 1}}, + {{2, 1}, {3, 1}, {299210837, 1}}, + {{2, 8}, {3, 4}, {5, 2}, {7, 2}, {11, 1}, {13, 1}, {17, 1}, {19, 1}, {23, 1}, {29, 1}, {3137, 1}}, + }; + + timer t; + for (auto expected : test) { + ll x = mul(expected); + t.start(); + auto got = factor(x); + t.stop(); + if (got != expected) { + cerr << "number: " << x << endl; + cerr << "got:" << endl; + for (auto [p, c] : got) cerr << p << "^" << c << endl; + cerr << "expected" << endl; + for (auto [p, c] : expected) cerr << p << "^" << c << endl; + cerr << FAIL; + } + } + if (t.time > 100) cerr << "too slow" << FAIL; + cerr << "stress tested: " << t.time << "ms" << endl; +} + +constexpr int N = 2'000; +void performance_test() { + timer t; + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll x = Random::integer(1e18 / 2, 1e18); + t.start(); + hash += factor(x).size(); + t.stop(); + } + if (t.time > 500) 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/math/shortModInv.cpp b/test/math/shortModInv.cpp new file mode 100644 index 0000000..26960bf --- /dev/null +++ b/test/math/shortModInv.cpp @@ -0,0 +1,39 @@ +#include "../util.h" +#include + +void stress_test() { + ll queries = 0; + for (int i = 0; i < 10'000'000; i++) { + ll n = Random::integer(2, 1'000'000'000); + ll x = 0; + do { + x = Random::integer(0, n); + } while (gcd(x, n) != 1); + ll y = multInv(x, n); + ll got = (x*y) % n; + if (got != 1) cerr << "got: " << got << ", expected: 1" << FAIL; + queries++; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 1'000'000; +void performance_test() { + timer t; + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll a = Random::integer(0, 1'000'000'000); + ll b = Random::integer(2, 1'000'000'000); + t.start(); + hash += multInv(a, b); + 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/math/simpson.cpp b/test/math/simpson.cpp new file mode 100644 index 0000000..d7cdba3 --- /dev/null +++ b/test/math/simpson.cpp @@ -0,0 +1,63 @@ +#include "../util.h" +std::function f; +constexpr double EPS = 1e-9; +#include + +struct RandomPolynom { + vector polynom; + RandomPolynom(int deg) : polynom(deg) { + for (auto& x : polynom) x = Random::real(-100, 100); + } + double operator()(double x) const { + double res = 0; + double xx = 1; + for (double y : polynom ) { + res += xx * y; + xx *= x; + } + return res; + } + double area(double a, double b) const { + double res = 0; + double aa = a; + double bb = b; + ll d = 1; + for (double y : polynom) { + res += bb / d * y; + res -= aa / d * y; + aa *= a; + bb *= b; + d++; + } + return res; + } +}; + +void stress_test() { + timer t; + ll queries = 0; + for (int tries = 0; tries < 1'000; tries++) { + ll n = Random::integer(0, 6); + RandomPolynom poly(n); + f = poly; + for (ll i = 0; i < 200; i++) { + double l = Random::real(-20, 20); + double r = Random::real(-20, 20); + if (l > r) swap(l, r); + + t.start(); + double got = integrate(l, r); + t.stop(); + double expected = poly.area(l, r); + if (float_error(got, expected) > 1e-6) cerr << fixed << setprecision(20) << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + } + if (t.time > 5000) cerr << "too slow: " << t.time << FAIL; + cerr << "tested random queries: " << queries << " (" << t.time << "ms)" << endl; +} + +int main() { + stress_test(); +} + diff --git a/test/math/sqrtModCipolla.cpp b/test/math/sqrtModCipolla.cpp new file mode 100644 index 0000000..26d975b --- /dev/null +++ b/test/math/sqrtModCipolla.cpp @@ -0,0 +1,48 @@ +#include "../util.h" +#include +#include +mt19937 rng(123456789); +#include + +void stress_test(ll range) { + ll work = 0; + for (ll i = 0; i < 10'000; i++) { + ll p = Random::prime(range); + for (ll j = 0; j < 100; j++) { + ll x = Random::integer(0, p); + if (legendre(x, p) < 0) continue; + + ll got = sqrtMod(x, p); + if (got < 0 || got >= p) cerr << "error: out of range" << FAIL; + if ((got * got) % p != x) cerr << "error: not root" << FAIL; + work++; + } + } + cerr << "stress tested: " << work << endl; +} + +constexpr int N = 200'000; +constexpr ll mod = 1'394'633'899; +void performance_test() { + timer t; + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll x; + do { + x = Random::integer(0, mod); + } while (legendre(x, mod) >= 0); + t.start(); + hash += sqrtMod(x, mod); + 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(1'000); + stress_test(1'000'000'000); + performance_test(); +} + diff --git a/test/math/transforms/andTransform.cpp b/test/math/transforms/andTransform.cpp new file mode 100644 index 0000000..fa029f6 --- /dev/null +++ b/test/math/transforms/andTransform.cpp @@ -0,0 +1,38 @@ +#include "../../util.h" +#include + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int n = 1ll << Random::integer(0, 10); + auto expected = Random::integers(n, -1000, 1000); + auto got = expected; + fft(got, false); + fft(got, true); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 1ll << 23; +void performance_test() { + timer t; + vector a = Random::integers(N, -1000, 1000); + vector b = Random::integers(N, -1000, 1000); + t.start(); + fft(a, true); + fft(b, false); + t.stop(); + hash_t hash = 0; + for (ll i = 0; i < N; i++) hash += i * a[i]; + for (ll i = 0; i < N; i++) hash += i * b[i]; + if (t.time > 500) 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/math/transforms/bitwiseTransforms.cpp b/test/math/transforms/bitwiseTransforms.cpp new file mode 100644 index 0000000..132740c --- /dev/null +++ b/test/math/transforms/bitwiseTransforms.cpp @@ -0,0 +1,38 @@ +#include "../../util.h" +#include + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int n = 1ll << Random::integer(0, 10); + auto expected = Random::integers(n, -1000, 1000); + auto got = expected; + bitwiseConv(got, false); + bitwiseConv(got, true); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 1ll << 23; +void performance_test() { + timer t; + vector a = Random::integers(N, -1000, 1000); + vector b = Random::integers(N, -1000, 1000); + t.start(); + bitwiseConv(a, true); + bitwiseConv(b, false); + t.stop(); + hash_t hash = 0; + for (ll i = 0; i < N; i++) hash += i * a[i]; + for (ll i = 0; i < N; i++) hash += i * b[i]; + if (t.time > 500) 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/math/transforms/fft.cpp b/test/math/transforms/fft.cpp new file mode 100644 index 0000000..858676b --- /dev/null +++ b/test/math/transforms/fft.cpp @@ -0,0 +1,51 @@ +#include "../../util.h" +#include + +vector to_cplx(const vector& in) { + vector res(sz(in)); + for (int i = 0; i < sz(in); i++) res[i] = in[i]; + return res; +} + +vector from_cplx(const vector& in) { + vector res(sz(in)); + for (int i = 0; i < sz(in); i++) res[i] = llround(real(in[i])); + return res; +} + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int n = 1ll << Random::integer(0, 10); + auto expected = Random::integers(n, -1000, 1000); + vector tmp = to_cplx(expected); + fft(tmp, false); + fft(tmp, true); + auto got = from_cplx(tmp); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 1ll << 21; +void performance_test() { + timer t; + auto a = to_cplx(Random::integers(N, -1000, 1000)); + auto b = to_cplx(Random::integers(N, -1000, 1000)); + t.start(); + fft(a, true); + fft(b, false); + t.stop(); + hash_t hash = 0; + for (ll i = 0; i < N; i++) hash += i * llround(real(a[i])); + for (ll i = 0; i < N; i++) hash += i * llround(real(b[i])); + if (t.time > 500) 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/math/transforms/fftMul.cpp b/test/math/transforms/fftMul.cpp new file mode 100644 index 0000000..5933864 --- /dev/null +++ b/test/math/transforms/fftMul.cpp @@ -0,0 +1,62 @@ +#include "../../util.h" +#include +#include +#pragma GCC diagnostic ignored "-Wnarrowing" +#include + +vector from_cplx(const vector& in) { + vector res(sz(in)); + for (int i = 0; i < sz(in); i++) res[i] = llround(real(in[i])); + return res; +} + +vector naive(const vector& a, const vector& b) { + vector res; + for (ll i = 1;; i *= 2) { + if (sz(a) + sz(b) <= i) { + res.resize(i, 0); + break; + } + } + for (int i = 0; i < sz(a); i++) { + for (int j = 0; j < sz(b); j++) { + res[i+j] += a[i] * b[j]; + } + } + return res; +} + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int n = Random::integer(1, 100); + int m = Random::integer(1, 100); + auto a = Random::integers(n, -1000, 1000); + auto b = Random::integers(m, -1000, 1000); + auto expected = naive(a, b); + auto got = from_cplx(mul(a, b)); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 1ll << 20; +void performance_test() { + timer t; + vector a = Random::integers(N, -1000, 1000); + vector b = Random::integers(N, -1000, 1000); + t.start(); + auto got = from_cplx(mul(a, b)); + t.stop(); + hash_t hash = 0; + for (ll i = 0; i < N; i++) hash += i * got[i]; + if (t.time > 500) 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/math/transforms/multiplyBitwise.cpp b/test/math/transforms/multiplyBitwise.cpp new file mode 100644 index 0000000..bc73290 --- /dev/null +++ b/test/math/transforms/multiplyBitwise.cpp @@ -0,0 +1,55 @@ +#include "../../util.h" +#include +#include +#include + +vector naive(const vector& a, const vector& b) { + vector res; + for (ll i = 1;; i *= 2) { + if (sz(a) <= i && sz(b) <= i) { + res.resize(i, 0); + break; + } + } + for (int i = 0; i < sz(a); i++) { + for (int j = 0; j < sz(b); j++) { + res[i&j] += a[i] * b[j]; + } + } + return res; +} + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int n = Random::integer(1, 100); + int m = Random::integer(1, 100); + auto a = Random::integers(n, -1000, 1000); + auto b = Random::integers(m, -1000, 1000); + auto expected = naive(a, b); + auto got = mul(a, b); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 1ll << 22; +void performance_test() { + timer t; + vector a = Random::integers(N, -1000, 1000); + vector b = Random::integers(N, -1000, 1000); + t.start(); + auto got = mul(a, b); + t.stop(); + hash_t hash = 0; + for (ll i = 0; i < N; i++) hash += i * got[i]; + if (t.time > 500) 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/math/transforms/multiplyFFT.cpp b/test/math/transforms/multiplyFFT.cpp new file mode 100644 index 0000000..782be1b --- /dev/null +++ b/test/math/transforms/multiplyFFT.cpp @@ -0,0 +1,55 @@ +#include "../../util.h" +#include +#include +#include + +vector naive(const vector& a, const vector& b) { + vector res; + for (ll i = 1;; i *= 2) { + if (sz(a) + sz(b) <= i) { + res.resize(i, 0); + break; + } + } + for (int i = 0; i < sz(a); i++) { + for (int j = 0; j < sz(b); j++) { + res[i+j] += a[i] * b[j]; + } + } + return res; +} + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int n = Random::integer(1, 100); + int m = Random::integer(1, 100); + auto a = Random::integers(n, -1000, 1000); + auto b = Random::integers(m, -1000, 1000); + auto expected = naive(a, b); + auto got = mul(a, b); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 1ll << 19; +void performance_test() { + timer t; + vector a = Random::integers(N, -1000, 1000); + vector b = Random::integers(N, -1000, 1000); + t.start(); + auto got = mul(a, b); + t.stop(); + hash_t hash = 0; + for (ll i = 0; i < N; i++) hash += i * got[i]; + if (t.time > 500) 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/math/transforms/multiplyNTT.cpp b/test/math/transforms/multiplyNTT.cpp new file mode 100644 index 0000000..70fc137 --- /dev/null +++ b/test/math/transforms/multiplyNTT.cpp @@ -0,0 +1,56 @@ +#include "../../util.h" +#include +#include +#include + +vector naive(const vector& a, const vector& b) { + vector res; + for (ll i = 1;; i *= 2) { + if (sz(a) + sz(b) <= i) { + res.resize(i, 0); + break; + } + } + for (int i = 0; i < sz(a); i++) { + for (int j = 0; j < sz(b); j++) { + res[i+j] += a[i] * b[j]; + res[i+j] %= mod; + } + } + return res; +} + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int n = Random::integer(1, 100); + int m = Random::integer(1, 100); + auto a = Random::integers(n, 0, mod); + auto b = Random::integers(m, 0, mod); + auto expected = naive(a, b); + auto got = mul(a, b); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 1ll << 20; +void performance_test() { + timer t; + vector a = Random::integers(N, 0, mod); + vector b = Random::integers(N, 0, mod); + t.start(); + auto got = mul(a, b); + t.stop(); + hash_t hash = 0; + for (ll i = 0; i < N; i++) hash += i * got[i]; + if (t.time > 500) 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/math/transforms/ntt.cpp b/test/math/transforms/ntt.cpp new file mode 100644 index 0000000..cd32073 --- /dev/null +++ b/test/math/transforms/ntt.cpp @@ -0,0 +1,39 @@ +#include "../../util.h" +#include +#include + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int n = 1ll << Random::integer(0, 10); + auto expected = Random::integers(n, 0, mod); + auto got = expected; + ntt(got, false); + ntt(got, true); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 1ll << 22; +void performance_test() { + timer t; + vector a = Random::integers(N, 0, mod); + vector b = Random::integers(N, 0, mod); + t.start(); + ntt(a, true); + ntt(b, false); + t.stop(); + hash_t hash = 0; + for (ll i = 0; i < N; i++) hash += i * a[i]; + for (ll i = 0; i < N; i++) hash += i * b[i]; + if (t.time > 500) 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/math/transforms/orTransform.cpp b/test/math/transforms/orTransform.cpp new file mode 100644 index 0000000..0ec9155 --- /dev/null +++ b/test/math/transforms/orTransform.cpp @@ -0,0 +1,38 @@ +#include "../../util.h" +#include + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int n = 1ll << Random::integer(0, 10); + auto expected = Random::integers(n, -1000, 1000); + auto got = expected; + fft(got, false); + fft(got, true); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 1ll << 23; +void performance_test() { + timer t; + vector a = Random::integers(N, -1000, 1000); + vector b = Random::integers(N, -1000, 1000); + t.start(); + fft(a, true); + fft(b, false); + t.stop(); + hash_t hash = 0; + for (ll i = 0; i < N; i++) hash += i * a[i]; + for (ll i = 0; i < N; i++) hash += i * b[i]; + if (t.time > 500) 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/math/transforms/xorTransform.cpp b/test/math/transforms/xorTransform.cpp new file mode 100644 index 0000000..17b0f6f --- /dev/null +++ b/test/math/transforms/xorTransform.cpp @@ -0,0 +1,38 @@ +#include "../../util.h" +#include + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int n = 1ll << Random::integer(0, 10); + auto expected = Random::integers(n, -1000, 1000); + auto got = expected; + fft(got, false); + fft(got, true); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 1ll << 23; +void performance_test() { + timer t; + vector a = Random::integers(N, -1000, 1000); + vector b = Random::integers(N, -1000, 1000); + t.start(); + fft(a, true); + fft(b, false); + t.stop(); + hash_t hash = 0; + for (ll i = 0; i < N; i++) hash += i * a[i]; + for (ll i = 0; i < N; i++) hash += i * b[i]; + if (t.time > 500) 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/compiletime.cpp b/test/other/compiletime.cpp new file mode 100644 index 0000000..591669d --- /dev/null +++ b/test/other/compiletime.cpp @@ -0,0 +1,2 @@ +#include +int main() {} \ No newline at end of file diff --git a/test/other/divideAndConquer.cpp b/test/other/divideAndConquer.cpp new file mode 100644 index 0000000..a6fda9d --- /dev/null +++ b/test/other/divideAndConquer.cpp @@ -0,0 +1,103 @@ +#include "../util.h" +constexpr ll inf = LL::INF; +#include + +vector> gen(int n) { + vector> res(n, vector(n)); + ll mi = 0; + for (ll a = n-1; a >= 0; a--) { + for (ll c = n-1; c >= a; c--) { + for (ll b = a; b <= c; b++) { + for (ll d = c; d < n; d++) { + res[a][c] = min(res[a][c], res[a][d] + res[b][c] - res[b][d]); + } + } + res[a][c] -= Random::integer(0, 1000); + mi = min(mi, res[a][c]); + } + } + for (auto& v : res) for (auto& x : v) x -= mi; + + for (ll a = 0; a < n; a++) { + for (ll b = a; b < n; b++) { + for (ll c = b; c < n; c++) { + for (ll d = c; d < n; d++) { + if (res[a][d] < 0 || res[a][d] + res[b][c] < res[a][c] + res[b][d]) { + cerr << "invalid C array!" << FAIL; + } + } + } + } + } + return res; +} + +vector> genQuick(int n) { + vector> res(n, vector(n)); + for (ll a = n-1; a >= 0; a--) { + for (ll c = n-1; c >= a; c--) { + res[a][c] = (c-a) * (c - a) + Random::integer(0, 2); + } + } + return res; +} + +/*ll naive(int n, int m) { + vector> state(m+1, vector(n+1, inf)); + state[0][0] = 0; + for (int i = 1; i <= m; i++) { + for (int j = 1; j <= n; j++) { + for (int k = 1; k <= j; k++) { + state[i][j] = min(state[i][j], state[i-1][k-1] + C[k-1][j-1]); + } + } + } + return state[m][n]; +}*/ + +vector naive(int n) { + vector> state(n+1, vector(n+1, inf)); + state[0][0] = 0; + vector 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++) { + state[i][j] = min(state[i][j], state[i-1][k-1] + C[k-1][j-1]); + } + } + res[i] = state[i][n]; + } + return res; +} + +void stress_test() { + ll tests = 0; + for (ll i = 0; i < 1000; i++) { + auto n = Random::integer(10, 20); + C = gen(n); + auto expected = naive(n); + for (ll m = 1; m <= n; m++) { + auto got = calc(n, m); + if (got != expected[m]) cerr << "got: " << got << ", expected: " << expected[m] << FAIL; + tests++; + } + } + cerr << "tested random queries: " << tests << endl; +} + +constexpr int N = 10'000; +void performance_test() { + timer t; + C = genQuick(N); + t.start(); + auto hash = calc(N, 32); + t.stop(); + if (t.time > 50) 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/fastIO.cpp b/test/other/fastIO.cpp new file mode 100644 index 0000000..765ddba --- /dev/null +++ b/test/other/fastIO.cpp @@ -0,0 +1,32 @@ +#include "../util.h" +#include + +int main() { + if (freopen("other/fastIO.in", "r", stdin) == nullptr) cerr << "fastIO.in not found" << FAIL; + vector got(5); + vector expected = {4, 7, 3, 6, 9}; + for (int& x : got) fastscan(x); + if (got != expected) cerr << "failed fastscan" << FAIL; + + if (freopen("other/fastIO.out", "w", stdout) == nullptr) cerr << "fastIO.out not writebale" << FAIL; + fastprint(0); + putchar('\n'); + fastprint(-1); + putchar(' '); + fastprint(-8321648); + putchar(' '); + fastprint(1); + putchar(' '); + fastprint(42387); + putchar('\n'); + fclose(stdout); + + stringstream buffer; + { + ifstream tmp("other/fastIO.out"); + buffer << tmp.rdbuf(); + } + if (buffer.str() != "0\n-1 -8321648 1 42387\n") cerr << "failed fastprint" << FAIL; + cerr << "done" << endl; +} + diff --git a/test/other/fastIO.in b/test/other/fastIO.in new file mode 100644 index 0000000..45594a4 --- /dev/null +++ b/test/other/fastIO.in @@ -0,0 +1,2 @@ +4 7 +3 6 9 \ No newline at end of file diff --git a/test/other/josephus2.cpp b/test/other/josephus2.cpp new file mode 100644 index 0000000..d28fe0d --- /dev/null +++ b/test/other/josephus2.cpp @@ -0,0 +1,42 @@ +#include "../util.h" +#include + +template +ll naive(ll n, ll k) { + vector state(n); + iota(all(state), O); + for (ll i = k-1; state.size() > 1; i = (i + k - 1) % sz(state)) { + state.erase(state.begin() + i); + } + return state[0]; +} + +void stress_test() { + ll tests = 0; + for (ll i = 1; i < 2'000; i++) { + auto got = rotateLeft(i); + auto expected = naive<1>(i, 2); + if (got != expected) cerr << "error: " << i << FAIL; + tests++; + } + cerr << "tested queries: " << tests << endl; +} + +constexpr int N = 1'000'000'000; +void performance_test() { + timer t; + hash_t hash = 0; + t.start(); + for (ll i = 0; i < N; i++) { + hash += rotateLeft(1'000'000'000'000'000'000ll + i); + } + t.stop(); + if (t.time > 500) 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/josephusK.cpp b/test/other/josephusK.cpp new file mode 100644 index 0000000..e837640 --- /dev/null +++ b/test/other/josephusK.cpp @@ -0,0 +1,43 @@ +#include "../util.h" +#include +#include + +template +ll naive(ll n, ll k) { + vector state(n); + iota(all(state), O); + for (ll i = k-1; state.size() > 1; i = (i + k - 1) % sz(state)) { + state.erase(state.begin() + i); + } + return state[0]; +} + +void stress_test() { + ll tests = 0; + for (ll i = 1; i < 500; i++) { + for (ll j = 1; j <= i; j++) { + auto got = josephus(i, j); + auto expected = naive<0>(i, j); + if (got != expected) cerr << "error: " << i << FAIL; + tests++; + } + } + cerr << "tested queries: " << tests << endl; +} + +constexpr int N = 10'000'000; +void performance_test() { + timer t; + hash_t hash = 0; + t.start(); + hash += josephus(N, N/2); + t.stop(); + if (t.time > 500) 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/knuth.cpp b/test/other/knuth.cpp new file mode 100644 index 0000000..d469ceb --- /dev/null +++ b/test/other/knuth.cpp @@ -0,0 +1,103 @@ +#include "../util.h" +constexpr ll inf = LL::INF; +#include + +vector> gen(int n) { + vector> res(n, vector(n)); + ll mi = 0; + for (ll a = n-1; a >= 0; a--) { + for (ll c = n-1; c >= a; c--) { + for (ll b = a; b <= c; b++) { + for (ll d = c; d < n; d++) { + res[a][c] = min(res[a][c], res[a][d] + res[b][c] - res[b][d]); + } + } + res[a][c] -= Random::integer(0, 1000); + mi = min(mi, res[a][c]); + } + } + for (auto& v : res) for (auto& x : v) x -= mi; + + for (ll a = 0; a < n; a++) { + for (ll b = a; b < n; b++) { + for (ll c = b; c < n; c++) { + for (ll d = c; d < n; d++) { + if (res[a][d] < 0 || res[a][d] + res[b][c] < res[a][c] + res[b][d]) { + cerr << "invalid C array!" << FAIL; + } + } + } + } + } + return res; +} + +vector> genQuick(int n) { + vector> res(n, vector(n)); + for (ll a = n-1; a >= 0; a--) { + for (ll c = n-1; c >= a; c--) { + res[a][c] = (c-a) * (c - a) + Random::integer(0, 2); + } + } + return res; +} + +/*ll naive(int n, int m, const vector>& C) { + vector> state(m+1, vector(n+1, inf)); + state[0][0] = 0; + for (int i = 1; i <= m; i++) { + for (int j = 1; j <= n; j++) { + for (int k = 1; k <= j; k++) { + state[i][j] = min(state[i][j], state[i-1][k-1] + C[k-1][j-1]); + } + } + } + return state[m][n]; +}*/ + +vector naive(int n, const vector>& C) { + vector> state(n+1, vector(n+1, inf)); + state[0][0] = 0; + vector 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++) { + state[i][j] = min(state[i][j], state[i-1][k-1] + C[k-1][j-1]); + } + } + res[i] = state[i][n]; + } + return res; +} + +void stress_test() { + ll tests = 0; + for (ll i = 0; i < 1000; i++) { + auto n = Random::integer(10, 20); + auto C = gen(n); + auto expected = naive(n, C); + for (ll m = 1; m <= n; m++) { + auto got = calc(n, m, C); + if (got != expected[m]) cerr << "got: " << got << ", expected: " << expected[m] << FAIL; + tests++; + } + } + cerr << "tested random queries: " << tests << endl; +} + +constexpr int N = 5000; +void performance_test() { + timer t; + auto C = genQuick(N); + t.start(); + auto hash = calc(N, N/2, C); + t.stop(); + if (t.time > 500) 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/sos.cpp b/test/other/sos.cpp new file mode 100644 index 0000000..f3a6109 --- /dev/null +++ b/test/other/sos.cpp @@ -0,0 +1,50 @@ +#include "../util.h" + +vector sos(const vector& in) { + #include + return res; +} + +vector naive(const vector& in) { + vector res(sz(in)); + for (ll i = 0; i < sz(in); i++) { + for (ll j = 0; j <= i; j++) { + if ((i | j) == i) { + res[i] += in[j]; + } + } + } + return res; +} + +void stress_test() { + ll tests = 0; + for (ll i = 0; i < 1000; i++) { + int n = Random::integer(1, 100); + auto in = Random::integers(n, -1000, 1000); + auto got = sos(in); + auto expected = naive(in); + if (got != expected) cerr << "error: " << i << FAIL; + tests += n; + } + cerr << "tested random queries: " << tests << endl; +} + +constexpr int N = 10'000'000; +void performance_test() { + timer t; + auto in = Random::integers(N, -1000, 1000); + t.start(); + auto res = sos(in); + t.stop(); + hash_t hash = 0; + for (ll x : res) hash += x; + if (t.time > 500) 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/split.cpp b/test/other/split.cpp new file mode 100644 index 0000000..e0f5ee1 --- /dev/null +++ b/test/other/split.cpp @@ -0,0 +1,24 @@ +#include "../util.h" +#include + +vector split2(string_view s, string_view delim) { + vector res; + while (!s.empty()) { + auto end = s.find_first_of(delim); + if (end != 0) res.emplace_back(s.substr(0, end)); + if (end == string_view::npos) break; + s.remove_prefix(end + 1); + } + return res; +} + +int main() { + auto in = "+" + Random::string(100, "abcdef+-*") + "-"; + + auto expected = split2(in, "+-*"); + auto got = split(in, "+-*"); + + if (got != expected) cerr << "error" << FAIL; + cerr << "done" << endl; +} + diff --git a/test/string/ahoCorasick.cpp b/test/string/ahoCorasick.cpp new file mode 100644 index 0000000..c3361d6 --- /dev/null +++ b/test/string/ahoCorasick.cpp @@ -0,0 +1,76 @@ +#include "../util.h" +#include + +vector naive(string s, vector patterns) { + vector ans(patterns.size()); + for (int k = 0; k < (int)patterns.size(); k++) { + string pattern = patterns[k]; + for (int i = 0; i + pattern.size() <= s.size(); i++) { + if (s.substr(i, pattern.size()) == pattern) ans[k]++; + } + } + return ans; +} + +vector normal(string s, vector patterns) { + AhoCorasick aho; + vector ind(patterns.size()); + for (int i = 0; i < (int)patterns.size(); i++) { + ind[i] = aho.addString(patterns[i]); + } + aho.buildGraph(); + + int v = 0; + for (char c : s) v = aho.go(v, c - OFFSET), aho.dp[v]++; + aho.dfs(); + vector ans(patterns.size()); + for (int i = 0; i < (int)patterns.size(); i++) { + ans[i] = aho.dp[ind[i]]; + } + return ans; +} + +void stress_test() { + ll queries = 0; + for (int i = 0; i < 100; i++) { + int n = Random::integer(1, 100); + string s = Random::string(n, "abc"); + int m = Random::integer(1, 100); + vector patterns(m); + for (string& e : patterns) { + int k = Random::integer(1, 100); + e = Random::string(k, "abc"); + } + + auto got = normal(s, patterns); + auto expected = naive(s, patterns); + if (got != expected) cerr << "Wrong Answer" << FAIL; + queries++; + } + cerr << "Tested random queries: " << queries << endl; +} + +constexpr int N = 1'000'000; +void performance_test() { + timer t; + string s = string(N, 'a') + Random::string(N, "ab"); + vector patterns = {"a"}; + for (int sm = 1; sm < N; sm += patterns.back().size()) { + patterns.emplace_back(patterns.back().size()+1, 'a'); + } + for (int i = 0; i < 100; i++) { + patterns.emplace_back(Random::string(N/100, "ab")); + } + + t.start(); + hash_t hash = normal(s, patterns)[0]; + t.stop(); + + if (t.time > 500) cerr << "Too slow: " << t.time << FAIL; + cerr << "Tested performance: " << t.time << "ms (hash: hash " << hash << ")" << endl; +} + +int main() { + stress_test(); + performance_test(); +} diff --git a/test/string/deBruijn.cpp b/test/string/deBruijn.cpp new file mode 100644 index 0000000..6b3fea4 --- /dev/null +++ b/test/string/deBruijn.cpp @@ -0,0 +1,43 @@ +#include "../util.h" +#include +#include + +bool isDeBruijn(string s, int n, int k) { + ll expected = 1; + for (ll i = 0; i < n; i++) expected *= k; + if (expected != sz(s)) return false; + s += s; + set seen; + for (ll i = 0; 2*i < sz(s); i++) { + seen.insert(string_view(s).substr(i, n)); + } + return sz(seen) == expected; +} + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 1000; i++) { + int n = Random::integer(1, 9); + auto [l, r] = Random::pair('b', 'f'); + auto got = deBruijn(n, l, r); + if (!isDeBruijn(got, n, r - l + 1)) cerr << "error" << FAIL; + queries += sz(got); + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 26; +void performance_test() { + timer t; + t.start(); + auto res = deBruijn(N, '0', '1'); + t.stop(); + hash_t hash = sz(res); + if (t.time > 500) 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/string/duval.cpp b/test/string/duval.cpp new file mode 100644 index 0000000..58b4a44 --- /dev/null +++ b/test/string/duval.cpp @@ -0,0 +1,85 @@ +#include "../util.h" +#pragma GCC diagnostic ignored "-Wreturn-type" +#include + +constexpr int N = 20'000'000; + +bool isLyndon(string_view s) { + string t = string(s) + string(s); + for (ll i = 1; i < sz(s); i++) { + if (s >= t.substr(i, sz(s))) return false; + } + return !s.empty(); +} + +void stress_test_duval() { + ll queries = 0; + for (int i = 0; i < 10'000; i++) { + int n = Random::integer(1, 100); + auto s = Random::string(n, "abc"); + vector> got = duval(s); + if (got.empty()) cerr << "error: a" << FAIL; + if (got.front().first != 0) cerr << "error: b" << FAIL; + if (got.back().second != n) cerr << "error: c" << FAIL; + for (int j = 1; j < sz(got); j++) { + if (got[j - 1].second != got[j].first) cerr << "error: d" << FAIL; + } + for (auto [l, r] : got) { + if (!isLyndon(string_view(s).substr(l, r-l))) cerr << "error: e" << FAIL; + } + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +void performance_test_duval() { + timer t; + auto s = Random::string(N, "a") + Random::string(N, "ab") + Random::string(N, "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789$#"); + t.start(); + auto got = duval(s); + t.stop(); + hash_t hash = 0; + for (auto [l, r] : got) hash += l + r; + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int naive(string s) { + ll n = sz(s); + s += s; + int res = 0; + for (int i = 0; i < n; i++) { + if (string_view(s).substr(i, n) <= string_view(s).substr(res, n)) res = i; + } + return res; +} + +void stress_test_minrotation() { + ll queries = 0; + for (int i = 0; i < 10'000; i++) { + int n = Random::integer(1, 100); + auto s = Random::string(n, "abc"); + int got = minrotation(s); + auto expected = naive(s); + if (got != expected) cerr << s << ": got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +void performance_test_minrotation() { + timer t; + auto s = Random::string(N, "a") + Random::string(N, "ab") + Random::string(N, "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789$#"); + t.start(); + hash_t hash = minrotation(s); + t.stop(); + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + stress_test_duval(); + performance_test_duval(); + stress_test_minrotation(); + performance_test_minrotation(); +} diff --git a/test/string/kmp.cpp b/test/string/kmp.cpp new file mode 100644 index 0000000..9c9c924 --- /dev/null +++ b/test/string/kmp.cpp @@ -0,0 +1,85 @@ +#include "../util.h" +#include + +vector naive(string_view s) { + vector res(sz(s) + 1, -1); + for (int i = 0; i < sz(s); i++) { + for (int j = 0; j <= i; j++) + if (s.substr(0, j) == s.substr(i-j+1, j)) + res[i+1] = j; + } + return res; +} + +void stress_test_preprocessing() { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer(1, 15); + auto s = Random::string(n, "abc"); + auto got = kmpPreprocessing(s); + auto expected = naive(s); + if (got != expected) cerr << " error" << FAIL; + queries += n; + } + cerr << " tested random queries: " << queries << endl; +} + +constexpr int N = 10'000'000; +void performance_test_preprocessing() { + timer t; + auto s = Random::string(N, "a") + Random::string(N, "ab") + Random::string(N, "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789$#"); + t.start(); + auto res = kmpPreprocessing(s); + t.stop(); + hash_t hash = 0; + for (int x : res) hash += x; + if (t.time > 500) cerr << " too slow: " << t.time << FAIL; + cerr << " tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +vector naive(string_view s, string_view sub) { + vector res; + auto pos = s.find(sub); + while (pos != string_view::npos) { + res.push_back(pos); + pos = s.find(sub, pos + 1); + } + return res; +} + +void stress_test_kmp() { + ll queries = 0; + auto a = Random::string(10'000, "abc"); + for (int tries = 0; tries < 10'000; tries++) { + int n = Random::integer(1, 10); + auto b = Random::string(n, "abc"); + auto got = kmpSearch(a, b); + auto expected = naive(a, b); + if (got != expected) cerr << " error" << FAIL; + queries += got.size(); + } + cerr << " tested random queries: " << queries << endl; +} + +void performance_test_kmp() { + timer t; + auto s = Random::string(N, "a") + Random::string(N, "ab") + Random::string(N, "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789$#"); + auto sub1 = Random::string(N/2, "a"); + auto sub2 = Random::string(N/2, "ab"); + hash_t hash = 0; + t.start(); + hash += kmpSearch(s, sub1).size(); + hash += kmpSearch(s, sub2).size(); + t.stop(); + if (t.time > 500) cerr << " too slow: " << t.time << FAIL; + cerr << " tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + cerr << "preprocessing:" << endl; + stress_test_preprocessing(); + performance_test_preprocessing(); + cerr << "kmp:" << endl; + stress_test_kmp(); + performance_test_kmp(); +} diff --git a/test/string/longestCommonSubsequence.cpp b/test/string/longestCommonSubsequence.cpp new file mode 100644 index 0000000..6d7a6c5 --- /dev/null +++ b/test/string/longestCommonSubsequence.cpp @@ -0,0 +1,55 @@ +#include "../util.h" +#include + +bool isSubstr(string_view s, string_view sub) { + int i = 0; + for (char c : s) { + if (i < sz(sub) && c == sub[i]) i++; + } + return i >= sz(sub); +} + +string naive(string_view s, string_view t) { + string res = ""; + for (ll i = 1; i < (1ll << sz(s)); i++) { + string tmp; + for (ll j = 0; j < sz(s); j++) { + if (((i >> j) & 1) != 0) tmp.push_back(s[j]); + } + if (sz(tmp) >= sz(res) && isSubstr(t, tmp)) res = tmp; + } + return res; +} + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int n = Random::integer(1, 12); + int m = Random::integer(1, 12); + auto s = Random::string(n, "abc"); + auto t = Random::string(m, "abc"); + auto got = lcss(s, t); + auto expected = naive(s, t); + if (got != expected) cerr << s << ", " << t << ", got: " << got << ", expected: " << expected << FAIL; + queries += n + m; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 2'000; +void performance_test() { + timer t; + auto a = Random::string(N, "a") + Random::string(N, "ab") + Random::string(N, "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789$#"); + auto b = Random::string(N, "a") + Random::string(N, "ab") + Random::string(N, "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789$#"); + t.start(); + auto res = lcss(a, b); + t.stop(); + hash_t hash = sz(res); + if (t.time > 500) 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/string/lyndon.cpp b/test/string/lyndon.cpp new file mode 100644 index 0000000..ecf2dad --- /dev/null +++ b/test/string/lyndon.cpp @@ -0,0 +1,61 @@ +#include "../util.h" +#include + +bool isLyndon(string_view s) { + string t = string(s) + string(s); + for (ll i = 1; i < sz(s); i++) { + if (s >= t.substr(i, sz(s))) return false; + } + return !s.empty(); +} + +vector naive(ll n, char mi, char ma) { + vector res; + auto dfs = [&](auto&& self, string pref)->void{ + if (sz(pref) <= n && isLyndon(pref)) res.push_back(pref); + if (sz(pref) >= n) return; + for (char c = mi; c <= ma; c++) { + self(self, pref + c); + } + }; + dfs(dfs, ""); + return res; +} + +vector fast(ll n, char mi, char ma) { + vector res; + string tmp(1, mi); + do { + res.push_back(tmp); + } while (next(tmp, n, mi, ma)); + return res; +} + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int n = Random::integer(1, 6); + auto [l, r] = Random::pair('a', 'f'); + auto got = fast(n, l, r); + auto expected = naive(n, l, r); + if (got != expected) cerr << "error" << FAIL; + queries += sz(expected); + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 9; +void performance_test() { + timer t; + t.start(); + auto res = fast(N, 'a', 'f'); + t.stop(); + hash_t hash = sz(res); + if (t.time > 500) 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/string/manacher.cpp b/test/string/manacher.cpp new file mode 100644 index 0000000..503d181 --- /dev/null +++ b/test/string/manacher.cpp @@ -0,0 +1,49 @@ +#include "../util.h" +#include + +vector naive(string_view s) { + vector res(2 * sz(s) + 1); + for (int i = 0; i < sz(s); i++) { //odd palindromes + int j = 2*i+1; + while (i+res[j] < sz(s) && i-res[j] >= 0 && s[i-res[j]] == s[i+res[j]]) res[j]++; + res[j]*=2; + res[j]--; + } + for (int i = 0; i <= sz(s); i++) { //even palindromes + int j = 2*i; + while (i+res[j] < sz(s) && i-res[j]-1 >= 0 && s[i-res[j]-1] == s[i+res[j]]) res[j]++; + res[j] *= 2; + } + return res; +} + +void stress_test() { + ll queries = 0; + for (int i = 0; i < 10'000; i++) { + int n = Random::integer(1, 100); + auto s = Random::string(n, "abc"); + vector got = manacher(s); + vector expected = naive(s); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 5'000'000; +void performance_test() { + timer t; + auto s = Random::string(N, "a") + Random::string(N, "ab") + Random::string(N, "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789$#"); + t.start(); + auto got = manacher(s); + t.stop(); + hash_t hash = 0; + for (int x : got) hash += x; + if (t.time > 500) 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/string/rollingHash.cpp b/test/string/rollingHash.cpp new file mode 100644 index 0000000..0491bc0 --- /dev/null +++ b/test/string/rollingHash.cpp @@ -0,0 +1,92 @@ +#include "../util.h" +#include + +string thueMorse(ll n) { + string res = "a"; + while (sz(res) < n) { + string tmp = res; + for (char& c : tmp) c ^= 1; + res += tmp; + } + return res; +} + +auto getHash(const string& s) { + return Hash(s)(0, sz(s)); +} + +void testThueMorse() { + set got; + set expected; + string s = thueMorse(1000); + Hash h(s); + for (int l = 0; l < sz(s); l++) { + for (int r = l + 1; r <= sz(s); r++) { + got.insert(h(l, r)); + expected.insert(s.substr(l, r - l)); + } + } + if (sz(got) != sz(expected)) cerr << "error: thueMorse" << FAIL; + cerr << "thueMorse: ok" << endl; +} + +void testTiny() { + if (getHash("aa") == getHash("a")) cerr << "error: tiny" << FAIL; + if (getHash("00") == getHash("0")) cerr << "error: tiny" << FAIL; + if (getHash("AA") == getHash("A")) cerr << "error: tiny" << FAIL; + cerr << "tiny: ok" << endl; +} + +void testSmall() { + set got; + ll expected = 0; + auto dfs = [&](auto&& self, string pref)->void { + expected++; + got.insert(getHash(pref)); + if(sz(pref) >= 5) return; + for (char c = 'a'; c <= 'z'; c++) { + self(self, pref + c); + } + }; + dfs(dfs, ""); + if (sz(got) != expected) cerr << "error: small" << FAIL; + cerr << "small: ok" << endl; +} + +void stress_test() { + set got; + set expected; + string s = Random::string(1000, "abc"); + Hash h(s); + for (int l = 0; l < sz(s); l++) { + for (int r = l + 1; r <= sz(s); r++) { + got.insert(h(l, r)); + expected.insert(s.substr(l, r - l)); + } + } + if (sz(got) != sz(expected)) cerr << "error: stress test" << FAIL; + cerr << "stress test: ok" << endl; +} + +constexpr int N = 1'000'000; +void performance_test() { + timer t; + auto s = Random::string(N, "a") + Random::string(N, "ab") + Random::string(N, "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789$#"); + hash_t hash = 0; + t.start(); + Hash h(s); + for (ll i = 0; i < N; i++) { + hash += h(i, i + 2*N); + } + t.stop(); + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + testThueMorse(); + testTiny(); + testSmall(); + stress_test(); + performance_test(); +} diff --git a/test/string/rollingHashCf.cpp b/test/string/rollingHashCf.cpp new file mode 100644 index 0000000..79003de --- /dev/null +++ b/test/string/rollingHashCf.cpp @@ -0,0 +1,94 @@ +#include "../util.h" +#include + +constexpr ll RandomQ = 318LL << 53; + +string thueMorse(ll n) { + string res = "a"; + while (sz(res) < n) { + string tmp = res; + for (char& c : tmp) c ^= 1; + res += tmp; + } + return res; +} + +auto getHash(const string& s) { + return Hash(s, RandomQ)(0, sz(s)); +} + +void testThueMorse() { + set got; + set expected; + string s = thueMorse(1000); + Hash h(s, RandomQ); + for (int l = 0; l < sz(s); l++) { + for (int r = l + 1; r <= sz(s); r++) { + got.insert(h(l, r)); + expected.insert(s.substr(l, r - l)); + } + } + if (sz(got) != sz(expected)) cerr << "error: thueMorse" << FAIL; + cerr << "thueMorse: ok" << endl; +} + +void testTiny() { + if (getHash("aa") == getHash("a")) cerr << "error: tiny" << FAIL; + if (getHash("00") == getHash("0")) cerr << "error: tiny" << FAIL; + if (getHash("AA") == getHash("A")) cerr << "error: tiny" << FAIL; + cerr << "tiny: ok" << endl; +} + +void testSmall() { + set got; + ll expected = 0; + auto dfs = [&](auto&& self, string pref)->void { + expected++; + got.insert(getHash(pref)); + if(sz(pref) >= 5) return; + for (char c = 'a'; c <= 'z'; c++) { + self(self, pref + c); + } + }; + dfs(dfs, ""); + if (sz(got) != expected) cerr << "error: small" << FAIL; + cerr << "small: ok" << endl; +} + +void stress_test() { + set got; + set expected; + string s = Random::string(1000, "abc"); + Hash h(s, RandomQ); + for (int l = 0; l < sz(s); l++) { + for (int r = l + 1; r <= sz(s); r++) { + got.insert(h(l, r)); + expected.insert(s.substr(l, r - l)); + } + } + if (sz(got) != sz(expected)) cerr << "error: stress test" << FAIL; + cerr << "stress test: ok" << endl; +} + +constexpr int N = 1'000'000; +void performance_test() { + timer t; + auto s = Random::string(N, "a") + Random::string(N, "ab") + Random::string(N, "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789$#"); + hash_t hash = 0; + t.start(); + Hash h(s, RandomQ); + for (ll i = 0; i < N; i++) { + hash += h(i, i + 2*N); + } + t.stop(); + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + testThueMorse(); + testTiny(); + testSmall(); + stress_test(); + performance_test(); +} diff --git a/test/string/suffixArray.cpp b/test/string/suffixArray.cpp new file mode 100644 index 0000000..4945d8e --- /dev/null +++ b/test/string/suffixArray.cpp @@ -0,0 +1,61 @@ +#include "../util.h" +#include + +vector naive(string_view s) { + vector SA(sz(s)); + iota(all(SA), 0); + sort(all(SA), [s](int a, int b){ + return s.substr(a) < s.substr(b); + }); + return SA; +} + +int lcp(string_view s, int x, int y) { + int res = 0; + while (x + res < sz(s) && y + res < sz(s) && s[x + res] == s[y + res]) res++; + return res; +} + +void stress_test() { + ll queries = 0; + for (int i = 0; i < 100; i++) { + int n = Random::integer(1, 100); + auto s = Random::string(n, "abc"); + SuffixArray sa(s); + vector got = sa.SA; + vector expected = naive(s); + vector SA(n); + if (got != expected) cerr << "error: SA" << FAIL; + got = sa.LCP; + swap(SA, expected); + for (int x = 0; x < n; x++) { + for (int y = 0; y < n; y++) { + int gotLCP = sa.lcp(x, y); + int expectedLCP = lcp(s, x, y); + if (gotLCP != expectedLCP) cerr << "error: lcp" << FAIL; + } + if (x > 0) expected[x] = lcp(s, SA[x-1], SA[x]); + } + if (got != expected) cerr << "error: LCP" << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 200'000; +void performance_test() { + timer t; + auto s = Random::string(N, "a") + Random::string(N, "ab") + Random::string(N, "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789$#"); + t.start(); + SuffixArray sa(s); + t.stop(); + hash_t hash = 0; + for (int i = 0; i < sz(sa.SA); i++) hash += i*sa.SA[i]; + if (t.time > 500) 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/string/suffixAutomaton.cpp b/test/string/suffixAutomaton.cpp new file mode 100644 index 0000000..c2ff511 --- /dev/null +++ b/test/string/suffixAutomaton.cpp @@ -0,0 +1,62 @@ +#include "../util.h" +#include + +pair naive(string_view s, string_view t) { + int pos = 0; + int len = 0; + for (int j = 0; j < sz(t); j++) { + for (int i = 0; i < sz(s); i++) { + int cur = 0; + while (i+cur < sz(s) && j+cur < sz(t) && s[i+cur] == t[j+cur]) cur++; + if (cur > len) { + pos = j; + len = cur; + } + } + } + return {pos, len}; +} + +void stress_test() { + ll queries = 0; + for (int i = 0; i < 1000; i++) { + int n = Random::integer(1, 100); + auto s = Random::string(n, "abc"); + SuffixAutomaton sa(s); + for (int j = 0; j < 1000; j++) { + int m = Random::integer(1, 100); + auto t = Random::string(m, "abc"); + auto got = sa.longestCommonSubstring(t); + auto expected = naive(s, t); + if (got != expected) cerr << "error" << FAIL; + queries += m; + } + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 500'000; +void performance_test() { + timer t; + auto s = Random::string(N, "a") + Random::string(N, "ab") + Random::string(N, "abcdefghijklmnopqrstuvwxyz"); + t.start(); + SuffixAutomaton sa(s); + t.stop(); + hash_t hash = 0; + for (ll c = 0; c < sz(s);) { + int m = Random::integer(1, 1000); + s = Random::string(m, "abc"); + t.start(); + auto [p, l] = sa.longestCommonSubstring(s); + t.stop(); + hash += l + p; + c += m; + } + if (t.time > 500) 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/string/suffixTree.cpp b/test/string/suffixTree.cpp new file mode 100644 index 0000000..c0d79e4 --- /dev/null +++ b/test/string/suffixTree.cpp @@ -0,0 +1,50 @@ +#include "../util.h" +#include + +vector naive(string_view s) { + vector res(sz(s)); + for (ll i = 0; i < sz(s); i++) { + res[i] = s.substr(i); + } + return res; +} + +void stress_test() { + ll queries = 0; + for (int i = 0; i < 10'000; i++) { + int n = Random::integer(1, 15); + auto s = Random::string(n, "abc") + "#"; + SuffixTree st(s); + vector got(n + 1); + auto dfs = [&](auto&& self, string pref, ll node) -> void { + auto& [l, r, _, next] = st.tree[node]; + if (l >= 0) pref += s.substr(l, r - l); + if (pref.back() == '#') got[n + 1 - sz(pref)] = pref; + for (auto [__, j] : next) { + self(self, pref, j); + } + }; + dfs(dfs, "", 0); + auto expected = naive(s); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 200'000; +void performance_test() { + timer t; + auto s = Random::string(N, "a") + Random::string(N, "ab") + Random::string(N, "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789$#"); + t.start(); + SuffixTree st(s); + t.stop(); + hash_t hash = sz(st.tree); + if (t.time > 500) 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/string/trie.cpp b/test/string/trie.cpp new file mode 100644 index 0000000..45d89cf --- /dev/null +++ b/test/string/trie.cpp @@ -0,0 +1,58 @@ +#include "../util.h" +#include + +void stress_test() { + multiset> naive; + ll queries = 0; + ll deleted = 0; + for (int tries = 0; tries < 100'000; tries++) { + { + int n = Random::integer(1, 20); + auto s = Random::integers(n, 0, 2); + insert(s); + naive.insert(s); + } + { + int n = Random::integer(1, 20); + auto s = Random::integers(n, 0, 2); + bool got = erase(s); + auto it = naive.find(s); + bool expected = it != naive.end(); + if (expected) naive.erase(it); + if (got != expected) cerr << "error" << FAIL; + queries++; + if (got) deleted++; + } + } + cerr << "tested random queries: " << queries << " (" << deleted << ")" << endl; +} + +constexpr int N = 10'000; +void performance_test() { + timer t; + trie = {node()}; + hash_t hash = 0; + for (int tries = 0; tries < N; tries++) { + { + int n = Random::integer(1, 2000); + auto s = Random::integers(n, 0, 2); + t.start(); + insert(s); + t.stop(); + } + { + int n = Random::integer(1, 2000); + auto s = Random::integers(n, 0, 2); + t.start(); + hash += erase(s); + t.stop(); + } + } + if (t.time > 500) 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/string/z.cpp b/test/string/z.cpp new file mode 100644 index 0000000..f890a3e --- /dev/null +++ b/test/string/z.cpp @@ -0,0 +1,41 @@ +#include "../util.h" +#include + +vector naive(const string& s) { + vector res(sz(s)); + for (int i = 1; i < sz(s); i++) { + while (i + res[i] < sz(s) && s[res[i]] == s[i + res[i]]) res[i]++; + } + return res; +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer(1, 15); + auto s = Random::string(n, "abc"); + auto got = Z(s); + auto expected = naive(s); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 10'000'000; +void performance_test() { + timer t; + auto s = Random::string(N, "a") + Random::string(N, "ab") + Random::string(N, "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789$#"); + t.start(); + auto res = Z(s); + t.stop(); + hash_t hash = 0; + for (int x : res) hash += x; + if (t.time > 500) 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/template/template.cpp b/test/template/template.cpp new file mode 100644 index 0000000..db9aa00 --- /dev/null +++ b/test/template/template.cpp @@ -0,0 +1 @@ +#include