Line passing the most number of points

Question

Given points on a two dimensional graph, find a line that passes the most number of points.

Any comments please?

import static org.junit.Assert.*;

import java.util.*;

import org.junit.*;

public class Solution {
  public class Point {
    double x_coord;

    double y_coord;

    public Point(double x, double y) {
      x_coord = x;
      y_coord = y;
    }
  }

  public class Line {
    // define line with two points
    Point p1;

    Point p2;

    public Line(Point a, Point b) {
      p1 = a;
      p2 = b;
    }
  }

  public Line maxLine(ArrayList<Point> points) {
    int cnt = 0;
    int maxL = 0;
    Line bestL = null;
    if (points.size() == 0) {
      return new Line(new Point(0, 0), new Point(1, 1));
    } else if (points.size() == 1) {
      return new Line(new Point(0, 0), points.get(0));
    } else if (points.size() == 2) {
      return new Line(points.get(0), points.get(1));
    } else {
      for (Point p1 : points) {
        for (Point p2 : points) {
          if (p1.x_coord <= p2.x_coord) {
            cnt = countPoints(p1, p2, points);
            if (cnt > maxL) {
              if (p1.x_coord == p2.x_coord && p1.y_coord <= p2.y_coord || p1.x_coord < p2.x_coord) {
                bestL = new Line(p1, p2);
              } else {
                bestL = new Line(p2, p1);
              }
              maxL = cnt;
            }
            // define line with left most and right most points
            // in case of equality, with bottom most left
            // with upper most right
            else if (cnt == maxL && p2.x_coord > bestL.p2.x_coord) {
              bestL = new Line(bestL.p1, p2);
            } else if (cnt == maxL && p1.x_coord < bestL.p1.x_coord) {
              bestL = new Line(p1, bestL.p2);
            } else if (cnt == maxL && p1.x_coord == bestL.p1.x_coord
                    && p1.y_coord < bestL.p1.y_coord) {
              bestL = new Line(p1, bestL.p2);
            } else if (cnt == maxL && p2.x_coord == bestL.p2.x_coord
                    && p2.y_coord > bestL.p2.y_coord) {
              bestL = new Line(bestL.p1, p2);
            }
          }
        }
      }
    }
    return bestL;
  }

  public int countPoints(Point p1, Point p2, ArrayList<Point> points) {
    int cnt = 0;
    if (p1.x_coord != p2.x_coord) {
      double slope = (p2.y_coord - p1.y_coord) / (p2.x_coord - p1.x_coord);
      for (Point p : points) {
        if (p.y_coord - p1.y_coord == slope * (p.x_coord - p1.x_coord)) {
          cnt++;
        }
      }
    } else {
      for (Point p : points) {
        if (p.x_coord == p1.x_coord) {
          cnt++;
        }
      }
    }
    return cnt;
  }

  @Test
  public void test_1() {
    ArrayList<Point> p = new ArrayList<Point>();
    p.add(new Point(0, 0));
    // System.out.println(maxLine(p).p1.x_coord + " " + maxLine(p).p1.y_coord + " "
    // + maxLine(p).p2.x_coord + " " + maxLine(p).p2.y_coord);

    assertEquals(0, maxLine(p).p1.x_coord, 0);
    assertEquals(0, maxLine(p).p1.y_coord, 0);

    assertEquals(0, maxLine(p).p2.x_coord, 0);
    assertEquals(0, maxLine(p).p2.y_coord, 0);
  }

  @Test
  public void test_2() {
    ArrayList<Point> p = new ArrayList<Point>();
    p.add(new Point(0, 0));
    p.add(new Point(0, 1));
    // System.out.println(maxLine(p).p1.x_coord + " " + maxLine(p).p1.y_coord + " "
    // + maxLine(p).p2.x_coord + " " + maxLine(p).p2.y_coord);
    assertEquals(0, maxLine(p).p1.x_coord, 0);
    assertEquals(0, maxLine(p).p1.y_coord, 0);

    assertEquals(0, maxLine(p).p2.x_coord, 0);
    assertEquals(1, maxLine(p).p2.y_coord, 0);
  }

