Horse-racing Duals

The aim of this puzzle is to find the minimum difference between 2 values a list. The difficulty lies in the length of the list, and the short time to do it. A "simple" solution is to first sort all the values efficiently enough, then compare all the differences between consecutive values.

C

To sort the powers, you could use your own sorting function instead of the standard C function qsort.

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>

/* compares the two integers pointed by e1 and e2, 
   returns -1 / 0 / 1, if e1 < / = / > e2 */ 
int comp (const void * e1, const void * e2) {
    int f = *((int*)e1);
    int s = *((int*)e2);
    if (f > s) return  1;
    if (f < s) return -1;
    return 0;
}

int main(int argc, char** argv)
{
    int N;
    scanf("%d\n", &N);
    int horses[N];
    for (int i = 0; i < N; i++)
        scanf("%d\n", horses+i);

    // Sorts the powers
    qsort(horses, N, sizeof(int), comp);
    
    int min = INT_MAX;
    int diff;
    for (int i = 0; i < N-1; i++) {
        diff = horses[i+1]-horses[i];
        if (diff < min)
                min = diff;
    }

    printf("%d\n", min);
    return EXIT_SUCCESS;
}

Java

Instead of reading all the powers then sorting them, you can also insert them in order in a sorted data structure, as I did in Java.

import java.util.*;

class Solution {
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        
        // TreeSet is one of Java's sorted data structure
        TreeSet<Integer> horses = new TreeSet<Integer>();
        for (int i = 0; i < N; i++)
            horses.add(in.nextInt());

        Iterator<Integer> it = horses.iterator();
        int curr, prev = it.next(); 
        int min = Integer.MAX_VALUE;
        while (it.hasNext()) {
            curr = it.next();
            if (curr-prev < min)
                min = curr-prev;
            prev = curr;
        }
        System.out.println(min);
    }
}

Python 3

Same algorithm as in Java, using bisect to insert a value in a sorted array (by the bisection method).

import bisect, sys

N = int(input())
horses = []
mini, diff = sys.maxsize, None

for i in range(N):
    bisect.insort(horses, int(input()))

for i in range(N-1):
    diff = horses[i+1] - horses[i]
    if diff < mini:
        mini = diff

print(mini)

Bash

I also did this one in Bash to unlock the third achievement. The tricky part is to sort the array containing the powers, but it becomes very easy if you're used to sort the lines of a file.

#!/bin/bash

read N
# reads all power values and store them in an array
for (( i=0; i<N; i++ ))
do
    read p
    power[$i]=$p
done

# sorts the array
power=($(for p in ${power[@]}; do echo $p; done | sort -n))

# at this point, power contains all the power sorted by increading order
# the result expected is the smallest difference between 2 consecutive values
min=9999999
for (( i=0; i<${#power[@]}-1; i++ ))
    do
        current=${power[$i]}
        next=${power[$i+1]}
        diff=$(( next - current))
        if [ $diff -lt $min ]
        then
            min=$diff
        fi
    done

echo $min