Menu
Topics Index
...
`

Weekend Hack - 02 Feb 2013 - Results

Thanks to Soma Sneha, Krishna Sai Mulpuri, Sulekha Metta, Srihari Adelli, Srinivas Rao Bolla, Tejaswini Rao Potlapally and Sruthi Vaka for spending so much time, coming up with original and innovative answers and for submitting them. Thanks to many others who have tried to get the solution.
We have reviewed the solutions as per the criteria mentioned at Weekend Hack and included the comments below. Few minor comments found are included below in the order of the submission. These comments are not intended to point out the mistakes in the solutions but to learn from them.

The winner of both the weeekend hacks (Weekend Hack 02 Feb 2013 - 1 and Weekend Hack 02 Feb 2013 - 2) is Sulekha Metta. She is eligible for two recharges worth Rs. 150 each. But she kind heartedly agreed to part with one of the recharges. The parted recharge worth Rs. 150 will be given to the second best solution provided by Tejaswini Rao Potlapally.

Find the triangle whose center (centroid) is nearest to the origin (0,0)

Given the list of triangles, write a program to find the triangle whose center (centroid) is nearest to the origin (0,0). When returning the triangle, the points of the triangle should be adjusted such that the top, left and bottom values represent the positions in the coordinate system. The top point is top most left point and left point is left most bottom point. The remaining point will be considered as the right point.

Input (List) Output (Triangle)
[{[0.0,0.0] - [2.0,0.0] - [1.0,3.0]},
{[0.0,0.0] - [8.0,0.0] - [7.0,8.0]}]
{[1.0,3.0] - [0.0,0.0] - [2.0,0.0]}
[{[0.0,0.0] - [2.0,0.0] - [1.0,3.0]}] {[1.0,3.0] - [0.0,0.0] - [2.0,0.0]}
[{[0.0,0.0] - [8.0,0.0] - [7.0,8.0]},
{[5.0,5.0] - [13.0,5.0] - [12.0,13.0]},
{[10.0,0.0] - [18.0,0.0] - [77.0,8.0]}]
{[7.0,8.0] - [0.0,0.0] - [8.0,0.0]}
[{[0.0,0.0] - [2.0,0.0] - [1.0,90.0]},
{[21.0,0.0] - [50.0,5.0] - [120.0,111.0]},
{[0.0,0.0] - [28.0,0.0] - [7.0,8.0]},
{[-10.0,-11.0] - [0.0,0.0] - [-5.0,0.0]}]
{[-5.0,0.0] - [-10.0,-11.0] - [0.0,0.0]}
EMPTY LIST null

Solution 1 - Submitted on Sat Feb 2 12:34:52 2013

import java.util.ArrayList;
import java.util.List;

public class FindNearestTriangle {

    public static void main(String s[]) {
        List points = new ArrayList();
        points.add(new Triangle(0, 0, 2, 0, 1, 90));
        points.add(new Triangle(21, 0, 50, 5, 120, 111));
        points.add(new Triangle(0, 0, 28, 0, 7, 8));
        points.add(new Triangle(-10, -11, 0, 0, -5, 0));
        System.out.println("The nearest triangle is : " + findNearestTriangle(points));
    }

    public static Triangle findNearestTriangle(List triangles) {
        if (triangles.isEmpty())
            return null;
        if (triangles.size() == 1)
            return arrange(triangles.get(0));
        Triangle nearest = new Triangle(0, 0, 0, 0, 0, 0);
        double high = -1;
        for (Triangle temp : triangles) {
            double x = (temp.top.x + temp.left.x + temp.right.x) / 3;
            double y = (temp.top.y + temp.left.y + temp.right.y) / 3;
            double t = Math.sqrt(x * x + y * y);
            /* should here OR is usd b'coz for the first time (high>t) doesn't hold good,but still content present in if should be executed */
            if (high > t || high == -1) {
                high = t;
                nearest.top = temp.top;
                nearest.left = temp.left;
                nearest.right = temp.right;
            }
        }
        return arrange(nearest);
    }

    public static Triangle arrange(Triangle nearest) {
        //for right point
        Point temp = nearest.right;
        if (nearest.right.x > nearest.left.x) {
            if (nearest.right.x < nearest.top.x) {
                nearest.right = nearest.top;
                nearest.top = temp;
            }
        } else {
            if (nearest.left.x > nearest.top.x) {
                nearest.right = nearest.left;
                nearest.left = temp;
            } else {
                nearest.right = nearest.top;
                nearest.top = temp;
            }
        }
        //for top point 
        if (nearest.top.y < nearest.left.y) {
            temp = nearest.top;
            nearest.top = nearest.left;
            nearest.left = temp;
        }
        return (nearest);
    }
}

class Point {

    double x;
    double y;

    Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "[" + x + "," + y + "]";
    }
}

class Triangle {

    Point top;
    Point left;
    Point right;

    public Triangle(Point top, Point left, Point right) {
        this.top = top;
        this.left = left;
        this.right = right;
    }

    public Triangle(int x1, int y1, int x2, int y2, int x3, int y3) {
        this(new Point(x1, y1), new Point(x2, y2), new Point(x3, y3));
    }

    @Override
    public String toString() {
        return "{" + top + " - " + left + " - " + right + "}";
    }
}

Review Comments

  1. The code is simple and easy to understand.
  2. Naming conventions and the comments are useful.
  3. Need not create an object for nearest during initialization. It would have been better if we initialized nearest as null. Instead of having one more variable high, and comparing high == -1, we could have done the comparison of nearest with null.
  4. Need not assign top, left, right from temp to nearest. We could have directly assigned temp to nearest, that way both nearest and temp point the same object.
  5. The checks of isEmpty and size() == 1 could have been avoided if we improved the intialization of the variables. It is not a good idea to return in between the method. If in future, we have to call arrange2 instead of arrange, there are good chances that the method call arrange at the beginning of the method will not be changed.
  6. The input traingles should not be modified, since the method name does not convey any changes/modifications.
  7. The adjusting logic does not work for triangles {[5.0,30.0] - [5.0,20.0] - [-10.0,25.0]}, {[-10.0,25.0] - [5.0,30.0] - [5.0,20.0]}, {[5.0,20.0] - [-10.0,25.0] - [5.0,30.0]},

Solution 2 - Submitted on Sat Feb 2 13:05:37 2013

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

class FindNearestTriangle {

    public static void main(String s[]) {
        List points = new ArrayList();
        points.add(new Triangle(0, 0, 2, 0, 1, 90));
        points.add(new Triangle(21, 0, 50, 5, 120, 111));
        points.add(new Triangle(0, 0, 28, 0, 7, 8));
        points.add(new Triangle(-10, -11, 0, 0, -5, 0));
        System.out.println("The nearest triangle is : " + findNearestTriangle(points));
    }

    public static Triangle findNearestTriangle(List triangles) {
        if (triangles != null && triangles.size() > 1) {
            Iterator it = triangles.iterator();
            double cen[] = new double[triangles.size()];
            Triangle[] t = new Triangle[triangles.size()];
            //code for calculating centroid of each triangle
            //cen[i] refers to the centroid of triangle t[i]
            for (int i = 0; it.hasNext(); i++) {
                t[i] = (Triangle) it.next();
                Point p = new Point(0, 0);
                p.x = (t[i].top.x + t[i].left.x + t[i].right.x) / 3;
                p.y = (t[i].top.y + t[i].left.y + t[i].right.y) / 3;
                /*calculating sum of squares of coordinates as the squareroot doesnt matter for checking the distance*/
                cen[i] = p.x * p.x + p.y * p.y;
            }
            /*using selection sort for one iteration so that t[0] is the triangle having least distance from its centroid to origin */
            for (int i = 0; i < 1; i++)
                for (int j = i + 1; j < cen.length; j++)
                    if (cen[i] > cen[j]) {
                        Triangle tri = t[i];
                        double d = cen[i];
                        t[i] = t[j];
                        cen[i] = cen[j];
                        t[j] = tri;
                        cen[j] = d;
                    }
            return adjust(t[0]);
        } else if (triangles.size() == 1) {
            Iterator it = triangles.iterator();
            return adjust((Triangle) it.next());
        } else
            return null;
    }

    public static Triangle adjust(Triangle t) {
        /*method for adjusting the points so that the top point is top most left point and left point is left most bottom point & the remaining point is the right point*/
        Point[] p = new Point[3];
        p[0] = t.top;
        p[1] = t.left;
        p[2] = t.right;
        for (int i = 0; i < 2; i++)
            for (int j = i + 1; j < 3; j++)
                if (p[i].x > p[j].x) {
                    Point pt = p[i];
                    p[i] = p[j];
                    p[j] = pt;
                }
        t.top = p[1];
        t.left = p[0];
        t.right = p[2];
        return t;
    }
}

class Point {

    double x;
    double y;

    Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "[" + x + "," + y + "]";
    }
}

class Triangle {

    Point top;
    Point left;
    Point right;

    public Triangle(Point top, Point left, Point right) {
        this.top = top;
        this.left = left;
        this.right = right;
    }

    public Triangle(int x1, int y1, int x2, int y2, int x3, int y3) {
        this(new Point(x1, y1), new Point(x2, y2), new Point(x3, y3));
    }

    @Override
    public String toString() {
        return "{" + top + " - " + left + " - " + right + "}";
    }
}

Review Comments

  1. Comments are useful
  2. The idea of not calculating the square root, since it does not matter while comparing is good.
  3. We could have avoided the sorting logic, by creating a variable above the first loop and use it for tracking the nearest triangle and its value.
  4. Unnecessary arrays for storing the triangles and centroids could be avoided.
  5. The logic of adjust method is little bit confusing and it does not seem to compare the values of y while arriving at the left point.
  6. The input traingles should not be modified, since the method name does not convey any changes/modifications.
  7. The adjusting logic does not work for triangles {[5.0,30.0] - [5.0,20.0] - [10.0,25.0]}, {[5.0,30.0] - [10.0,25.0] - [5.0,20.0]}, {[10.0,25.0] - [5.0,30.0] - [5.0,20.0]}, {[5.0,30.0] - [5.0,20.0] - [-10.0,25.0]}, {[-10.0,25.0] - [5.0,20.0] - [5.0,30.0]}, {[5.0,20.0] - [-10.0,25.0] - [5.0,30.0]}, {[10.0,0.0] - [20.0,0.0] - [15.0,-21.0]}, {[10.0,0.0] - [15.0,-21.0] - [20.0,0.0]}, {[15.0,-21.0] - [10.0,0.0] - [20.0,0.0]}, {[15.0,-21.0] - [20.0,0.0] - [10.0,0.0]}, {[20.0,0.0] - [15.0,-21.0] - [10.0,0.0]}, {[20.0,0.0] - [10.0,0.0] - [15.0,-21.0]},

Solution 3 - Submitted on Sat Feb 2 14:21:20 2013

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

class FindNearestTriangle {

    public static void main(String s[]) {
        List points = new ArrayList();
        points.add(new Triangle(0, 0, 2, 0, 1, 90));
        points.add(new Triangle(21, 0, 50, 5, 120, 111));
        points.add(new Triangle(0, 0, 28, 0, 7, 8));
        points.add(new Triangle(-10, -11, 0, 0, -5, 0));
        System.out.println("The nearest triangle is : " + findNearestTriangle(points));
    }

    public static Triangle findNearestTriangle(List triangles) {
        if (triangles.isEmpty())
            return null;
        double sumx = 0, sumy = 0, min;
        int j = 0;
        double distance[] = new double[triangles.size()];
        for (Triangle t : triangles) {
            sumx = (t.top.x + t.left.x + t.right.x) / 3; //calculating centroid
            sumy = (t.top.y + t.left.y + t.right.y) / 3;
            double centroidDistanceFrmOrigin = sumx * sumx + sumy * sumy;
            distance[j] = Math.sqrt(centroidDistanceFrmOrigin); /*Centroid Distance From Origin and storing in distance array*/
            j++;
        }
        int index = 0;
        min = distance[0];
        for (int k = 1; k < j; k++) {
            if (min > distance[k]) {
                min = distance[k];
                index = k;
            }
        }
        Triangle t1 = triangles.get(index); //arranging arraylist element in order
        List result = new ArrayList();
        result.add(new Point(t1.top.x, t1.top.y));
        result.add(new Point(t1.left.x, t1.left.y));
        result.add(new Point(t1.right.x, t1.right.y));
        Collections.sort(result, new Comparator() {

            @Override
            public int compare(Point p1, Point p2) {
                final Point p21 = p2;
                if (p1.x != p21.x)
                    return (int) (p1.x - p21.x);
                return (int) (p1.y - p21.y);
            }
        });
        Collections.swap(result, 0, 1);
        Triangle out = new Triangle(0, 0, 0, 0, 0, 0);
        out.top = (Point) result.get(0);
        out.left = (Point) result.get(1);
        out.right = (Point) result.get(2);
        return out;
    }
}

class Point {

    double x;
    double y;

    Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "[" + x + "," + y + "]";
    }
}

class Triangle {

    Point top;
    Point left;
    Point right;

    public Triangle(Point top, Point left, Point right) {
        this.top = top;
        this.left = left;
        this.right = right;
    }

    public Triangle(int x1, int y1, int x2, int y2, int x3, int y3) {
        this(new Point(x1, y1), new Point(x2, y2), new Point(x3, y3));
    }

    @Override
    public String toString() {
        return "{" + top + " - " + left + " - " + right + "}";
    }
}

Review Comments

  1. Comments are useful and the naming conventions are followed.
  2. The idea of using the Collections.sort for arranging the triangle is good. The variable p21 is unnecessary and could have used p2 directly.
  3. We could have avoided the sorting logic, by creating a variable above the first loop and use it for tracking the nearest triangle and its value.
  4. List and ArrayList could have been declared as Generics, so unnecessary type casting to Point could have been avoided.
  5. Could have created one or two methods to improve the readability.
  6. The adjusting logic does not work for triangles {[5.0,30.0] - [5.0,20.0] - [-10.0,25.0]}, {[5.0,30.0] - [-10.0,25.0] - [5.0,20.0]}, {[-10.0,25.0] - [5.0,30.0] - [5.0,20.0]}, {[-10.0,25.0] - [5.0,20.0] - [5.0,30.0]}, {[5.0,20.0] - [-10.0,25.0] - [5.0,30.0]}, {[5.0,20.0] - [5.0,30.0] - [-10.0,25.0]}, {[10.0,0.0] - [20.0,0.0] - [15.0,-21.0]}, {[10.0,0.0] - [15.0,-21.0] - [20.0,0.0]}, {[15.0,-21.0] - [10.0,0.0] - [20.0,0.0]}, {[15.0,-21.0] - [20.0,0.0] - [10.0,0.0]}, {[20.0,0.0] - [15.0,-21.0] - [10.0,0.0]}, {[20.0,0.0] - [10.0,0.0] - [15.0,-21.0]},

Solution 4 - Submitted on Sat Feb 2 14:52:24 2013

import java.util.ArrayList;
import java.util.List;

class FindNearestTriangle {

    public static void main(String s[]) {
        List points = new ArrayList();
        points.add(new Triangle(0, 0, 2, 0, 1, 90));
        points.add(new Triangle(21, 0, 50, 5, 120, 111));
        points.add(new Triangle(0, 0, 28, 0, 7, 8));
        points.add(new Triangle(-10, -11, 0, 0, -5, 0));
        System.out.println("The nearest triangle is : " + findNearestTriangle(points));
    }

    public static Triangle findNearestTriangle(List triangles) {
        double minimumlength = 0;
        boolean flag = true;
        Triangle trisample = null;
        if (triangles.size() == 0)//if list is empty it return null.
            return null;
        for (Triangle triangle : triangles) {
            double length;
            Point output = findcentriod(triangle);//calculating the centroid.
            length = lengthfromcentre00(output);//calculating the length from (0,0).
            if (minimumlength > length || flag)//if it is first iteration,minimumlength will be intialized to length using flag.
            {
                trisample = triangle;
                minimumlength = length;
                flag = false;
            }
        }
        //Now,arranging  according to the requirement
        Triangle result = null;
        if (trisample.top.y > trisample.left.y) {
            if (trisample.top.y > trisample.right.y)
                result = arranging(trisample.left, trisample.right, trisample.top);
            else
                result = arranging(trisample.top, trisample.right, trisample.left);
        } else {
            if (trisample.left.y > trisample.right.y)
                result = arranging(trisample.top, trisample.right, trisample.left);
            else
                result = arranging(trisample.top, trisample.left, trisample.right);
        }
        return result;
    }

    static Triangle arranging(Point left1, Point right1, Point top1) {
        Triangle result = null;
        if (left1.x < right1.x)
            result = new Triangle(top1, left1, right1);
        else {
            if (left1.x == right1.x) {
                if (left1.y < right1.y)
                    result = new Triangle(top1, left1, right1);
                else
                    result = new Triangle(top1, right1, left1);
            } else
                result = new Triangle(top1, right1, left1);
        }
        return result;
    }//end of the arranging method.

    static Point findcentriod(Triangle sample) {
        Point centroid = new Point(0, 0);
        centroid.x = sample.top.x + sample.left.x + sample.right.x / 3;
        centroid.y = sample.top.y + sample.left.y + sample.right.y / 3;
        return centroid;
    }//end of the findcentriod method.

    static double lengthfromcentre00(Point centroid) {
        double result = Math.sqrt(Math.pow(centroid.x - 0, 2) + Math.pow(centroid.y - 0, 2));
        return result;
    }//end of the lengthfromcetre(0,0).
}

class Point {

    double x;
    double y;

    Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "[" + x + "," + y + "]";
    }
}

class Triangle {

    Point top;
    Point left;
    Point right;

    public Triangle(Point top, Point left, Point right) {
        this.top = top;
        this.left = left;
        this.right = right;
    }

    public Triangle(int x1, int y1, int x2, int y2, int x3, int y3) {
        this(new Point(x1, y1), new Point(x2, y2), new Point(x3, y3));
    }

    @Override
    public String toString() {
        return "{" + top + " - " + left + " - " + right + "}";
    }
}

Review Comments

  1. The way methods are created to split the functionality is good.
  2. Comments and naming conventions are followed.
  3. The logic of arranging is too complex and could be simplified.
  4. The adjusting logic does not work for triangles {[10.0,25.0] - [5.0,20.0] - [5.0,30.0]}, {[-10.0,25.0] - [5.0,20.0] - [5.0,30.0]}, {[10.0,0.0] - [20.0,0.0] - [15.0,-21.0]}, {[10.0,0.0] - [15.0,-21.0] - [20.0,0.0]}, {[15.0,-21.0] - [10.0,0.0] - [20.0,0.0]}, {[20.0,0.0] - [15.0,-21.0] - [10.0,0.0]}, {[1.0,1.0] - [5.0,0.0] - [3.0,7.0]},

Solution 5 - Submitted on Sat Feb 2 18:09:47 2013

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

class FindNearestTriangle {

    public static void main(String s[]) {
        List points = new ArrayList();
        points.add(new Triangle(0, 0, 2, 0, 1, 90));
        points.add(new Triangle(21, 0, 50, 5, 120, 111));
        points.add(new Triangle(0, 0, 28, 0, 7, 8));
        points.add(new Triangle(-10, -11, 0, 0, -5, 0));
        System.out.println("The nearest triangle is : " + findNearestTriangle(points));
    }

    public static Triangle findNearestTriangle(List triangles) {
        Triangle t1;
        if (triangles != null && triangles.size() > 1) {
            Iterator it = triangles.iterator();
            double centroid[] = new double[triangles.size()];
            Triangle[] t = new Triangle[triangles.size()];
            for (int i = 0; it.hasNext(); i++) {
                t[i] = (Triangle) it.next();
                Point p = new Point(0, 0);
                p.x = (t[i].top.x + t[i].left.x + t[i].right.x) / 3;
                p.y = (t[i].top.y + t[i].left.y + t[i].right.y) / 3;
                centroid[i] = p.x * p.x + p.y * p.y;
            }
            for (int i = 0; i < 1; i++)
                for (int j = i + 1; j < centroid.length; j++)
                    if (centroid[i] > centroid[j]) {
                        Triangle tri = t[i];
                        double d = centroid[i];
                        t[i] = t[j];
                        centroid[i] = centroid[j];
                        t[j] = tri;
                        centroid[j] = d;
                    }
            t1 = t[0];
            Point[] p = new Point[3];
            p[0] = t1.top;
            p[1] = t1.left;
            p[2] = t1.right;
            for (int i = 0; i < 2; i++)
                for (int j = i + 1; j < 3; j++)
                    if (p[i].x > p[j].x) {
                        Point pt = p[i];
                        p[i] = p[j];
                        p[j] = pt;
                    }
            t1.top = p[1];
            t1.left = p[0];
            t1.right = p[2];
            return t1;
        } else if (triangles.size() == 1) {
            Iterator it = triangles.iterator();
            t1 = (Triangle) it.next();
            Point[] p = new Point[3];
            p[0] = t1.top;
            p[1] = t1.left;
            p[2] = t1.right;
            for (int i = 0; i < 2; i++)
                for (int j = i + 1; j < 3; j++)
                    if (p[i].x > p[j].x) {
                        Point pt = p[i];
                        p[i] = p[j];
                        p[j] = pt;
                    }
            t1.top = p[1];
            t1.left = p[0];
            t1.right = p[2];
            return t1;
        } else
            return null;
    }
}

class Point {

    double x;
    double y;

    Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "[" + x + "," + y + "]";
    }
}

class Triangle {

    Point top;
    Point left;
    Point right;

    public Triangle(Point top, Point left, Point right) {
        this.top = top;
        this.left = left;
        this.right = right;
    }

    public Triangle(int x1, int y1, int x2, int y2, int x3, int y3) {
        this(new Point(x1, y1), new Point(x2, y2), new Point(x3, y3));
    }

    @Override
    public String toString() {
        return "{" + top + " - " + left + " - " + right + "}";
    }
}

Review Comments

  1. The arrays for storing the traingles and distances and the sorting logic could have been avoided, if we used variables for tracking the nearest triangle and the distance.
  2. There is duplicate code between while processing multiple triangles and single triangle.
  3. The input traingles should not be modified, since the method name does not convey any changes/modifications.
  4. The adjusting logic does not work for triangles {[5.0,30.0] - [5.0,20.0] - [10.0,25.0]}, {[5.0,30.0] - [10.0,25.0] - [5.0,20.0]}, {[10.0,25.0] - [5.0,30.0] - [5.0,20.0]}, {[5.0,30.0] - [5.0,20.0] - [-10.0,25.0]}, {[-10.0,25.0] - [5.0,20.0] - [5.0,30.0]}, {[5.0,20.0] - [-10.0,25.0] - [5.0,30.0]}, {[10.0,0.0] - [20.0,0.0] - [15.0,-21.0]}, {[10.0,0.0] - [15.0,-21.0] - [20.0,0.0]}, {[15.0,-21.0] - [10.0,0.0] - [20.0,0.0]}, {[15.0,-21.0] - [20.0,0.0] - [10.0,0.0]}, {[20.0,0.0] - [15.0,-21.0] - [10.0,0.0]}, {[20.0,0.0] - [10.0,0.0] - [15.0,-21.0]},

Solution 6 - Submitted on Sat Feb 2 21:20:58 2013

import java.util.ArrayList;
import java.util.List;

class FindNearestTriangle {

    public static void main(String s[]) {
        List points = new ArrayList();
        points.add(new Triangle(0, 0, 2, 0, 1, 90));
        points.add(new Triangle(21, 0, 50, 5, 120, 111));
        points.add(new Triangle(0, 0, 28, 0, 7, 8));
        points.add(new Triangle(-10, -11, 0, 0, -5, 0));
        System.out.println("The nearest triangle is : " + findNearestTriangle(points));
    }

    public static Triangle findNearestTriangle(List triangles) {
        try {
            Triangle[] array = triangles.toArray(new Triangle[triangles.size()]);
            double d1[] = new double[2];
            double d2[] = new double[triangles.size()];
            for (int i = 0; i < array.length; i++) {
                Point[] p = new Point[3];
                p[0] = array[i].top;
                p[1] = array[i].left;
                p[2] = array[i].right;
                double[] d = new double[6];
                int k, j;
                for (j = 0, k = 0; j < d.length || k <= 2; j++, k++) {
                    d[j++] = p[k].x;
                    d[j] = p[k].y;
                }
                d1[0] = (d[0] + d[2] + d[4]) / 3;
                d1[1] = (d[1] + d[3] + d[5]) / 3;
                d2[i] = Math.sqrt(d1[0] * d1[0] + d1[1] * d1[1]);
            }
            double min = d2[0];
            int index = 0;
            for (int s = 1; s < d2.length; s++) {
                if (d2[s] < min) {
                    min = d2[s];
                    index = s;
                }
            }
            return new Triangle(array[index].right, array[index].top, array[index].left);
        } catch (Exception e) {
            return null;
        }
    }
}

class Point {

    double x;
    double y;

    Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "[" + x + "," + y + "]";
    }
}

class Triangle {

    Point top;
    Point left;
    Point right;

    public Triangle(Point top, Point left, Point right) {
        this.top = top;
        this.left = left;
        this.right = right;
    }

    public Triangle(int x1, int y1, int x2, int y2, int x3, int y3) {
        this(new Point(x1, y1), new Point(x2, y2), new Point(x3, y3));
    }

    @Override
    public String toString() {
        return "{" + top + " - " + left + " - " + right + "}";
    }
}

Review Comments

  1. The logic of finding the distance and the nearest triangle is confusing.
  2. It is better to prevent the exceptions than handling them. We could have checked for Traingles size and returned null if it was empty.
  3. The logic of adjusting is completely missing.
  4. The adjusting logic does not work for triangles {[5.0,30.0] - [5.0,20.0] - [10.0,25.0]}, {[5.0,30.0] - [10.0,25.0] - [5.0,20.0]}, {[10.0,25.0] - [5.0,30.0] - [5.0,20.0]}, {[10.0,25.0] - [5.0,20.0] - [5.0,30.0]}, {[5.0,20.0] - [5.0,30.0] - [10.0,25.0]}, {[5.0,30.0] - [5.0,20.0] - [-10.0,25.0]}, {[5.0,30.0] - [-10.0,25.0] - [5.0,20.0]}, {[-10.0,25.0] - [5.0,30.0] - [5.0,20.0]}, {[5.0,20.0] - [-10.0,25.0] - [5.0,30.0]}, {[5.0,20.0] - [5.0,30.0] - [-10.0,25.0]}, {[10.0,0.0] - [15.0,21.0] - [20.0,0.0]}, {[15.0,21.0] - [10.0,0.0] - [20.0,0.0]}, {[15.0,21.0] - [20.0,0.0] - [10.0,0.0]}, {[20.0,0.0] - [15.0,21.0] - [10.0,0.0]}, {[20.0,0.0] - [10.0,0.0] - [15.0,21.0]}, {[10.0,0.0] - [20.0,0.0] - [15.0,-21.0]}, {[10.0,0.0] - [15.0,-21.0] - [20.0,0.0]}, {[15.0,-21.0] - [10.0,0.0] - [20.0,0.0]}, {[20.0,0.0] - [15.0,-21.0] - [10.0,0.0]}, {[20.0,0.0] - [10.0,0.0] - [15.0,-21.0]}, {[1.0,1.0] - [3.0,7.0] - [5.0,0.0]}, {[3.0,7.0] - [1.0,1.0] - [5.0,0.0]}, {[3.0,7.0] - [5.0,0.0] - [1.0,1.0]}, {[5.0,0.0] - [3.0,7.0] - [1.0,1.0]}, {[5.0,0.0] - [1.0,1.0] - [3.0,7.0]},

Find all the possible positions which a white minister can move without getting killed by black minister and black horse

In chess, assuming that the columns are numbered A to H and the rows are numbered 1 to 8. Write a program to find all the possible positions which a white minister can move without getting killed by black minister and black horse. Assume that there is nothing else on the chess board apart from these three.
NOTE: The list returned should be first sorted by columns and then by rows, so A4 comes before B1 and C7 comes before D5 etc.,

Input (White Minister Position, Black Minister Position, Black Horse Position) Output (Sorted List of Positions)
White Minister = C6, Black Minister = B4, Black Horse = A3 [A6, A8, C1, C7, C8, D5, D7, E6, E8, F3, F6, G2, G6, H1, H6]
White Minister = C3, Black Minister = G3, Black Horse = E5 [A1, A5, B2, B4, C1, C2, C5, C8, D2, D4, F6, H8]
White Minister = A5, Black Minister = D3, Black Horse = G6 [A1, A2, A4, A7, A8, B4, B6, C5, C7, E1, G5, H5]
White Minister = D1, Black Minister = A3, Black Horse =F4 [B1, C2, D2, D4, D7, D8, E1, F1, G1, G4, H1]

Solution 1 - Submitted on Sat Feb 2 14:42:14 2013

import java.util.ArrayList;
import java.util.List;

class FindWhiteMinisterPositionsWithBlackMinisterAndHorse {

    public static void main(String s[]) {
        ChessPosition whiteMinister = new ChessPosition('C', 6);
        ChessPosition blackMinister = new ChessPosition('B', 4);
        ChessPosition blackHorse = new ChessPosition('A', 3);
        System.out.println("The positions which the white minister can move with out getting killed : " + getPossiblePositions(whiteMinister, blackMinister, blackHorse));
    }

    public static List getPossiblePositions(ChessPosition whiteMinister, ChessPosition blackMinister, ChessPosition blackHorse) {
        List result = new ArrayList();
        for (char i = 'A'; i <= 'H'; i++) {
            for (int j = 1; j <= 8; j++) {
                //if i,j values are equal to give Ministers and horse,then don't enter
                if (!((whiteMinister.column == i && whiteMinister.row == j) || (blackHorse.row == i && blackHorse.column == j) || (blackMinister.row == j && blackMinister.column == i))) {
                    /*this if loop gives what are all possbile moves for whiteMinister irrespective of others */
                    if (whiteMinister.column == i || whiteMinister.row == j || (Math.abs(whiteMinister.column - i) - Math.abs(whiteMinister.row - j)) == 0) {
                        /* this if removes all those postions which whiteMinister collides with blackMinister */
                        if (!(blackMinister.column == i || blackMinister.row == j || Math.abs(blackMinister.column - i) - Math.abs(blackMinister.row - j) == 0)) {
                            /* this if removes all those postions which whiteMinister collides with blackHorse */
                            if (!(Math.abs(blackHorse.column - i) <= 2 && Math.abs(blackHorse.column - i) >= 1 && Math.abs(blackHorse.row - j) <= 2 && Math.abs(blackHorse.row - j) >= 1 && Math.abs(Math.abs(blackHorse.column - i) - Math.abs(blackHorse.row - j)) == 1))
                                result.add(new ChessPosition(i, j));
                        }
                    }
                }
            }
        }
        return result;
    }
}

class ChessPosition {

    char column;
    int row;

    public ChessPosition(char column, int row) {
        this.column = column;
        this.row = row;
    }

    @Override
    public String toString() {
        return column + "" + row;
    }
}

Review Comments

  1. The logic is simple and easy to understand.
  2. The comments are useful.
  3. We could have split the multiple if conditions into smaller ones for better readability.

Solution 2 - Submitted on Sat Feb 2 22:16:52 2013

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

class FindWhiteMinisterPositionsWithBlackMinisterAndHorse {

    public static void main(String s[]) {
        ChessPosition whiteMinister = new ChessPosition('C', 6);
        ChessPosition blackMinister = new ChessPosition('B', 4);
        ChessPosition blackHorse = new ChessPosition('A', 3);
        System.out.println("The positions which the white minister can move with out getting killed : " + getPossiblePositions(whiteMinister, blackMinister, blackHorse));
    }

    public static List getPossiblePositions(ChessPosition whiteMinister, ChessPosition blackMinister, ChessPosition blackHorse) {
        List d1, d2, d3 = new ArrayList();
        d1 = positions(whiteMinister);
        d2 = positions(blackMinister);
        d2.add(new ChessPosition(blackMinister.column, blackMinister.row));
        d3 = positionsHorse(blackHorse);
        List d2d3 = new ArrayList();
        d2d3.addAll(d2);
        d2d3.addAll(d3);
        Collections.sort(d1, new Comparator() {

            @Override
            public int compare(ChessPosition o1, ChessPosition o2) {
                if (o1.column != o2.column)
                    return o1.column - o2.column;
                return o1.row - o2.row;
            }
        });
        List out = new ArrayList(); /*finding the positions which the white minister can move with out getting killed*/
        for (ChessPosition t1 : d1) {
            int count = 0;
            for (ChessPosition t2 : d2d3) {
                if (t1.column == t2.column && t2.row == t1.row) {
                    count = 1;
                    break;
                }
            }
            if (count == 0) {
                out.add(t1);
            }
        }
        return out;
    }

    public static List positions(ChessPosition minister)/*method to find the all the possible positions*/
    {
        char j;
        List diagonals = new ArrayList();
        j = minister.column;
        j--;
        for (int i = minister.row + 1; i <= 8 && j >= 'A' && j <= 'H'; i++, j--)
            diagonals.add(new ChessPosition(j, i));
        j = minister.column;
        j--;
        for (int i = minister.row - 1; i >= 1 && j >= 'A' && j < 'H'; i--, j--)
            diagonals.add(new ChessPosition(j, i));
        j = minister.column;
        j++;
        for (int i = minister.row + 1; i <= 8 && j <= 'H'; i++, j++)
            diagonals.add(new ChessPosition(j, i));
        j = minister.column;
        j++;
        for (int i = minister.row - 1; i >= 1 && j <= 'H'; i--, j++)
            diagonals.add(new ChessPosition(j, i));
        char i;
        int k;
        for (i = minister.column, k = 1; k <= 8; k++) {
            if (k == minister.row)
                continue;
            diagonals.add(new ChessPosition(i, k));
        }
        int i1;
        char ch;
        for (i1 = minister.row, ch = 'A'; ch <= 'H'; ch++) {
            if (ch == minister.column)
                continue;
            diagonals.add(new ChessPosition(ch, i1));
        }
        return diagonals;
    }

    public static List positionsHorse(ChessPosition horse) {
        List horsePositions = new ArrayList();
        char c1 = (char) ((horse.column) - 1);
        char c2 = (char) ((horse.column) + 1);
        int i1 = (horse.row) + 2;
        int i2 = (horse.row) - 2;
        for (int i = 0; i < 2; i++) {
            if (c1 >= 'A' && i1 <= 8)
                horsePositions.add(new ChessPosition(c1, i1));
            if (c1 >= 'A' && i2 >= 1)
                horsePositions.add(new ChessPosition(c1, i2));
            if (c2 <= 'H' && i1 <= 8)
                horsePositions.add(new ChessPosition(c2, i1));
            if (c2 <= 'H' && i2 >= 1)
                horsePositions.add(new ChessPosition(c2, i2));
            c1--;
            c2++;
            i1--;
            i2++;
        }
        return horsePositions;
    }
}

class ChessPosition {

    char column;
    int row;

    public ChessPosition(char column, int row) {
        this.column = column;
        this.row = row;
    }

    @Override
    public String toString() {
        return column + "" + row;
    }
}

Review Comments

  1. The variables d1, d2, d3, d2d3, t1, t2 could be named better.
  2. The idea of creating the methods for getting the positions of minister and horse is good.
  3. The duplicate code inside positions and positionsHorse could be avoided.
  4. Although the logic is lengthy, it is easy to understand.

Solution 3 - Submitted on Sun Feb 3 17:50:14 2013

import java.util.ArrayList;
import java.util.List;

class FindWhiteMinisterPositionsWithBlackMinisterAndHorse {

    public static void main(String s[]) {
        ChessPosition whiteMinister = new ChessPosition('C', 6);
        ChessPosition blackMinister = new ChessPosition('B', 4);
        ChessPosition blackHorse = new ChessPosition('A', 3);
        System.out.println("The positions which the white minister can move with out getting killed : " + getPossiblePositions(whiteMinister, blackMinister, blackHorse));
    }

    public static List getPossiblePositions(ChessPosition whiteMinister, ChessPosition blackMinister, ChessPosition blackHorse) {
        int board[][] = new int[8][8];
        int col = blackMinister.column - 65;
        int row = blackMinister.row - 1;
        //positions where  black minister can move
        for (int i = 0; i < 8; i++) {
            if (i != col)
                board[row][i] = 1; //along row and column
            if (i != row)
                board[i][col] = 1;
        }
        int r = row;
        int c = col;
        r++;
        c--;
        while (r <= 7 && c >= 0)
            board[r++][c--] = 1;//along diagonal downwards left
        r = row;
        c = col;
        r--;
        c++;
        while (r >= 0 && c <= 7)
            //along diagonal upwards right
            board[r--][c++] = 1;
        r = row;
        c = col;
        r++;
        c++;
        while (r <= 7 && c <= 7)
            //along diagonal downwards right
            board[r++][c++] = 1;
        r = row;
        c = col;
        r--;
        c--;
        while (r >= 0 && c >= 0)
            // along diagonal upwards left
            board[r--][c--] = 1;
        //positions where  black horse can move
        row = blackHorse.row - 1;
        col = blackHorse.column - 65;
        r = row;
        c = col;
        if (r >= 2) {
            r = r - 2;
            if (c >= 1) {
                board[r][--c] = 1;
                c++;
            }
            if (c <= 6)
                board[r][++c] = 1;
        }
        c = col;
        r = row;
        if (r <= 5) {
            r = r + 2;
            if (c >= 1) {
                board[r][--c] = 1;
                c++;
            }
            if (c <= 6)
                board[r][++c] = 1;
        }
        r = row;
        c = col;
        if (c >= 2) {
            c = c - 2;
            if (r >= 1) {
                board[--r][c] = 1;
                r++;
            }
            if (r <= 6)
                board[++r][c] = 1;
        }
        r = row;
        c = col;
        if (c <= 5) {
            c = c + 2;
            if (r >= 1) {
                board[--r][c] = 1;
                r++;
            }
            if (r <= 6)
                board[++r][c] = 1;
        }
        board[blackMinister.row - 1][blackMinister.column - 65] = 1;
        board[blackHorse.row - 1][blackHorse.column - 65] = 1;
        // positions where white Minister can move
        row = whiteMinister.row - 1;
        col = whiteMinister.column - 65;
        for (int i = 0; i < 8; i++) {
            if (i != col && board[row][i] != 1)
                board[row][i] = 2;
            if (i != row && board[i][col] != 1)
                board[i][col] = 2;
        }
        r = row;
        c = col;
        r++;
        c--;
        while (r <= 7 && c >= 0) {
            if (board[r][c] != 1)
                board[r][c] = 2;
            r++;
            c--;
        }
        r = row;
        c = col;
        r--;
        c++;
        while (r >= 0 && c <= 7) {
            if (board[r][c] != 1)
                board[r][c] = 2;
            r--;
            c++;
        }
        r = row;
        c = col;
        r++;
        c++;
        while (r <= 7 && c <= 7) {
            if (board[r][c] != 1)
                board[r][c] = 2;
            r++;
            c++;
        }
        r = row;
        c = col;
        r--;
        c--;
        while (r >= 0 && c >= 0) {
            if (board[r][c] != 1)
                board[r][c] = 2;
            r--;
            c--;
        }
        board[row][col] = 0;
        List array = new ArrayList();
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (board[j][i] == 2) {
                    array.add(new ChessPosition((char) (i + 65), j + 1));
                }
            }
        }
        return array;
    }
}

class ChessPosition {

    char column;
    int row;

    public ChessPosition(char column, int row) {
        this.column = column;
        this.row = row;
    }

    @Override
    public String toString() {
        return column + "" + row;
    }
}

Review Comments

  1. The logic is lengthy and a bit confusing.
  2. There is lots of duplicate code, which could have been moved into methods.
  3. Could have created variables/constants for 0, 5, 6, 7, 8 etc

© meritcampus 2019

All Rights Reserved.

Open In App