Java solution to Codility NumberOfDiscIntersections problem (Lesson 6 – Sorting) which scored 87%. The problem is to determine whether a triangle can be built from a given set of edges. The strategy is:
- create an ordered array of circles, each circle consisting of (leftmost x, rightmost x)
- have a custom java.util.Comparator to order the Circles based on where their radius starts and stops
- check intersection by comparing rightmost x with leftmost x of next element
References
How to use Comparator in Java to sort (Stack Overflow)
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class NumberOfDiscIntersections {
public int solution(int[] A) {
List aList = new ArrayList();
for(int i=0; i<A.length; i++) {
//need explicit cast to long on right side for case when A[i] is Integer.MAX_VALUE and adding would cause overflow
long leftMost = i - (long) A[i];
long rightMost = i + (long) A[i];
aList.add(new Circle(leftMost, rightMost));
}
Collections.sort(aList, new CircleComparator());
Circle [] aOrderedCircles = new Circle[A.length];
int index = 0;
for(Circle circle : aList) {
aOrderedCircles[index++] = circle;
}
int intersections = 0;
for(int i=0; i<aOrderedCircles.length-1; i++) {
for(int j=i+1; j<aOrderedCircles.length; j++) { //check intersection by comparing rightmost x with leftmost x of next element if(aOrderedCircles[i].rightMostX >= aOrderedCircles[j].leftMostX) {
intersections++;
if(intersections > 10000000) return -1;
}
//as soon as don't find intersection, stop counting cause circles are ordered so all subsequent circles won't intersect
else break;
}
}
return intersections;
}
class Circle {
long leftMostX;
long rightMostX;
Circle(long pLeftMostX, long pRightMostX) {
leftMostX = pLeftMostX;
rightMostX = pRightMostX;
}
}
//reference: https://stackoverflow.com/questions/2839137/how-to-use-comparator-in-java-to-sort
class CircleComparator implements Comparator {
@Override
public int compare(Circle pCircle1, Circle pCircle2) {
if(pCircle1.leftMostX < pCircle2.leftMostX) return -1; //e.g. circle1 (-4, 6) < circle2 (-2, 9)
if(pCircle2.leftMostX < pCircle1.leftMostX) return 1; //e.g. circle2 (-4, 6) < circle1 (-3, 1)
if(pCircle1.rightMostX < pCircle2.rightMostX) return -1; //e.g. circle1 (-4, 3) < circle2 (-4, 6)
if(pCircle2.rightMostX < pCircle1.rightMostX) return 1; //e.g. circle2 (-4, 3) < circle1 (-4, 1)
return 0; //e.g. circle1 (-2, 2), circle2 (-2, 2)
}
}
}
TestNG test cases for this problem which all passed:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import org.testng.Assert;
import org.testng.annotations.BeforeTest;
import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;
import com.codility.lesson06.sorting.NumberOfDiscIntersections;
public class NumberOfDiscIntersectionsTests {
private NumberOfDiscIntersections solution;
@BeforeTest
public void setUp() {
solution = new NumberOfDiscIntersections();
}
@DataProvider(name = "test1")
public Object [][] createData1() {
return new Object [][] {
new Object [] { new int [] { 1, 5, 2, 1, 4, 0 }, 11 },
new Object [] { new int [] { 2, 1, 0, 4 }, 6 },
new Object [] { new int [] { }, 0 },
new Object [] { new int [] { 1 }, 0 },
new Object [] { new int [] { 1, 2147483647, 0 }, 2 },
};
}
@Test(dataProvider = "test1")
public void verifySolution(int[] pA, int pExpected) {
Assert.assertEquals(solution.solution(pA), pExpected);
}
}