From af56ef8708c749b9eeee220c8fa6bc729f9380f7 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= <jeremy@asynk.ch>
Date: Mon, 11 Mar 2013 08:06:21 +0100
Subject: Algorithms-I : 3-Collinear: first submission, Fast is slow ;)
---
Algorithms/Part-I/3-Collinear/Brute.java | 92 ++++++++++++++++++++
Algorithms/Part-I/3-Collinear/Fast.java | 141 +++++++++++++++++++++++++++++++
Algorithms/Part-I/3-Collinear/Point.java | 122 ++++++++++++++++++++++++++
Algorithms/Part-I/3-Collinear/input6.txt | 7 ++
Algorithms/Part-I/3-Collinear/input8.txt | 9 ++
Algorithms/Part-I/3-Collinear/run.sh | 24 ++++++
6 files changed, 395 insertions(+)
create mode 100644 Algorithms/Part-I/3-Collinear/Brute.java
create mode 100644 Algorithms/Part-I/3-Collinear/Fast.java
create mode 100644 Algorithms/Part-I/3-Collinear/Point.java
create mode 100644 Algorithms/Part-I/3-Collinear/input6.txt
create mode 100644 Algorithms/Part-I/3-Collinear/input8.txt
create mode 100755 Algorithms/Part-I/3-Collinear/run.sh
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
--
cgit v1.1-2-g2b99