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)

[cc lang="java" escaped="true"]
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)
		}
	}
}
[/cc]

TestNG test cases for this problem which all passed:

[cc lang="java" escaped="true"]
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);
	}	
}
[/cc]