The period in a sighting ledger

An observatory ledger records the years a faint object was seen. If one object in there is periodic, its sightings are evenly spaced and the rest are noise.

The problem

The ledger years lists, in chronological order, every year in which a faint object was logged from one observatory. The years strictly increase: at most one entry per year. Most entries are unrelated objects, and the archivist wants the strongest case for a single periodic one.

That case is the longest set of ledger entries whose years are evenly spaced — one fixed gap between each entry and the next. The entries need not be neighbours; the ones in between are attributed to something else. Report how many entries the longest such set holds. Any two entries are trivially evenly spaced, so a ledger of two or more never answers less than 2.

Input. years — a strictly increasing list of integers.

Output. The number of entries in the longest evenly spaced set.

Example.

years = [1907, 1912, 1919, 1921, 1926, 1935, 1940, 1954]   ->  4

1912, 1926, 1940 and 1954 are 14 years apart each. The 1919, 1921 and 1935 entries fall between them and belong to something else.

A second example, where the whole ledger lines up:

years = [1811, 1820, 1829, 1838, 1847, 1856]   ->  6

A gap of 9 throughout. Note that a gap of 18 also works, on three entries — the longest wins, not the first one found.

Constraints.

• 1 <= len(years) <= 1000
• 1600 <= years[i] <= 2400
• years is strictly increasing

Hints

Approach

Brute force

Fix the first two entries, which pins the gap, then walk forward taking every year that continues the spacing. That is n^2 / 2 starting pairs and an n-step walk each — 5 x 10^8 lookups at n = 1000, re-walking the same partial chains over and over.

The insight

Make the gap part of the state: the longest evenly spaced set ending at entry j with gap d is one longer than the same answer at the entry d years earlier.

Chop the last entry off an evenly spaced set and what remains is one too, with the same gap, ending at the previous entry. Hang a small map from gap to length off each entry and fill entries left to right: every answer is final before it is read. Because the years strictly increase, a gap and an endpoint pin down exactly one predecessor, so nothing is counted twice.

Algorithm

1. If the ledger has fewer than three entries, return its length.
2. Give each entry an empty map from gap to run length.
3. For each j, and each earlier i, let gap = years[j] - years[i].
4. Set runs[j][gap] to runs[i].get(gap, 1) + 1 — the 1 is entry i standing alone.
5. Track the largest value written, starting from 2.

Complexity

Time O(n^2) — one map write per ordered pair, a million of them at the top of the range. Space O(n^2) in the worst case: each entry can carry up to n - 1 distinct gaps.

Solution

"""Reading a period out of the ledger — dynamic programming over pairs, keyed by the gap."""


def solve(years):
    """Length of the longest evenly spaced subsequence of sighting years."""
    n = len(years)
    if n < 3:
        return n
    # runs[j][gap] = how many sightings are in the longest evenly spaced
    # subsequence that ends at year j and steps by exactly gap. Every such
    # subsequence has a second-to-last entry, so it is built from an earlier
    # answer with the same gap.
    runs = [dict() for _ in range(n)]
    longest = 2
    for j in range(n):
        for i in range(j):
            gap = years[j] - years[i]
            runs[j][gap] = runs[i].get(gap, 1) + 1
            if runs[j][gap] > longest:
                longest = runs[j][gap]
    return longest

TESTS = [
    (([1907, 1912, 1919, 1921, 1926, 1935, 1940, 1954],), 4),
    (([1901, 1902, 1904, 1908],), 2),
    (([1811, 1820, 1829, 1838, 1847, 1856],), 6),
    (([1900, 1950, 2000],), 3),
    (([1899, 1990],), 2),
    (([1899],), 1),
]

Pitfalls

• One shared map keyed by gap alone. [1900, 1910, 1930, 1940] then reports 3: the two 10-year pairs are counted as one chain, though nothing links them. The map has to hang off the endpoint.
• Defaulting the lookup to 2 instead of 1. runs[i].get(gap, 2) + 1 counts entry i twice, and [1900, 1950, 2000] comes back as 4 entries from a ledger with 3.
• Returning 1 or 0 for a short ledger. [1899, 1990] answers 2 — two entries are always evenly spaced. Only a one-entry ledger answers 1.

Variants

• Posts on an even grade — the same constant step on neighbours only, which collapses the state to one counter.
• Loudest run on the board — another "best thing ending here", with two carried numbers instead of a map.