Algorithms-I : 3-Collinear: first submission, Fast is slow ;)

6 files changed, 395 insertions, 0 deletions

diff --git a/Algorithms/Part-I/3-Collinear/Brute.java b/Algorithms/Part-I/3-Collinear/Brute.java
new file mode 100644
index 0000000..d7eb052
--- /dev/null
+++ b/Algorithms/Part-I/3-Collinear/Brute.java
@@ -0,0 +1,92 @@
+/* vim: set expandtab tabstop=4 shiftwidth=4 : */
+
+import java.util.List;
+import java.util.ArrayList;
+
+public class Brute
+{
+
+    public static void main(String[] args)
+    {
+        class Solution implements Comparable<Solution>
+        {
+            private Point[] pts = new Point[4];
+
+            public Solution(Point p, Point q, Point r, Point s)
+            {
+                pts[0] = p;
+                pts[1] = q;
+                pts[2] = r;
+                pts[3] = s;
+                Insertion.sort(pts);
+            }
+
+            public void draw()
+            {
+                pts[0].drawTo(pts[3]);
+            }
+
+            public void print()
+            {
+                System.out.println(pts[0]+" -> "+pts[1]+" -> "+pts[2]+" -> "+pts[3]);
+            }
+
+            public int compareTo(Solution that)
+            {
+                int r = pts[0].compareTo(that.pts[0]);
+                if (r != 0) return r;
+                r = pts[1].compareTo(that.pts[1]);
+                if (r != 0) return r;
+                r = pts[2].compareTo(that.pts[2]);
+                if (r != 0) return r;
+                return pts[3].compareTo(that.pts[3]);
+            }
+        }
+
+        In in = new In(args[0]);
+        int n = in.readInt();
+
+        StdDraw.setXscale(0, 32768);
+        StdDraw.setYscale(0, 32768);
+
+        Point[] pts = new Point[n];
+        for (int i = 0; i < n; i++)
+        {
+            Point p = new Point(in.readInt(), in.readInt());
+            pts[i] = p;
+            p.draw();
+        }
+
+        List<Solution> res = new ArrayList<Solution>();
+        for (int p = 0; p < n; p++)
+        {
+            for (int q = p+1; q < n; q++)
+            {
+                double sl = pts[p].slopeTo(pts[q]);
+                for (int r = q+1; r < n; r++)
+                {
+                    if (!(sl == pts[p].slopeTo(pts[r])))
+                        continue;
+                    for (int s = r+1; s < n; s++)
+                    {
+                        if (sl == pts[p].slopeTo(pts[s]))
+                        {
+                            res.add(new Solution(pts[p], pts[q], pts[r], pts[s]));
+                        }
+                    }
+                }
+            }
+        }
+
+        Solution[] sorted = new Solution[res.size()];
+        res.toArray(sorted);
+        Insertion.sort(sorted);
+        for (Solution sol : sorted)
+        {
+            sol.draw();
+            sol.print();
+        }
+        StdDraw.show(0);
+    }
+}
+
diff --git a/Algorithms/Part-I/3-Collinear/Fast.java b/Algorithms/Part-I/3-Collinear/Fast.java
new file mode 100644
index 0000000..2640d65
--- /dev/null
+++ b/Algorithms/Part-I/3-Collinear/Fast.java
@@ -0,0 +1,141 @@
+/* vim: set expandtab tabstop=4 shiftwidth=4 : */
+
+import java.util.List;
+import java.util.ArrayList;
+import java.util.Arrays;
+
+public class Fast
+{
+
+    public static void main(String[] args)
+    {
+        class Solution implements Comparable<Solution>
+        {
+            private Point[] pts;
+            private int n = 0;
+
+            public Solution(int n)
+            {
+                pts = new Point[n];
+            }
+
+            public void add(Point p)
+            {
+                pts[n++] = p;
+            }
+
+            public void sort()
+            {
+                Insertion.sort(pts);
+            }
+
+            public void draw()
+            {
+                pts[0].drawTo(pts[n - 1]);
+            }
+
+            public void print()
+            {
+                String out = "";
+                for (int i = 0; i < n; i++)
+                    out += pts[i]+" -> ";
+                System.out.println(out.substring(0, (out.length() - 4)));
+            }
+
+            public boolean equals(Object o)
+            {
+                if (o == this) return true;
+                if (o == null) return false;
+                if (o.getClass() != this.getClass()) return false;
+
+                Solution other = (Solution) o;
+                if (n != other.n) return false;
+
+                for (int i = 0; i < n; i++)
+                    if (pts[i] != other.pts[i])
+                        return false;
+                return true;
+
+            }
+
+            public int compareTo(Solution that)
+            {
+                for (int i = 0; i < n; i++)
+                {
+                    int r = pts[0].compareTo(that.pts[0]);
+                    if (r != 0) return r;
+                }
+                return 0;
+            }
+        }
+
+        In in = new In(args[0]);
+        int n = in.readInt();
+
+        StdDraw.setXscale(0, 32768);
+        StdDraw.setYscale(0, 32768);
+
+        Point[] pts = new Point[n];
+        for (int i = 0; i < n; i++)
+        {
+            pts[i] = new Point(in.readInt(), in.readInt());
+        }
+
+        List<Solution> res = new ArrayList<Solution>();
+        Point[] others = new Point[n];
+        for (int i = 0; i < n; i++)
+        {
+            Point ref = pts[i];
+            ref.draw();
+            for (int j = 0; j < n; j++)
+                others[j] = pts[j];
+
+            Arrays.sort(others, ref.SLOPE_ORDER);
+
+            int start = 0;
+            double slope = Double.NEGATIVE_INFINITY;
+            for (int j = 1; j < n; j++)
+            {
+                double sl = ref.slopeTo(others[j]);
+                if (sl == Double.NEGATIVE_INFINITY)
+                    continue;
+
+                if (slope != sl)
+                {
+                    if ((start != 0) && ((j - start) > 2)) {
+                        Solution sol = new Solution(j - start + 1);
+                        sol.add(ref);
+                        for (int k = start; k < j; k++)
+                            sol.add(others[k]);
+                        sol.sort();
+                        if (!res.contains(sol))
+                            res.add(sol);
+                    }
+                    slope = sl;
+                    start = j;
+                }
+
+            }
+            if ((n -  start) > 2) {
+                Solution sol = new Solution(n - start + 1);
+                sol.add(ref);
+                for (int k = start; k < n; k++)
+                    sol.add(others[k]);
+                sol.sort();
+                if (!res.contains(sol))
+                    res.add(sol);
+            }
+        }
+
+        Solution[] sorted = new Solution[res.size()];
+        res.toArray(sorted);
+        Insertion.sort(sorted);
+        for (Solution sol : sorted)
+        {
+            sol.draw();
+            sol.print();
+        }
+        StdDraw.show(0);
+    }
+}
+
diff --git a/Algorithms/Part-I/3-Collinear/Point.java b/Algorithms/Part-I/3-Collinear/Point.java
new file mode 100644
index 0000000..bd5bbe7
--- /dev/null
+++ b/Algorithms/Part-I/3-Collinear/Point.java
@@ -0,0 +1,122 @@
+/*************************************************************************
+ * Name:
+ * Email:
+ *
+ * Compilation:  javac Point.java
+ * Execution:
+ * Dependencies: StdDraw.java
+ *
+ * Description: An immutable data type for points in the plane.
+ *
+ *************************************************************************/
+
+import java.util.Comparator;
+
+public class Point implements Comparable<Point> {
+
+    // compare points by slope
+    public final Comparator<Point> SLOPE_ORDER = new SlopeOrder();
+
+    private final int x;                              // x coordinate
+    private final int y;                              // y coordinate
+
+    // create the point (x, y)
+    public Point(int x, int y) {
+        /* DO NOT MODIFY */
+        this.x = x;
+        this.y = y;
+    }
+
+    // plot this point to standard drawing
+    public void draw() {
+        /* DO NOT MODIFY */
+        StdDraw.point(x, y);
+    }
+
+    // draw line between this point and that point to standard drawing
+    public void drawTo(Point that) {
+        /* DO NOT MODIFY */
+        StdDraw.line(this.x, this.y, that.x, that.y);
+    }
+
+    // slope between this point and that point
+    public double slopeTo(Point that) {
+        if (this.y == that.y && this.x == that.x) return Double.NEGATIVE_INFINITY;
+
+        double dx = that.x - this.x;
+        if (dx == 0.0) return Double.POSITIVE_INFINITY;
+
+        double dy = that.y - this.y;
+        if (dy == 0.0) return +0;
+
+        return dy / dx;
+    }
+
+    private class SlopeOrder implements Comparator<Point>
+    {
+        public int compare(Point p, Point q)
+        {
+            double sp = slopeTo(p);
+            double sq = slopeTo(q);
+            if (sp < sq) return -1;
+            if (sp > sq) return  1;
+            return 0;
+        }
+    }
+
+    // is this point lexicographically smaller than that one?
+    // comparing y-coordinates and breaking ties by x-coordinates
+    public int compareTo(Point that) {
+        if (this.y < that.y) return -1;
+        if (this.y > that.y) return  1;
+        if (this.x < that.x) return -1;
+        if (this.x > that.x) return  1;
+        return 0;
+    }
+
+    // return string representation of this point
+    public String toString() {
+        /* DO NOT MODIFY */
+        return "(" + x + ", " + y + ")";
+    }
+
+    // unit test
+    public static void main(String[] args) {
+        System.out.println("Point.java asserts");
+        Point p0 = new Point(5, 4);
+
+        Point p1 = new Point(5, 4);
+        Point p2 = new Point(9, 3);
+        Point p3 = new Point(0, 5);
+        Point p4 = new Point(4, 4);
+        Point p5 = new Point(6, 4);
+
+        assert (p0.compareTo(p1) ==  0) : "compareTo p1";
+        assert (p0.compareTo(p2) ==  1) : "compareTo p2";
+        assert (p0.compareTo(p3) == -1) : "compareTo p3";
+        assert (p0.compareTo(p4) ==  1) : "compareTo p4";
+        assert (p0.compareTo(p5) == -1) : "compareTo p5";
+
+        Point[] pts = new Point[8];
+        pts[0] = new Point(-5, 3);
+        pts[1] = new Point(3, 5);
+        pts[2] = new Point(4, 3);
+        pts[3] = new Point(3, 3);
+        pts[4] = new Point(3, 0);
+        pts[5] = new Point(9, 6);
+        pts[6] = new Point(5, 5);
+        pts[7] = new Point(6, 0);
+
+        Point ref = pts[3];
+        System.out.println("REF: "+ref);
+        Selection.sort(pts, ref.SLOPE_ORDER);
+        double t = Double.NEGATIVE_INFINITY;
+        for (Point p : pts)
+        {
+            assert t <= ref.slopeTo(p);
+            System.out.println("  "+p+" "+ref.slopeTo(p));
+            t = ref.slopeTo(p);
+        }
+        System.out.println("SUCCESS");
+    }
+}
diff --git a/Algorithms/Part-I/3-Collinear/input6.txt b/Algorithms/Part-I/3-Collinear/input6.txt
new file mode 100644
index 0000000..8fb298a
--- /dev/null
+++ b/Algorithms/Part-I/3-Collinear/input6.txt
@@ -0,0 +1,7 @@
+6
+19000  10000
+18000  10000
+32000  10000
+21000  10000
+ 1234   5678
+14000  10000
diff --git a/Algorithms/Part-I/3-Collinear/input8.txt b/Algorithms/Part-I/3-Collinear/input8.txt
new file mode 100644
index 0000000..17f9e1e
--- /dev/null
+++ b/Algorithms/Part-I/3-Collinear/input8.txt
@@ -0,0 +1,9 @@
+8
+10000      0
+    0  10000
+ 3000   7000
+ 7000   3000
+20000  21000
+ 3000   4000
+14000  15000
+ 6000   7000
diff --git a/Algorithms/Part-I/3-Collinear/run.sh b/Algorithms/Part-I/3-Collinear/run.sh
new file mode 100755
index 0000000..154d8d7
--- /dev/null
+++ b/Algorithms/Part-I/3-Collinear/run.sh
@@ -0,0 +1,24 @@
+#! /bin/bash
+
+export "CLASSPATH=$CLASSPATH:.:$HOME/algs4/algs4.jar:$HOME/algs4/stdlib.jar"
+
+CLASSES="Point Brute Fast"
+
+rm *.class *.zip 2>/dev/null
+
+for kls in $CLASSES; do
+    ~/algs4/bin/checkstyle ${kls}.java
+    javac ${kls}.java
+done
+~/algs4/bin/findbugs *.class
+
+echo "RUN..."
+# java -enableassertions Point
+# java Brute input6.txt
+# java Brute input8.txt
+java Brute random152.txt
+# java Fast input6.txt
+# java Fast input8.txt
+java Fast random152.txt
+
+zip collinear.zip Point.java Brute.java Fast.java