# NumberOfDiscIntersections – Codility – Solution

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)

```12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667package com.codility.lesson06.sorting;

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];

}

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:

```123456789101112131415161718192021222324252627282930313233package test.com.codility.lesson06.sorting;

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);
}
}

```