Merging tables done!

Another interesting problem to solve. I gained a much better understanding
of disjoint sets (aka Union/Find) through the coding challenge. A few takeaways:
1. Writing test cases is so important. I can sink my teeth into it and
have something concrete to work on, instead of wasting time beating around the bush;
2. Modify starter code to make it testable, if it's not easy to test to
begin with;
3. Get started early, so I can use my "sleep on it" technique. It really
improves understanding!
4. I'm slightly bothered by the fact that I don't have a test case to catch
the issue with grader test case 8. I looked at the code and added line 61
which enabled me to pass the grader.

2 files changed, 222 insertions, 0 deletions

diff --git a/src/main/MergingTables.java b/src/main/MergingTables.java
new file mode 100644
index 0000000..bf0e337
--- /dev/null
+++ b/src/main/MergingTables.java
@@ -0,0 +1,139 @@
+import java.io.BufferedReader;
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.InputStreamReader;
+import java.io.OutputStream;
+import java.io.PrintWriter;
+import java.util.Locale;
+import java.util.StringTokenizer;
+
+public class MergingTables {
+    private final InputReader reader;
+    private final OutputWriter writer;
+
+    int maximumNumberOfRows = -1;
+    int[] parent;
+    int[] rank;
+    Table[] tables;
+
+    MergingTables(InputReader reader, OutputWriter writer) {
+        this.reader = reader;
+        this.writer = writer;
+    }
+
+    public static void main(String[] args) {
+        InputReader reader = new InputReader(System.in);
+        OutputWriter writer = new OutputWriter(System.out);
+        new MergingTables(reader, writer).run();
+        writer.writer.flush();
+    }
+
+    static class Table {
+        Table setID;
+        int numberOfRows;
+
+        Table(int numberOfRows) {
+            this.numberOfRows = numberOfRows;
+            setID = this;
+        }
+
+    }
+
+    private int find(int i) {
+        if (i != parent[i])
+            parent[i] = find(parent[i]);
+        return parent[i];
+    }
+
+    void merge(int destination, int source) {
+        Table realDestination = tables[find(destination)];
+        Table realSource = tables[find(source)];
+        if (realDestination == realSource) {
+            return;
+        }
+        maximumNumberOfRows = Math.max(maximumNumberOfRows, realDestination.setID.numberOfRows + realSource.setID.numberOfRows);
+        realDestination.numberOfRows = realDestination.setID.numberOfRows + realSource.setID.numberOfRows;
+        realSource.numberOfRows = 0;
+        realSource.setID = realDestination;
+        // The code below fixed the issue with test case 8 from the grader.
+        // My code then passed all tests. I'm slightly bothered that I don't
+        // have a test case to capture it.
+        realDestination.setID = realDestination;
+        union(destination, source);
+    }
+
+    private void union(int destination, int source) {
+        int destination_id = find(destination);
+        int source_id = find(source);
+        if (destination_id == source_id)
+            return;
+        if (rank[destination_id] > rank[source_id])
+            parent[source_id] = destination_id;
+        else {
+            parent[destination_id] = source_id;
+            if (rank[destination_id] == rank[source_id])
+                rank[source_id] = rank[source_id] + 1;
+        }
+    }
+
+    private void run() {
+        int n = reader.nextInt();
+        int m = reader.nextInt();
+        parent = new int[n];
+        rank = new int[n];
+        tables = new Table[n];
+        for (int i = 0; i < n; i++) {
+            int numberOfRows = reader.nextInt();
+            tables[i] = new Table(numberOfRows);
+            parent[i] = i;
+            rank[i] = 0;
+            maximumNumberOfRows = Math.max(maximumNumberOfRows, numberOfRows);
+        }
+        for (int i = 0; i < m; i++) {
+            int destination = reader.nextInt() - 1;
+            int source = reader.nextInt() - 1;
+            merge(destination, source);
+            writer.printf("%d\n", maximumNumberOfRows);
+        }
+    }
+
+
+    static class InputReader {
+        BufferedReader reader;
+        StringTokenizer tokenizer;
+
+        InputReader(InputStream stream) {
+            reader = new BufferedReader(new InputStreamReader(stream), 32768);
+            tokenizer = null;
+        }
+
+        String next() {
+            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
+                try {
+                    tokenizer = new StringTokenizer(reader.readLine());
+                } catch (IOException e) {
+                    throw new RuntimeException(e);
+                }
+            }
+            return tokenizer.nextToken();
+        }
+
+        int nextInt() {
+            return Integer.parseInt(next());
+        }
+
+    }
+
+    static class OutputWriter {
+        PrintWriter writer;
+
+        OutputWriter(OutputStream stream) {
+            writer = new PrintWriter(stream);
+        }
+
+        void printf(String format, Object... args) {
+            writer.print(String.format(Locale.ENGLISH, format, args));
+        }
+    }
+}
+
diff --git a/src/test/MergingTablesTest.java b/src/test/MergingTablesTest.java
new file mode 100644
index 0000000..fcb5829
--- /dev/null
+++ b/src/test/MergingTablesTest.java
@@ -0,0 +1,83 @@
+import org.junit.jupiter.api.Test;
+
+import java.io.*;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class MergingTablesTest {
+    @Test
+    void test() {
+        MergingTables.InputReader reader = new MergingTables.InputReader(System.in);
+        MergingTables.OutputWriter writer = new MergingTables.OutputWriter(System.out);
+        MergingTables mergingTables = new MergingTables(reader, writer);
+        mergingTables.tables = new MergingTables.Table[5];
+
+        MergingTables.Table t0 = new MergingTables.Table(1);
+        MergingTables.Table t1 = new MergingTables.Table(1);
+        MergingTables.Table t2 = new MergingTables.Table(1);
+        MergingTables.Table t3 = new MergingTables.Table(1);
+        MergingTables.Table t4 = new MergingTables.Table(1);
+
+        mergingTables.tables[0] = t0;
+        mergingTables.tables[1] = t1;
+        mergingTables.tables[2] = t2;
+        mergingTables.tables[3] = t3;
+        mergingTables.tables[4] = t4;
+        mergingTables.maximumNumberOfRows = 1;
+        mergingTables.rank = new int[]{0, 0, 0, 0, 0};
+        mergingTables.parent = new int[]{0, 1, 2, 3, 4};
+
+        mergingTables.merge(2, 4);
+        assertEquals(2, mergingTables.maximumNumberOfRows);
+
+        mergingTables.merge(1, 3);
+        assertEquals(2, mergingTables.maximumNumberOfRows);
+
+        mergingTables.merge(0, 3);
+        assertEquals(3, mergingTables.maximumNumberOfRows);
+
+        mergingTables.merge(4, 3);
+        assertEquals(5, mergingTables.maximumNumberOfRows);
+
+        mergingTables.merge(4, 2);
+        assertEquals(5, mergingTables.maximumNumberOfRows);
+    }
+
+    @Test
+    void test1() {
+        MergingTables.InputReader reader = new MergingTables.InputReader(System.in);
+        MergingTables.OutputWriter writer = new MergingTables.OutputWriter(System.out);
+        MergingTables mergingTables = new MergingTables(reader, writer);
+        mergingTables.tables = new MergingTables.Table[6];
+
+        MergingTables.Table t0 = new MergingTables.Table(10);
+        MergingTables.Table t1 = new MergingTables.Table(0);
+        MergingTables.Table t2 = new MergingTables.Table(5);
+        MergingTables.Table t3 = new MergingTables.Table(0);
+        MergingTables.Table t4 = new MergingTables.Table(3);
+        MergingTables.Table t5 = new MergingTables.Table(3);
+
+        mergingTables.tables[0] = t0;
+        mergingTables.tables[1] = t1;
+        mergingTables.tables[2] = t2;
+        mergingTables.tables[3] = t3;
+        mergingTables.tables[4] = t4;
+        mergingTables.tables[5] = t5;
+        mergingTables.maximumNumberOfRows = 10;
+        mergingTables.rank = new int[]{0, 0, 0, 0, 0, 0};
+        mergingTables.parent = new int[]{0, 1, 2, 3, 4, 5};
+
+        mergingTables.merge(5, 5);
+        assertEquals(10, mergingTables.maximumNumberOfRows);
+
+        mergingTables.merge(5, 4);
+        assertEquals(10, mergingTables.maximumNumberOfRows);
+
+        mergingTables.merge(4, 3);
+        assertEquals(10, mergingTables.maximumNumberOfRows);
+
+        mergingTables.merge(3, 2);
+        assertEquals(11, mergingTables.maximumNumberOfRows);
+    }
+
+}
\ No newline at end of file