  @Test
  public void test_3() {
    ArrayList<Point> p = new ArrayList<Point>();
    p.add(new Point(0, 0));
    p.add(new Point(1, 0));
    assertEquals(0, maxLine(p).p1.x_coord, 0);
    assertEquals(0, maxLine(p).p1.y_coord, 0);

    assertEquals(1, maxLine(p).p2.x_coord, 0);
    assertEquals(0, maxLine(p).p2.y_coord, 0);
  }

  @Test
  public void test_4() {
    ArrayList<Point> p = new ArrayList<Point>();
    p.add(new Point(0, 0));
    p.add(new Point(2, 0));
    p.add(new Point(1, 0));

    // System.out.println(maxLine(p).p1.x_coord + " " + maxLine(p).p1.y_coord + " "
    // + maxLine(p).p2.x_coord + " " + maxLine(p).p2.y_coord);

    assertEquals(0, maxLine(p).p1.x_coord, 0);
    assertEquals(0, maxLine(p).p1.y_coord, 0);

    assertEquals(2, maxLine(p).p2.x_coord, 0);
    assertEquals(0, maxLine(p).p2.y_coord, 0);
  }

  public static void main(String[] args) {
    Solution e = new Solution();
    ArrayList<Point> p = new ArrayList<Point>();
    e.test_1();
    e.test_2();
    e.test_3();
    e.test_4();
  }

}

Answer 1

This part of code is not just hard to follow, it is incorrect:

else if (cnt == maxL && p2.x_coord > bestL.p2.x_coord) {
    bestL = new Line(bestL.p1, p2);
} else if (cnt == maxL && p1.x_coord < bestL.p1.x_coord) {
    bestL = new Line(p1, bestL.p2);
} else if (cnt == maxL && p1.x_coord == bestL.p1.x_coord
        && p1.y_coord < bestL.p1.y_coord) {
    bestL = new Line(p1, bestL.p2);
} else if (cnt == maxL && p2.x_coord == bestL.p2.x_coord
        && p2.y_coord > bestL.p2.y_coord) {
    bestL = new Line(bestL.p1, p2);
}

Here is a unit test it fails:

final double DELTA = 1e-12;

public void testMaxLineWithSixPoints() {
    Solution solution = new Solution();
    ArrayList<Solution.Point> p = new ArrayList<>(Arrays.asList(
            solution.new Point(0, 0),
            solution.new Point(1, 0),
            solution.new Point(2, 0),
            solution.new Point(1, 1),
            solution.new Point(2, 1),
            solution.new Point(3, 1)
    ));
    Solution.Line line = solution.maxLine(p);
    assertEquals(1, line.p1.x, DELTA);
    assertEquals(1, line.p1.y, DELTA);
    assertEquals(3, line.p2.x, DELTA);
    assertEquals(1, line.p2.y, DELTA);
}

