# Perl Weekly Challenge 106: Maximum Gap

by Abigail

## Challenge

You are given an array of integers @N.

Write a script to display the maximum difference between two successive elements once the array is sorted.

If the array contains only 1 element then display 0.

### Examples

Input: @N = (2, 9, 3, 5)
Output: 4

Input: @N = (1, 3, 8, 2, 0)
Output: 5

Input: @N = (5)
Output: 0


## Solution

### Overview

The solution is pretty straight forward. After reading in the numbers, we have to sort the list of number. Then we iterate over the numbers, calculate the difference between the number and the previous number, and keeping track of the maximum.

We will be reading input from standard input, where each line contains a set of numbers, separated by white space. Each line is seen as a different challenge.

### Perl

We are iterating line by line over the input (<>), and splitting each line on whitespace (split). The resulting list is numerically sorted, and stored in an array (@N).

We're then finding all the differences between a number and the preceeding number using map, starting from the second number in the array. We use the max function from the module List::Util to get the maximum. If the input has just one number, the list of differences is empty; it that case, max returns undef. Hence the // 0, which means that in that case, we print 0.

use List::Util qw [max];
while (<>) {
my @N = sort {$a <=>$b} split;

say max (map {$N [$_] - $N [$_ - 1]} 1 .. $#N) // 0; }  Find the full program on GitHub. ### GNU AWK For our AWK solution, we turn to GNU AWK, the GNU implemenation of AWK. This implementation has the method asort, which takes an array, and sorts it. In AWK, the input is by default already split on whitespace, and available in the variables $1, $2, $3, .... The variable NF contains the number of fields the input has been split into. We can then iterate over the fields, and populate an array N.

Finding the maximum of the differences is done by iterating over the array.

{
#
# We don't have lexical variables, so we need to clear
# the array N in each iteration.
#
delete N

#
# Read in the data, and populate N
#
for (i = 1; i <= NF; i ++) {
N [i] = $i } # # Sort the array; for numeric values, this sorts numerically. # asort(N) # # Find the maximum of the differences. For a single element # array, the maximum will be 0. # max = 0 for (i = 2; i <= NF; i ++) { if (N [i] - N [i - 1] > max) { max = N [i] - N [i - 1] } } # # Print the result. # print max }  Find the full program on GitHub. ### Bash Bash does not have a sort function, so first point of business is the write one. We will write an implementation of a selection sort: function ssort() { for ((i = 0; i <${#N[*]}; i ++))
do for ((j = i + 1; j < ${#N[*]}; j ++)) do if ((N[j] < N[i])) then t=${N[$i]} N[$i]=${N[$j]]}
N[$j]=$t
fi
done
done
}


Note that bash doesn't have named function arguments, nor references, and only limited return values (integers 0 - 255). So, we're sorting an array named N in place. This sort has a worst case runtime of $$\mathcal{\Theta} (N^2)$$.

Once we have a sort function, the rest is simple:

while read -a N
do    ssort  # Sort the array N
#
# Find the maximum value
#
max=0
for ((i = 1; i < ${#N[*]}; i ++)) do if (((N[i] - N[i - 1]) > max)) then max=$((N[i] - N[i - 1]))
fi
done
#
# Print the maximum
#
echo \$max
done


Find the full program on GitHub.

### C

C lets us work hard. We start with a function which takes a string (char *) as input, extract the numbers from that string, and which populates an array with those numbers. The size of the array will be returned.

typedef long long number;
# define number_fmt "%lld"

/*
* Given a string, extract the numbers, and put them into an
* array. Return the number of extracted numbers.
*/
size_t extract_numbers (char * line, number ** list) {
/*
* First, calculate the number of numbers
*/
char * ptr = line;    /* Copy of line, so we don't modify line */
number num;           /* Number scanned                        */
int n;                /* Number of characters scanned          */
size_t c = 0;         /* Count of numbers scanned              */
number * numbers;     /* List of numbers to be created         */

while (sscanf (ptr, number_fmt "%n", &num, &n) == 1) {
ptr += n;
c ++;
}

/*
* Allocate memory for the array to be returned
*/
if ((numbers = (number *) malloc (c * sizeof (number))) == NULL) {
perror ("Malloc failed");
exit (1);
}

/*
* Scan again, this time, populate the array.
*/
ptr = line;
c = 0;
while (sscanf (ptr, number_fmt "%n", &num, &n) == 1) {
ptr += n;
numbers [c ++] = num;
}
* list = numbers;
return (c);
}


To sort an array, C has a qsort, but that requires a comparison function. This function takes two void pointers as arguments — they point to the elements we want to compare. So, we first have to cast the pointers to pointers of the appropriate type, and then we can compare the numbers:

int num_compare (const void * p1, const void * p2) {
number n1 = * (const number *) p1;
number n2 = * (const number *) p2;
return n1 < n2 ? -1 : n1 > n2 ? 1 : 0;
}


Note that the compare function returns -1 if the first number is less than the second number; it returns 1 if the first number is larger than the second number; and it return 0 if the numbers are equal.

We are now ready for the main part of the C solution:

int main (void) {
char *  line  = NULL;
size_t  len   = 0;
size_t  str_len;

/*
* Read a line of input
*/
while ((str_len = getline (&line, &len, stdin)) != -1) {
/*
* Extract the numbers from the line of input, putting
* them in an array N; n will be the number of numbers in N.
*/
number * N = NULL;
size_t   n = extract_numbers (line, &N);

/*
* Sort the array.
*/
qsort (N, n, sizeof (number), num_compare);

/*
* Find the maximum
*/
number max = 0;
for (size_t i = 1; i < n; i ++) {
if (N [i] - N [i - 1] > max) {
max = N [i] - N [i - 1];
}
}

/*
* Print it
*/
printf (number_fmt "\n", max);

/*
* Free the used memory for the array of numbers.
*/
free (N);
}
free (line);

return (0);
}


Find the full program on GitHub.

### Lua

The Lua implemenation is pretty straightforward:

for line in io . lines () do
--
-- Extract the numbers from the line of input
-- Note that gmatch() doesn't return an array or list;
-- we have to iterate over it, and construct an array
--
local numbers = {}
for i in line : gmatch ("(%S+)") do
numbers [#numbers + 1] = i
end

--
-- Sort it; the default sort is numerical
--
table . sort (numbers)

--
-- Find the max difference
--
local max = 0
for i, n in ipairs (numbers) do
if (i > 1 and (numbers [i] - numbers [i - 1]) > max)
then max = numbers [i] - numbers [i - 1]
end
end

--
-- And print it
--
print (max)
end


Find the full program on GitHub.

### Node.js

Using Node.js, we can write a program which is basically a single statement. We're using the readline module, which gives a call back on each line read.

In this call back, we split the given line on whitespace, and then we numify each chuck by using the unary + operator.

We then sort the array, and use reduce to find the maximum of the differences.

require ('readline')
. createInterface ({input: process . stdin})
. on ('line', _ => console . log (
_ . split  (/\s+/)                // Split on white space
. map    (_ => +_)              // Numify
. sort   ()                     // Sort
. reduce ((max, _, i, N) => {   // Find max difference
return i > 0 && (N [i] - N [i - 1]) > max
? (N [i] - N [i - 1]) : max
}, 0)))


Find the full program on GitHub.

### Python

Python makes life easy, although it requires an explict cast from string to integers.

import fileinput

for line in fileinput . input ():
#
# Extract the numbers from the line of input, by splitting
# the input on white space, and forcing the chucks to be integer.
#
N = list (map (lambda x: int (x), line . split ()))

#
# sort () modifies the array
#
N . sort ()

#
# Find the maximum difference
#
max = 0
for i in range (1, len (N)):
if N [i] - N [i - 1] > max:
max = N [i] - N [i - 1]

#
# Print it
#
print (max)


Find the full program on GitHub.

### Ruby

Nothing special in Ruby either. The also need an explicit cast from string to integer.

ARGF . each_line do |_|
#
# Split input on white space, turn the chucks into integers,
# then sort the result.
#
n = (_ . split (/\s+/))
. map {|_| _ . to_i}
. sort

#
# Find the maximum difference.
#
max = 0
n . each_index {|i|
if i > 0 && (n [i] - n [i - 1]) > max
then max = n [i] - n [i - 1]
end
}

#
# And print it
#
puts (max)
end


Find the full program on GitHub.