# Codingame Solution: Network Cabling

## The Goal

## Rules

For each building, a dedicated cable will connect from the building to the main cable by a minimal path (North or South), as shown in the following example:

The minimum length will therefore depend on the position of the main cable.

## Solution

That's a really interesting problem. For the horizontal distance it's easy, we need to find the left- and rightmost points. For the vertical position, we need to find the best height of the cable to minimize the distances. Least squares can't minimize the problem, think of the case when 3 houses are on one height and only one house is astray. The option that works is the minimum of the absolute values, or Manhatten distance, instead of least squares. But how can we minimize this? Interesting question. So interesting, I wrote an own article about the derivation. It's was astonishing, that it's the median of the values, which minimizes the absolute values. So all we have to do is run a hopefully minimalistic median implementation to solve this problem quickly. Here is my attemtp:

var minX = Infinity, maxX = 0, ys = []; var minCable = 0; var N = readline() | 0; for (var i = 0; i < N; i++) { var inputs = readline().split(' '); var x = inputs[0] | 0; var y = inputs[1] | 0; maxX = Math.max(maxX, x); minX = Math.min(minX, x); ys.push(y); } ys.sort((a, b) => a - b); var m = N % 2 ? ys[N >> 1] : Math.floor((ys[(N >> 1) - 1] + ys[N >> 1]) / 2) for (var i = 0; i < N; i++) { minCable+= Math.abs(ys[i] - m); } print(minCable + maxX - minX);

All images are copyright to Codingame