Trailhead campsites

A walking app lists the campsites around a trailhead. The hiker sets three filters at once and expects the survivors back in the app's own order, best first.

The problem

Each campsite is one record: an id, a score out of ten that walkers have voted on, a flag for whether the site has a drinking-water tap, the nightly fee, and the walk in from the trailhead in minutes.

The hiker sets three filters together. water_only is 1 when only sites with a tap should be shown and 0 when the tap does not matter. max_fee and max_distance are caps, and a site sitting exactly on a cap still counts as inside it.

Return the ids of the sites that survive, ordered by score from high to low. Two sites on the same score are ordered by id from high to low as well, because the app treats a larger id as a newer listing and shows newer listings first.

Input. sites — a list of [site_id, score, has_water, fee, minutes], all integers, has_water either 0 or 1. water_only — 0 or 1. max_fee and max_distance — integer caps.

Output. A list of ids in the order described.

Example.

sites = [[41, 4, 1, 22, 6],
         [17, 8, 0, 14, 3],
         [63, 8, 1, 30, 2],
         [58, 5, 1, 12, 9]]
water_only = 1, max_fee = 25, max_distance = 8   ->  [41]

Site 17 has no tap. Site 63 costs 30 against a cap of 25. Site 58 is a nine-minute walk against a cap of eight. Only 41 clears all three.

A second example, the same sites with the filters relaxed:

water_only = 0, max_fee = 30, max_distance = 9   ->  [63, 17, 58, 41]

water_only = 0 does not mean "no tap" — it means the tap is irrelevant, so every site is still in play. Sites 63 and 17 both score 8, and 63 comes first because the tie goes to the larger id.

Constraints.

• 1 <= len(sites) <= 10^4
• ids are distinct, 1 <= site_id <= 10^5
• 1 <= score <= 10
• 0 <= fee <= 10^5 and 0 <= minutes <= 10^5
• has_water and water_only are each 0 or 1

Hints

Approach

Brute force

Filter with one pass, then build the order by repeatedly scanning the survivors for the best remaining record and removing it: m passes over m survivors, about m²/2 comparisons, 50 million at m = 10,000. The other common attempt is to sort twice — by id, then by score — leaning on stability. That is correct in exactly one of the two possible orders and silently wrong in the other.

The insight

A multi-level order is one key, not several sorts: a tuple compares left to right, and negating a numeric field flips that field alone.

The precondition a sort key needs is that the key values order the way the answer should — and here both levels are integers, so (-score, -site_id) reproduces the rule exactly, with the second component consulted only when the first ties. Writing the direction into the key rather than into reverse keeps the two levels independent, so a rule like "score down, id up" is a one-character edit rather than a redesign.

Algorithm

1. Keep a site when has_water >= water_only, fee <= max_fee and minutes <= max_distance.
2. Sort the survivors by the key (-score, -site_id).
3. Return their ids in that order.

Complexity

Time O(n log n) — one linear filtering pass, then a sort of at most n survivors. Space O(n) for the survivors and the list of ids.

Solution

"""Trailhead campsites — filter on three rules, then sort by one tuple key."""


def passes(site, water_only, max_fee, max_distance):
    """A site clears all three filters; both caps are inclusive."""
    _, _, has_water, fee, minutes = site
    # water_only == 0 means "the tap is irrelevant", so the test is >=, not ==.
    return has_water >= water_only and fee <= max_fee and minutes <= max_distance


def solve(sites, water_only, max_fee, max_distance):
    kept = [s for s in sites if passes(s, water_only, max_fee, max_distance)]
    # Both levels of the order run downward, so both parts of the key are negated;
    # reverse=True could not do this if one level ran the other way.
    kept.sort(key=lambda s: (-s[1], -s[0]))
    return [s[0] for s in kept]


SITES = [[41, 4, 1, 22, 6], [17, 8, 0, 14, 3], [63, 8, 1, 30, 2], [58, 5, 1, 12, 9]]

TESTS = [
    ((SITES, 1, 25, 8), [41]),
    ((SITES, 0, 30, 9), [63, 17, 58, 41]),
    ((SITES, 1, 22, 6), [41]),          # site 41 sits exactly on both caps
    ((SITES, 1, 5, 1), []),             # nothing survives the filter
    (([[9, 3, 0, 0, 0]], 0, 0, 0), [9]),
    (([[3, 7, 1, 4, 4], [9, 7, 1, 4, 4], [5, 7, 1, 4, 4]], 0, 10, 10), [9, 5, 3]),
]

Pitfalls

• Reading water_only = 0 as "must have no tap". In the second example that returns [17] instead of all four sites. The test is has_water >= water_only: a 0 filter admits both flags, a 1 filter admits only 1.
• Using (-score, site_id). The tie also runs downward. That key answers the second example [17, 63, 58, 41] — right set, wrong order, and the failure is invisible until two sites share a score.
• Making the caps strict. fee < max_fee drops site 41 when max_fee is exactly 22, and the first example turns into an empty list.

Variants

• Letterpress tray — a two-level key whose second level runs the opposite way to its first.
• Order as a key — the lesson behind this one: why the key runs once per element and a comparator does not.