Maximise the minimum distance

Maximising the minimum distance means choosing k of n given positions so that the two closest chosen ones are as far apart as possible. The search does not try the choices. It guesses a gap d and asks whether k positions can be chosen with every gap at least d: after sorting, one walk from the left answers that, taking each position that is far enough from the last one taken. A smaller gap never makes placing harder, so “k fit with gap d” is true up to some d and false beyond it, and the last d that works can be binary searched. The problem below is an original take on the classic known as aggressive cows; a timed run shows what trying every choice would cost, and a short note names the signal.

The problem: spreading out fast chargers

1. sites = [48, 3, 95, 20, 61, 77, 12] and k = 4 give 18: chargers at 3, 48, 77 and 95, whose gaps are 45, 29 and 18.
2. The same sites with k = 2 give 92, the two ends of the highway.
3. sites = [5, 5, 5] and k = 2 give 0: two different sites at the same marker.

The brute force: try every choice of k sites

Sort the sites, try each of the C(n, k) choices of k of them, take each choice’s smallest gap, and keep the widest. It is a correct judge for small inputs, and the number of choices explodes:

"""The widest smallest gap, by trying every choice of k sites: the brute force, with its choices counted."""
import math
import time
from itertools import combinations


def widest_by_trying(sites, k):
    ordered = sorted(sites)
    best, choices = None, 0
    for chosen in combinations(ordered, k):  # each choice comes out in sorted order
        gap = min(b - a for a, b in zip(chosen, chosen[1:]))
        best = gap if best is None else max(best, gap)
        choices += 1
    return best, choices


for sites, k in [([48, 3, 95, 20, 61, 77, 12], 4), ([48, 3, 95, 20, 61, 77, 12], 2), ([5, 5, 5], 2)]:
    best, choices = widest_by_trying(sites, k)
    print(f"k = {k}: {best} after {choices:,} choices")

sites = [(37 * i) % 1_000 for i in range(26)]
start = time.perf_counter()
best, choices = widest_by_trying(sites, 7)
per_choice = (time.perf_counter() - start) / choices
print(f"26 sites, 7 chargers: {choices:,} choices, about {per_choice * 1e6:.1f} microseconds each")


def duration(seconds):
    for unit, size in (("year", 365 * 86_400), ("day", 86_400), ("hour", 3_600), ("minute", 60), ("second", 1)):
        if seconds >= size or unit == "second":
            value = round(seconds / size)
            return f"about {value:,} {unit}{'' if value == 1 else 's'}"


for n, k in [(40, 10), (100, 10), (100_000, 50)]:
    count = math.comb(n, k)
    shown = f"{count:,} choices" if count < 10**15 else f"{len(str(count))}-digit number of choices"
    print(f"{n:,} sites, {k} chargers: {shown}, {duration(count * per_choice) if count < 10**30 else 'far longer than the age of the universe'}")

k = 4: 18 after 35 choices
k = 2: 92 after 21 choices
k = 2: 0 after 3 choices
26 sites, 7 chargers: 657,800 choices, about 1.3 microseconds each
40 sites, 10 chargers: 847,660,528 choices, about 18 minutes
100 sites, 10 chargers: 17,310,309,456,440 choices, about 251 days
100,000 sites, 50 chargers: 186-digit number of choices, far longer than the age of the universe

At a microsecond or more per choice, 40 sites and 10 chargers take minutes, 100 sites take months, and the stated limits are out of reach.

What to notice

Fix a gap d. If k chargers fit with every gap at least d, the same chargers have every gap at least any smaller d, so “k fit with gap d” holds up to some d and fails beyond it: search for the last d that works. For one d, sort the sites, take the first, and walk along taking each site that is at least d past the last one taken; k fit when the walk takes at least k.

The widest gap by halving, step by step Pro: opens with a Pro, Premium or Ultimate pass