The Salesman in a Rush

You are a salesman and your goal is to visit all the houses along a certain street.

You walk at a constant rate and can start and end at any location. You may visit the houses in any order you wish. Given the locations of the houses along the street, what is the minimum amount of time needed for you to visit all the houses?

Formally, we represent the street as a number line and the positions of the houses as numbers along this line.

There are $n$ houses numbered $1,2…,n$ and they are located at c(x_1\), respectively. Assume that it takes $0$ (negligible) time to visit a house, and walking from house $i$ to house $j$ takes $|x_i-x_j|$ minutes.

Complete the function minimumTime which takes an integer array , denoting the locations of the houses as input. Return an integer denoting the minimum amount of time, in minutes, needed to visit all the houses.

Input Format

he first line contains a single integer $t$ denoting the number of streets. The description of $t$ streets follow.

Each street is described by two lines. The first line contains a single integer $n$ denoting the number of houses in that street. The second line contains $n$ integers $x_1,x_2,…,x_n$ denoting the locations of the houses along the street.

Constraints

$1\leqslant t \leqslant 500$
$1\leqslant n \leqslant 50$
$1\leqslant x_i \leqslant 1000$
The houses’ locations are distinct

Output Format

For each street, print a single line containing a single integer denoting the minimum amount of time, in minutes, needed to visit all the houses.

Example

Input:

Output:

1

5

Explanation:

In this case, there are $n=3$ houses at locations $x_1=11, x_2=6$ and $x_3=9$.

We can consider $6$ possible orders to visit the houses:

$1 \rightarrow 2 \rightarrow 3$. This will take $|11-6| + |6-9| = 8$ minutes.
$1 \rightarrow 3 \rightarrow 2$. This will take $|11-9| + |9-6| = 5$ minutes.
$2 \rightarrow 1 \rightarrow 3$. This will take $|6-11| + |11-9| = 7$ minutes.
$2 \rightarrow 3 \rightarrow 1$. This will take $|6-9| + |9-11| = 5$ minutes.
$3 \rightarrow 1 \rightarrow 2$. This will take $|9-11| + |11-6| = 7$ minutes.
$3 \rightarrow 2 \rightarrow 1$. This will take $|9-6| + |6-11| = 8$ minutes.

Solutions

The solution is simply the difference between the max and the min of the input array:

A C++ Solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


int t, n;
cin >> t;
vector<int> v;
while (t--)
{
    cin >> n;
    v.resize(n);
    copy_n(istream_iterator<int>(cin), n, begin(v));
    auto mm = minmax_element(begin(v), end(v));
    cout << (*mm.second-*mm.first) << "\n";
}

The same in Python:

1
2
3
4


for cas in xrange(input()):
    raw_input()
    a = map(int, raw_input().strip().split())
    print max(a) - min(a)

Haskell:

1
2
3
4
5
6
7
8
9


-- Algorithm
min_dist :: [Int] -> Int
min_dist houses = maximum houses - minimum houses

-- I/O and parsing
filter_only_needed_lines xs = [ x | (i, x) <- zip [0..] (tail xs), odd i ]
main = interact $ unlines
                . fmap (show . min_dist . fmap read . words)
                . filter_only_needed_lines . lines

Rust:

1
2
3


fn min_dist(houses: &[u32]) -> u32 {
    houses.iter().max().unwrap() - houses.iter().min().unwrap()
}

One can easily fall into the trap of following the example by calculating the adjacent differences of the sorted array. That’s more expensive but it’s a valid solution too.

Here is a succinct example in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


int t, n;
cin >> t;
vector<int> v;
while (t--)
{
    cin >> n;
    v.resize(n);
    copy_n(istream_iterator<int>(cin), n, begin(v));
    sort(begin(v), end(v));
    cout << inner_product(
    		next(begin(v)), end(v), 
    		begin(v), 0, plus<>{}, minus<>{}) << "\n";
}

The pattern here is zip | map | reduce, that is: we zip the array with itself by shifting it by 1, we map every pair by calculating the difference (it’s always positive because the array is sorted in ascending order) and we reduce by aggregating the temporary results along the way.

1
2
3
4


fn min_dist(mut houses: Vec<usize>) -> usize {
    houses.sort();
    houses.iter().zip(houses.iter().skip(1)).map(|(&l, &r)| r - l).sum()
}

1
2
3
4


min_dist :: [Int] -> Int
min_dist houses = sum $ (\(l, r) -> r - l) <$> zip sorted (tail sorted)
  where
    sorted = sort(houses)

math