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)

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

          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:

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