Codility numberOfDiscIntersections javascript

numberOfDiscIntersections.js

function generateTestData(numArrayItems, minVal, maxVal, random){
    return Array.from(Array(numArrayItems)).map((e,i) => {
        if (random) {
            return getRandomInt(minVal, maxVal);
        }
        return i + minVal;
    });
}

function getRandomInt(min, max) {
    return Math.floor(Math.random() * (max - min + 1)) + min;
}

const testCases = [
    {
        description: 'Extreme Single',
        A: [1],
        expectedResult: 0
    },
    {
        description: 'Duplicates',
        A: [2, 2],
        expectedResult: 0
    },
    {
        description: 'Extreme Double',
        A: [2, 1],
        expectedResult: 1
    },
    {
        description: 'No intersections',
        A: [0, 0],
        expectedResult: 0
    },
    {
        description: 'Example',
        A: [1, 5, 2, 1, 4, 0],
        expectedResult: 11
    },
    {
        description: 'Simple',
        A: [1,2,3,4],
        expectedResult: 6
    },
    {
        description: 'Large',
        A: generateTestData(50000, 0, 2000000000, true),
        maxRuntime: 950
    },
    {
        description: 'Extreme Large',
        A: generateTestData(100000, 0, 2000000000, true),
        maxRuntime: 950
    },
];

const runTestCases = false;

if (runTestCases) {
    // use some so it stops after first failure
    testCases.some(testCase => {
        const startTime = new Date().getTime();
        const result = solution(testCase.A);

        const endTime = new Date().getTime();
        const duration = endTime - startTime;

        if (testCase.maxRunTime && duration > testCase.maxRunTime) {
            console.log(`Fail! ${testCase.description} took too long to execute (${duration}).`);
            return true;
        }

        if (testCase.expectedResult) {
          if (result !== testCase.expectedResult) {
            console.log('FAIL', testCase, 'actual result:', result);
            return true;
          }
        }

        return false;
    });
}

// based on http://julienrenaux.fr/2015/04/27/codility-efficient-algorithm-solutions-in-javascript/#NumberOfDiscIntersections
// and https://codesays.com/2014/solution-to-beta2010-number-of-disc-intersections-by-codility/
function solution(A) {
    const numPoints =  A.length;
    let numIntersections = 0;
    let startAndEndPoints = A.map((currentDisc, i) => [i - A[i], i + A[i]]);
     
    // [[5,5], [0,4], [-4, 6]] => [[-4, 6], [0,4], [5,5]]
    startAndEndPoints = startAndEndPoints.sort((a,b) => a[0] - b[0]);
 
    for (let j = 0; j < numPoints; j++) {
        const discPoint = startAndEndPoints[j];
        const discEndPoint = discPoint[1];
        for (let k = j + 1; k < numPoints; k++){
            const comparisonDisc = startAndEndPoints[k];
            const comparisonStartPoint = comparisonDisc[0];
            if (comparisonStartPoint <= discEndPoint) {
                // comparison disc is within this disc's area
                numIntersections++;
                if (numIntersections >10000000){
                    return -1;    
                }
            } else {
                // all other discs will be further right than this disc
                break;    
            }
        } 
    }
    return numIntersections;
}

/**
Exploring data...
For scenario [1, 5, 2, 1, 4, 0], which points are covered?

-4: 1
-3: 1
-2: 1
-1: 2
0: 4
1: 4
2: 4
3: 4
4: 4
5: 3
6: 2
7: 1
8: 1

Total = 32. Num unique intersections = 11
Total without 1s = 17

For scenario [1,2,3,4], which points are covered?

-1: 4
0: 4
1: 4
2: 3
3: 3
4: 2
5: 2
6: 1
7: 1

Total = 24. Num unique intersections = 7
Total without 1s = 15.

*/