summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2018-12-25 11:12:42 -0600
committerHaidong Ji2018-12-25 11:12:42 -0600
commit1c6c9657a6432fc1d7069ddf8dd106f7a614fbed (patch)
tree563c54d66a88a1878de02934c7aa5a33fed45379
parentc4ef43d3e77450b45bb7fb988bff0923ef8276fe (diff)
Longest Subsequence (betwee 2) done!
This one is pretty tricky. I solved it after reading online: http://www.cs.umd.edu/~meesh/351/mount/lectures/lect25-longest-common-subseq.pdf https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/ To find a good test case that reveals the bug, I tried stress testing (in commented out code), but the naive but correct algo is so inefficient that I didn't have enough patience to let it finish. Anyway, good practice of stress testing anyway.
-rw-r--r--AlgoDesignAndTechniqueEdxJava/sources/LCS2.java56
-rw-r--r--AlgoDesignAndTechniqueEdxJava/tests/LCS2Test.java52
2 files changed, 95 insertions, 13 deletions
diff --git a/AlgoDesignAndTechniqueEdxJava/sources/LCS2.java b/AlgoDesignAndTechniqueEdxJava/sources/LCS2.java
index d214eff..e2a882c 100644
--- a/AlgoDesignAndTechniqueEdxJava/sources/LCS2.java
+++ b/AlgoDesignAndTechniqueEdxJava/sources/LCS2.java
@@ -1,4 +1,6 @@
+import java.util.Arrays;
import java.util.Scanner;
+//import java.util.concurrent.ThreadLocalRandom;
public class LCS2 {
@@ -16,7 +18,33 @@ public class LCS2 {
b[i] = scanner.nextInt();
}
- System.out.println(lcs2(a, b));
+ System.out.println(third_lcs2(a, b));
+// System.out.println(alt_lcs2(a, b, n, m));
+
+// while (true) {
+//// int n = ThreadLocalRandom.current().nextInt(1, 101);
+//// int m = ThreadLocalRandom.current().nextInt(1, 101);
+// int n = ThreadLocalRandom.current().nextInt(1, 20);
+// int m = ThreadLocalRandom.current().nextInt(1, 20);
+// int[] a = new int[n];
+// int[] b = new int[m];
+// for (int i = 0; i < a.length; i++) {
+// a[i] = ThreadLocalRandom.current().nextInt(-999999999, 1000000000);
+// }
+// for (int i = 0; i < b.length; i++) {
+// b[i] = ThreadLocalRandom.current().nextInt(-999999999, 1000000000);
+// }
+// int r1 = lcs2(a, b);
+// int r2 = alt_lcs2(a, b, n, m);
+// if (r1 == r2)
+// System.out.println("ok");
+// else {
+// System.out.println(Arrays.toString(a));
+// System.out.println(Arrays.toString(b));
+// System.out.println("Wrong answer " + r1 + " " + r2);
+// break;
+// }
+// }
}
public static int[][] editDistance(int[] A, int[] B) {
@@ -66,4 +94,30 @@ public class LCS2 {
return lcs2(i - 1, j - 1, D);
}
+ public static int alt_lcs2(int[] a, int[] b, int i, int j) {
+ if (i == 0 || j == 0)
+ return 0;
+ if (a[i - 1] == b[j - 1])
+ return 1 + alt_lcs2(a, b, i - 1, j - 1);
+ else
+ return Math.max(alt_lcs2(a, b, i, j - 1), alt_lcs2(a, b, i - 1, j));
+ }
+
+ public static int third_lcs2(int[] a, int[] b) {
+ int m = b.length;
+ int n = a.length;
+ int[][] D = new int[n + 1][m + 1];
+ for (int j = 1; j < m + 1; j++) {
+ for (int i = 1; i < n + 1; i++) {
+ if (a[i - 1] == b[j - 1]) {
+ D[i][j] = D[i - 1][j - 1] + 1;
+ } else {
+ D[i][j] = Math.max(D[i - 1][j], D[i][j - 1]);
+ }
+ }
+ }
+
+ return D[n][m];
+ }
+
}
diff --git a/AlgoDesignAndTechniqueEdxJava/tests/LCS2Test.java b/AlgoDesignAndTechniqueEdxJava/tests/LCS2Test.java
index bdfa799..83de106 100644
--- a/AlgoDesignAndTechniqueEdxJava/tests/LCS2Test.java
+++ b/AlgoDesignAndTechniqueEdxJava/tests/LCS2Test.java
@@ -6,30 +6,58 @@ class LCS2Test {
@Test
void test() {
- int[] a = {2, 7, 5};
- int[] b = {2, 5};
- assertEquals(2, LCS2.lcs2(a,b));
+ int[] a = { 2, 7, 5 };
+ int[] b = { 2, 5 };
+ assertEquals(2, LCS2.lcs2(a, b));
+ assertEquals(2, LCS2.third_lcs2(a, b));
+ assertEquals(2, LCS2.alt_lcs2(a, b, 3, 2));
}
@Test
void test1() {
- int[] a = {7};
- int[] b = {1, 2, 3, 4};
- assertEquals(0, LCS2.lcs2(a,b));
+ int[] a = { 7 };
+ int[] b = { 1, 2, 3, 4 };
+ assertEquals(0, LCS2.lcs2(a, b));
+ assertEquals(0, LCS2.third_lcs2(a, b));
+ assertEquals(0, LCS2.alt_lcs2(a, b, 1, 4));
}
@Test
void test2() {
- int[] a = {2, 7, 8, 3};
- int[] b = {5, 2, 8, 7};
- assertEquals(2, LCS2.lcs2(a,b));
+ int[] a = { 2, 7, 8, 3 };
+ int[] b = { 5, 2, 8, 7 };
+ assertEquals(2, LCS2.lcs2(a, b));
+ assertEquals(2, LCS2.third_lcs2(a, b));
+ assertEquals(2, LCS2.alt_lcs2(a, b, 4, 4));
}
@Test
void test3() {
- int[] a = {1, 2, 3, 4, 5, 6, 7};
- int[] b = {1, 2, 8, 4, 5, 6};
- assertEquals(5, LCS2.lcs2(a,b));
+ int[] a = { 1, 2, 3, 4, 5, 6, 7 };
+ int[] b = { 1, 2, 8, 4, 5, 6 };
+ assertEquals(5, LCS2.lcs2(a, b));
+ assertEquals(5, LCS2.third_lcs2(a, b));
+ assertEquals(5, LCS2.alt_lcs2(a, b, 7, 6));
+ }
+
+ @Test
+ void test4() {
+ int[] a = { 1, 9, 2, 5, 5, 5, 8, 3, 5, 11, 0, 2, 4, 1, 7, 4, 5, 9, 2, 4, 0, 3, 1, 5, 8, 3, 5, 9, 7, 8, 4, 5, 6,
+ 7 };
+ int[] b = { 6, 3, 8, 3, 1, 8, 3, 5, 0, 9, 6, 8, 3, 5, 7, 9, 1, 4, 7, 9, 3, 5, 9, 0, 1, 4, 2, 7, 5, 8, 9, 3, 5,
+ 6, 1, 6, 3, 1, 6, 7, 3 };
+ assertEquals(16, LCS2.lcs2(a, b));
+ assertEquals(17, LCS2.third_lcs2(a, b));
+// assertEquals(5, LCS2.alt_lcs2(a, b, a.length, b.length));
+ }
+
+ @Test
+ void test5() {
+ int[] a = { 2, 4, 3, 3 };
+ int[] b = { 1, 4, 3 };
+ assertEquals(2, LCS2.lcs2(a, b));
+ assertEquals(2, LCS2.third_lcs2(a, b));
+// assertEquals(5, LCS2.alt_lcs2(a, b, a.length, b.length));
}
}