← Writing · Celebrity Golf

Project: Celebrity Golf

Connect two film people by naming movies — scored like golf.

  1. Par Is a Graph Property
  2. Offline validation

Par Is a Graph Property

Stroke metric, measured difficulty dial, par as a query result.

Six degrees of Kevin Bacon as a golf course: pair of film people, every film a stroke, fewest wins. Par, difficulty, valid shot, fair hole — each is a graph query.

Building the board

Four IMDb TSV dumps (title.basics, title.ratings, title.principals, name.basics) — ~1.5 GB compressed, principals ~90M rows — streamed with filters per pass, memory under 1 GB:

  • Movies only, no adult, year ≥ 1930, Documentary and Short excluded
  • ≥ 1,000 votes
  • Cast capped at 10 (billed roles)
  • Crew: directors, composers, cinematographers only
  • Films with fewer than two people dropped

Result: 45,904 films, 218,793 people, 598,198 typed edges (450,728 cast, 48,888 director, 50,936 composer, 47,646 cinematographer). Pickled adjacency — loads in seconds. Full graph is the generator.

Shipped course plays on graph_us: 6,081 films, 29,981 people, 79,639 edges. Admit rule: (English original ∧ ≥25,000 votes) or crossover fame (≥250,000 votes any language) — 6,044 + 37. Every connector in a valid chain has to be a film the player can name.

Stroke cost

Chain alternates person / film / person. Cost of [film, person, film, …, film] is (len + 1) / 2 — one stroke per film. BFS over person states, expanding person → films → people, with:

  • No immediate film reuse — arrival film can’t be departure film (zero-progress paths). Non-adjacent recurrence allowed.
  • Banned films — when generating non-ace routes, the search bans shared films that would be aces so those routes stay distinct.
  • Typed-route satisfaction as search state — (person, satisfied) so search finds a crew-typed route.

Ace = shared-film check before any search. Everything above is layers on one BFS.

FIG. 01

Stroke cost

Diagram of an alternating person-film chain with stroke accounting via (len+1)/2 and an ace as the one-stroke degenerate case
Each named film is one stroke. The chain alternates person / film / person; strokes = (len + 1) / 2. An ace is the shared-film case checked before search.

The difficulty dial, measured

Endpoints from a vote-ranked pool (people by summed film votes, min five films). Pool depth = how far down the fame curve tee/pin may sit. Full graph, 1,000 random pairs per pool: top-1,000 → 848 of 1,000 connect in two strokes; top-5,000 splits twos/threes; top-20,000 majority threes with 186 at four-plus.

FIG. 02

Difficulty dial: generator vs shipped board

Two rows of stroke-distribution histograms: full-graph pools at top 1,000, 5,000, and 20,000, and shipped graph_us pools below including a missing deep band
Pool depth sets distance. Top row: the full graph's three pools (labeled values measured, others illustrative). Bottom row: the shipped board, fully measured — the deep pool never appears.

On the shipped board: only 2,664 of 29,981 people clear the five-film bar, so pools of 5k/20k silently cap and return identical histograms. Measured (1,000 pairs, seed 7): top-1,000 → 53 aces / 878 twos / 69 threes; max depth → 16 / 681 / 302 / 1 — one four-stroke pair in a thousand, zero unreachable within six. Keeping connectors nameable prunes long-filmography obscurity that manufactures distance. A par-4 needs a bigger board or typed-route constraints that lengthen.

Playtesting: a hole ending on an unplaceable Bollywood actor failed when players couldn’t place the endpoint. Dial uses open/mid/deep bands by pool depth. Shipped board ~50 MB resident; BFS pair 24.5 ms median (p95 ~1.1 s on deep stragglers); generator-side only.

Top connectors across a thousand shortest chains: Hans Zimmer (20), Jerry Goldsmith (13), James Newton Howard (12), Danny Elfman (10) — five of top seven are composers despite composer edges ~8% of the graph. Concentration mild (Zimmer in 2% of chains).

Film IDs

Early hole data keyed films by title string. Playtest surfaced Flatliners — two films, 1990 and 2017, disjoint casts. Title-as-key merged them → chains no single film satisfies. Fix: tconst everywhere; titles display as “Title (YEAR)”. Same-titled different-cast pairs are a queryable pattern — the doppelgänger hole.

Par as a property

Par is a BFS result. Difficulty is a histogram. Hole validity is a two-route existence check. Shot legality is membership in a shortest-path closure. Fairness is a vote floor at ingest.

Offline validation

Three tiers of static JSON — legality, plausibility, existence — and a course audit that caught a wrong par.

Free-shot needs “was that film a legal stroke?” instantly, in the client. Answer ships in the bundle.

Hole generation emits validChains: ace check, shortest co-star chains (enumerated, capped, reduced to ≤10 per route by signature), plus one crew-typed route when ≤ co-star length. Hole needs ≥2 routes or it’s rejected. Shortest-path closure: nine holes, 71 KB in puzzle.ts, typical hole under 8 KB, chain data ~4.6 KB. Client flattens chains into a candidate set; named film either advances surviving chains or doesn’t.

FIG. 03

A shot filters surviving chains

Diagram of named-film shots advancing matching validChains and pruning the rest, with the shortest-path closure as the correctness set
A named film advances matching chains and prunes the rest. Correctness is the shortest-path closure — orders of magnitude smaller than the typeahead index.

Three tiers of static JSON, each precomputed offline, each loaded at the narrowest scope its question needs:

Legality — validChains, ~4.6 KB/hole, in the bundle. Shortest-path closure. Only tier consulted to score a shot.

Plausibility — per-hole move bundles, 48–273 KB, lazy-loaded. Tee’s filmography plus from[filmId] (cast-sharing neighbors of every reachable film) → graph-aware suggestions. Failed load fails visibly — an earlier fallback to the global dictionary hid broken loads as bad suggestions.

Existence — letter shards, ~348 KB for ~6,000 titles. Global dictionary, split by first normalized letter (a.json…z.json, _ for digits), rows [normalized, title, year, votes] sorted for binary-search prefix lookup. One shard per query.

FIG. 04

Prefix lookup over static shards

Diagram of prefix lookup over letter-sharded static JSON title dictionaries, with a growth path to budget-split B-plus-tree cuts
One shard fetch, then binary search. Rows are sorted; the cut points are the index. Bottom band: same structure with byte-budget cuts when letters get too big.

Upgrade path: one globally sorted row list, cut wherever a chunk exceeds a byte budget, cut points as strings in the manifest (m1 covering ["m", "mid"), …) — B+-tree of depth one. Client delta: firstChar → manifest.floor. Current size: 348 KB total, mean shard ~13 KB (~4 KB gzipped); fetch cost is RTT. Full-graph dictionary (~45.9k titles, ~2.6 MB) is when letter shards blow open.

Today move bundles filter suggestions; validChains alone decides legality. → Address space on What Year Is It?

Same closure audits the course. Recomputing unrestricted shortest paths against the shipped board verified eight of nine pars — and caught hole 8 claiming par 3 where the board says 2. graph_us ⊂ full graph, so distances can only lengthen; a 2 here means the stated par was never the true shortest. Left uncaught: a player naming the real two-stroke path would have a correct solution scored as a whiff (not in validChains). Cause: build_hole took the first typed crew route (composer, three strokes) and never checked the cinematographer route — The Boss → Julio Macat → Miracle on 34th Street, two strokes. Generator now selects the shortest typed route; hole 8 ships as par 2; course total par 20 → 19.