Consecutive van runs

Every parcel in the depot is stamped with the day it is due. A van run covers a block of days in a row and carries one parcel for each of them, so either the whole stack splits into runs or the morning does not work.

The problem

A courier depot sorts the morning's parcels by due day. Day numbers count from the start of the year, and several parcels can carry the same stamp.

A van run is a block of exactly k consecutive day numbers holding one parcel per day: [12, 13, 14] is a run of three, and so is [13, 14, 15]. Two runs may both cover day 13 as long as two parcels are stamped 13 — one rides on each van. What a run may never do is skip a day or carry two parcels for one day.

Every parcel leaves today or the morning fails. Decide whether the stack splits into runs of length k with nothing left behind.

Input. due_days — a list of integers, one per parcel, repeats allowed and in no particular order. k — the number of days one run covers.

Output. True if the whole stack splits into runs of k consecutive days, False otherwise.

Example.

due_days = [9, 11, 10, 12, 10, 11], k = 3   ->  True

Two runs: 9–10–11 and 10–11–12. Days 10 and 11 appear in both, which is fine because two parcels carry each of those stamps.

A second example, where the count divides but the days do not line up:

due_days = [3, 4, 5, 6, 8, 9], k = 3   ->  False

Six parcels and k = 3 means two runs. Day 7 has no parcel, so 3–4–5 is the only run that can start at 3, and it leaves 6, 8 and 9 — not three days in a row.

Constraints.

• 1 <= len(due_days) <= 10^5
• 1 <= due_days[i] <= 10^9 — the stamps are sparse, not a dense range
• 1 <= k <= len(due_days)

Hints

Approach

Brute force

Search. Pick a run for the smallest parcel, recurse on what is left, backtrack when the rest fails. The branching factor is k at each of the n/k steps, so even 30 parcels with k = 3 runs into millions of states.

The insight

The smallest unassigned day has no choice at all: it must be the first day of its run, because a run starting earlier would need a parcel on a day that no longer exists.

A run containing day d spans [s, s + k − 1] with s <= d. If s < d, that run wants a parcel stamped s, which is below the smallest remaining stamp, so there is none. So s = d, forced — and the argument applies again to whatever is left, which is why this greedy is not a heuristic that happens to work but the only assignment available at each step.

If c parcels share that smallest day, all c runs start there, so each of the next k − 1 days needs c parcels of its own. Deducting all c in one move is what keeps the work linear.

Algorithm

1. If len(due_days) % k != 0, return False.
2. Tally the days into counts.
3. Walk the distinct days in ascending order, letting c be the day's remaining count; skip the day when c is 0.
4. For each of d + 1 … d + k − 1, return False if it holds fewer than c parcels, otherwise subtract c from it.
5. Set day d to 0 and carry on. If the walk finishes, return True.

Complexity

Time O(n log n) — one pass to tally, O(d log d) to sort the distinct days, and k − 1 deduction steps once per run over n/k runs, so the deductions together are O(n). Space O(d) for the tally, d ≤ n being the number of distinct days.

Solution

"""Consecutive van runs — a forced greedy over a tally of due days."""

from collections import Counter


def solve(due_days, k):
    if len(due_days) % k:                 # every run is exactly k parcels
        return False
    tally = Counter(due_days)
    # sorted() is a snapshot: the tally is edited inside the loop.
    for day in sorted(tally):
        runs = tally[day]                 # the smallest open day can only start runs
        if runs == 0:
            continue
        for offset in range(1, k):
            # Each of those runs needs its own parcel on every following day.
            if tally.get(day + offset, 0) < runs:
                return False
            tally[day + offset] -= runs
        tally[day] = 0
    return True

TESTS = [
    (([9, 11, 10, 12, 10, 11], 3), True),
    (([3, 4, 5, 6, 8, 9], 3), False),
    (([5, 5, 6, 7, 7, 8], 3), False),      # two runs start at day 5, one parcel on day 6
    (([1, 2, 3, 4], 3), False),            # the stack does not divide into runs
    (([7], 1), True),
    (([4, 4, 4], 1), True),                # every stamp identical, runs of one
    (([999999999, 1000000000], 2), True),  # sparse day numbers, nothing to index
    (([1, 2, 3, 3, 4, 5], 3), True),
]

Pitfalls

• Sorting the parcels and cutting the sorted list into blocks of k. The first example sorts to [9, 10, 10, 11, 11, 12] and the leading block is 9, 10, 10, which is not consecutive, so this answers False where the truth is True. Equal days belong to different runs.
• Testing tally[d + i] > 0 instead of >= c. With due_days = [5, 5, 6, 7, 7, 8] and k = 3, two runs must start at day 5 but only one parcel is stamped 6. A "the day exists" test sees day 6 and answers True; the answer is False.
• Deducting from a defaultdict while iterating it. Touching tally[d + i] for a day nobody stamped inserts a zero key, and Python then raises RuntimeError: dictionary changed size during iteration. Iterate a sorted snapshot of the keys and read absent days with .get(day, 0).

Variants

• Letterpress tray — also collapses the input to a tally, but sorts the groups instead of consuming them in a forced order.
• Telescope night — another problem where putting the keys in ascending order is what removes the choices.