Your code returns a Line with Point(0, 0) and Point(3, 1), which contains only two points(while the correct answer is a Line with Point(1, 1) and Point(3, 1), which contains three points(or (0, 0), (2, 0)). I would recommend refactoring this piece of code to make it readable and correct:

1. I will start with refactoring the Point class. I will override the equals method and the compareTo method from the Comparable interface(I will also rename x_coord and y_coord to x and y).

   public class Point implements Comparable<Point> {
   
       double x;
       double y;
   
       public Point(double x, double y) {
           this.x = x;
           this.y = y;
       }
   
       @Override
       public boolean equals(Object o) {
           if (!(o instanceof Point))
               return false;
           Point p = (Point) o;
           return this.compareTo(p) == 0;
       }
   
       /**
        * Compares two Points first by their x coordinate and if they are
        * equal, by y coordinate.
        * @param p The other Point.
        * @return -1 if this is less than p, 0 if they are equal and 1 otherwise.
        */
       @Override
       public int compareTo(Point p) {
           int result = Double.compare(x, p.x);
           if (result != 0)
               return result;
           return Double.compare(y, p.y);
       }
   }
   

2. Now I can rewrite the part of code mentioned above:

   else if (cnt == maxL) {
       if (bestL.p1.compareTo(p1) > 0 || bestL.p2.compareTo(p2) < 0) {
           bestL = new Line(p1, p2);
       }
   }
   

   It looks much better now(and it passes the test)! The old version was incorrect because we can have several different lines with the same number of points on them and there is no guarantee that bestL.p1, bestL.p2, p1 and p2 lie on the same line(you can take look at the unit test I have shown above to understand it better).

The last thing: comparing doubles using == operator after performing arithmetic operations on them can be wrong due to the rounding errors(I refer to this part of code):

double slope = (p2.y_coord - p1.y_coord) / (p2.x_coord - p1.x_coord);
for (Point p : points) {
    if (p.y_coord - p1.y_coord == slope * (p.x_coord - p1.x_coord)) {
        cnt++;
    }
}

Answer 2

Just a couple of points on readability:

Naming

• You have unit tests, which is awesome. But they are not named very good. test_1 doesn't tell me anything about what it tests, or why it might fail. This might be ok if you only have 2 or 3 tests, but it will get very annoying very fast.
• I am generally all for long variable names, but x_coord doesn't say anything that x already does, so I would go with x. Additionally, camelCase is traditionally used in Java instead of snake_case.
• countPoints: What points? At least something like countPointsBetween would give a hint.
• p1, p2, p are a bit confusingly named. start, end, and current eg would be easier to distinguish.
• shortening variable names too much can reduce readability. I would change cnt to count or currentPointsCount, maxL to maxLineLength or maxPointsCount, and bestL to bestLine, or longest or longestLine.

Misc

• declare variables in as small a scope as possible (see eg cnt) to increase readability.
• I would probably add length as a field to Line (and possibly countPoints as a method), to avoid having both maxL and bestL in maxLine.

Answer 3

In addition to the comments made by Tim I wanted to suggest a few structural changes

} else if (points.size() == 2) {

this case will also be handled by the else section. (if your logic there works ofcourse but I am assuming that is a given since you post on codereview)

Your code for maxLine(ArrayList points) is nested 5 layers deep which is a strong indicator that it needs to be split up into sub methods. (see below)

Additionally I personally prefer early-out and continue rather than big if nesting. you use

if (p1.x_coord <= p2.x_coord) {
    // all the code
}

with nothing happening otherwise except go to the next iteration of the loop. you can do this also by:

if (p1.x_coord > p2.x_coord) {
    continue;
}
// all the code.

It is generally recommended not to exceed 1 continue statement in this, but it will avoid an entire level of nesting and it will let you know that for that specific case (points we're not interested in because p1.x > p2.x) we can stop reading as nothing else will happen.

I would suggest something like:

public Line maxLine(List<Point> points) {
    if (points.size() == 0) {
      return new Line(new Point(0, 0), new Point(1, 1));
    } else if (points.size() == 1) {
      return new Line(new Point(0, 0), points.get(0));
    } else if (points.size() == 2) {
      return new Line(points.get(0), points.get(1));
    } else {
      return calculateMaxLine(points);
    }
}

public Line calculateMaxLine(List<Point> points) {
    int cnt = 0;
    int maxL = 0;
    Line bestL = null;
    for (Point p1 : points) {
        for (Point p2 : points) {
            if (p1.x_coord > p2.x_coord) {
                continue;
            }
            cnt = countPoints(p1, p2, points);
            if (cnt > maxL) {
                if (p1.x_coord == p2.x_coord && p1.y_coord <= p2.y_coord || p1.x_coord < p2.x_coord) {
                    bestL = new Line(p1, p2);
                } else {
                    bestL = new Line(p2, p1);
                }
                maxL = cnt;
            }
            // define line with left most and right most points
            // in case of equality, with bottom most left
            // with upper most right
            else if (cnt == maxL && p2.x_coord > bestL.p2.x_coord) {
                bestL = new Line(bestL.p1, p2);
            } else if (cnt == maxL && p1.x_coord < bestL.p1.x_coord) {
                bestL = new Line(p1, bestL.p2);
            } else if (cnt == maxL && p1.x_coord == bestL.p1.x_coord
                && p1.y_coord < bestL.p1.y_coord) {
                bestL = new Line(p1, bestL.p2);
            } else if (cnt == maxL && p2.x_coord == bestL.p2.x_coord
                && p2.y_coord > bestL.p2.y_coord) {
                bestL = new Line(bestL.p1, p2);
            }
        }
    }    
}

Additionally try to avoid using ArrayList in your interfaces when List suffices.

Lastly (and this is rewritign further) I would suggest you create a separate method that finds the furthest points on the line and not call that inside your for loop. you do not need to recalculate this every single time.

assume you have a method

public Line findLongestLine(Line line, List<Point> points) {
    // which goes over the points that match the line and get the furthest points
}

then you can clean up your method further by doing the longest line part after deciding which line is best.

you'll end up with something like:

public Line calculateMaxLine(List<Point> points) {
    int maxL = 0;
    Line bestL = null;
    for (Point p1 : points) {
        for (Point p2 : points) {
            if (p1.x_coord > p2.x_coord) {
                continue;
            }
            int cnt = countPoints(p1, p2, points);
            if (cnt < maxL) {
                // ignore this line it's too short
                continue;
            }
            if (p1.x_coord == p2.x_coord && p1.y_coord <= p2.y_coord || p1.x_coord < p2.x_coord) {
                bestL = new Line(p1, p2);
            } else {
                bestL = new Line(p2, p1);
            }
            maxL = cnt;
        }
    }
    return findLongestLine(bestL, points)    
}

This way your code becomes easier to read

Also you don't need to declare cnt outside the loop, it is only used inside the loop.

One last statement, but this is a bit tricky and would have to be clearly documented:

if (p1.x_coord == p2.x_coord && p1.y_coord <= p2.y_coord || p1.x_coord < p2.x_coord) {
    bestL = new Line(p1, p2);
} else {
    bestL = new Line(p2, p1);
}

it can be argued that every line you define will always have x1 < x2 (and if the same, y1 < y2). This could be part of your system. you can incorporate this in the Line constructor then. any line you create with p1 and p2 would always order the p1,p2 this way.

this should be documented because if you do this then this:

Line l = new Line(p1, p2);
assert l.p1 == p1; // would potentially fail.

Again this can be by design if this must always be true. I'm writing this because if say you use this outside of this assignment and you create lines in 100 places, you don't want to write the if (...) else .... statement every time. If it is a requirement lines look a certain way you can either embed these rules in the constructor (universally true for the object) or in a factory method (true for any line created by factory)

something like

public Line createAscendingLine(Point p1, Point p2)

it entirely depends on how universal these rules are, but generally good to avoid repeating the same decision and embed it somewhere.

in your testcases I am missing testIfNull which verifies/enforces what happens if null is entered. This may sound finnicky but 2 years down the line someone might change a bit of code which suddenly changes this behaviour, etc, etc. I would suggest for any argument that should never be passed, throw an InvalidArgumentException (which is runtime) or assert it.

One very last comment: each of the additional helper methods I've introduced, can be tested separately using unit tests, as they only work on the arguments you supply them. This might be useful or it might be extra overhead, it depends on whether the methods will get used from more than 1 location. In this case I just use them to clean up code and move some code out of large for loops. in such a case I wouldn't write separate unit tests as the tests you have cover their logic. However if you end up using the same method from another location then they are independant methods (with a usefulness outside of the method you have testcases for) and need their own unit tests. This is ofcourse just an opinion but wanted to add that

Hope this helps.