Interfering channels

A harbour scanner listens on a list of frequencies. Two clash when they sit exactly one channel spacing apart, and the operator wants the number of clashing pairs before the boats sail.

The problem

The scanner is loaded with a list of channel numbers, in kilohertz. The same channel may appear twice, because two receivers can be tuned to it.

Two channels interfere when their numbers differ by exactly gap. Count the distinct pairs of channel numbers that interfere. A pair is unordered: 118 with 121 is the same clash as 121 with 118, counted once however many receivers sit on each number.

When gap is 0, a pair means one channel number carrying two or more receivers, which clash with each other. Such a channel contributes one pair, however many receivers it holds.

Input. channels — a list of integers, the channel numbers loaded, possibly with repeats and possibly empty. gap — a non-negative integer, the spacing that causes interference.

Output. An integer: how many distinct pairs of channel numbers interfere.

Example.

channels = [3, 1, 4, 1, 5], gap = 2   ->  2

The pairs are (1, 3) and (3, 5). Channel 1 appears twice, but 1 with 3 is still one pair, and 4 has neither 2 nor 6 to clash with.

A second example, with a gap of zero:

channels = [7, 7, 7, 2], gap = 0   ->  1

Channel 7 carries three receivers: one clashing channel number, not three pairs. Channel 2 is alone and contributes nothing.

Constraints.

• 0 <= len(channels) <= 10^4
• -10^7 <= channels[i] <= 10^7
• 0 <= gap <= 10^7

Hints

Approach

Brute force

Compare every channel against every other, collect the pairs that differ by gap, then deduplicate. That is n(n - 1) / 2 comparisons — about 50 million for a 10 000-entry scanner — plus the cost of removing repeats.

The insight

Fix one member of the pair and the other is determined — v and v + gap — so the question is one lookup per distinct channel number.

Build a count map over the channel numbers. For a positive gap, walk the distinct keys and count those v for which v + gap is also a key. Each pair is met once, at its lower member, so nothing needs deduplicating. For gap of 0 the same walk asks a different question of the same map — how many keys have a count of at least 2 — which is why the map stores counts, not just membership.

Algorithm

1. Build a count map from channel number to how many receivers hold it.
2. If gap is 0, return the number of keys whose count is 2 or more.
3. Otherwise set clashes = 0.
4. For each key v, if v + gap is also a key, add 1 to clashes.
5. Return clashes.

Complexity

Time O(n) — one pass to count, one over at most n distinct keys, each with an average-case constant-time lookup. Space O(n) for the map.

Solution

"""Interfering channels — count distinct value pairs a fixed gap apart with a count map."""

from collections import Counter


def solve(channels, gap):
    tally = Counter(channels)
    if gap == 0:
        # A zero gap needs the counts: membership of v + 0 is always true.
        return sum(1 for held in tally.values() if held > 1)
    # invariant: each pair is met once, at its lower member, so no dedup is needed.
    return sum(1 for number in tally if number + gap in tally)

TESTS = [
    (([3, 1, 4, 1, 5], 2), 2),
    (([7, 7, 7, 2], 0), 1),
    (([12, 15, 18], 3), 2),
    (([], 4), 0),
    (([4], 1), 0),
    (([1, 1, 3], 2), 1),
    (([-6, -3, 0, 3], 3), 3),
    (([8, 8, 9, 9], 0), 2),
]

Pitfalls

• Checking both v + gap and v - gap. Every pair is found from both ends: [12, 15, 18] with gap = 3 reports 4, not 2.
• Using a set and losing the zero case. With a plain set v + 0 is always present, so [7, 7, 7, 2] with gap = 0 reports 2, one per distinct channel.
• Counting index pairs instead of value pairs. Iterating the raw list answers 2 for [1, 1, 3] with gap = 2, because channel 1 is met twice.
• Indexing an array by channel number. Channel numbers may be negative, so an array indexed by them breaks where a map does not.

Variants

• Stamp album run — the same membership test with gap fixed at 1, chained rather than counted.
• Wristband tally — a count map whose counts are what the answer is built from.