CodinGame - Javascript Solution to Network Cabling problem

Print

This is a Javascript implementation for the "Network Cabling" problem given on the second CodinGame challenge.

The article is the third in a series that I started with the goal of testing the feasibility of solving CodinGame challenges in Javascript. You can also check out the first and second solutions that I posted earlier.


main();

function main()
{
    var n = readline();

    // will store all coordinates in an array
    var coords = [];

    // read and store each coordinate-pair in the coords array
    for (var i = 0; i < n; i++) {
        var xy = readline().split(' ');
        
        coords.push({X: parseInt(xy[0]),
                     Y: parseInt(xy[1])});

    }
    
    // get the result by calling 'solve' on the coords array
    var result = solve(coords);
    
    // print the result (the minimum length of cable required to connect all buildings)
    print(result);
}

function solve(coords)
{
    var minX = coords[0].X;
    var maxX = coords[0].X;
    
    var avgYBase = 0;
    

    // find the left-most house, and the right-most house (minX, maxX)
    // and compute the average vertical point for all houses
    for (var i = 0; i < coords.length; i++) {
        if(coords[i].X > maxX)
            maxX = coords[i].X;
        if(coords[i].X < minX)
            minX = coords[i].X;
        avgYBase += coords[i].Y;
    }
    
    // divide by number of houses to get the average vertical point (avg)
    var avg = Math.floor(avgYBase / coords.length);
    
    // because the coordinates are integers the average may be a floating point value
    // so we need to consider both integers around the average value
    var lenLow = 0;
    var lenMid = 0;
    var lenHigh = 0;
    
    for (var i = 0; i < coords.length; i++) {
        lenLow += Math.abs(coords[i].Y - (avg - 1));
        lenMid += Math.abs(coords[i].Y - avg);
        lenHigh += Math.abs(coords[i].Y - (avg + 1));
    }
    
    // the minimum will be one of the three values (plus the length of horizontal cable)
    return (maxX - minX) + Math.min(Math.min(lenLow, lenHigh), lenMid);
}

On the face of it the problem seemed straight-forward enough: since all coordinates are integer values the vertical location that minimizes the amount of cable required will be the one that is as close as possible to all buildings. Intuitively this is the average vertical coordinate. The only catch is that since the coordinates are all integers, and the answer is supposed to be an integer value as well, we'd have to consider both integer points closest to the real average value.

This results in a nice O(n) solution that computes the minimum and maximum horizontal coordinates, as well as the average vertical point. Another linear pass gives the final value.

The original problem statement can be found on the CodinGame website.

is the founder of Donaq, a software development consulting company with a focus on mobility. You can find Mike on Google+ and on LinkedIn.
Design copyright (c) Miky Dinescu