Algorithmic Complexity of the Shared Lexical and Puzzle-Generation System¶

Status: Engineering reference for the Phase 4 implementation

Scope: Shared lexical catalog, catalog views, Letter Golf indexes and generation, and Reverse Cross indexes and generation

Out of scope: Network latency prediction, database request-unit pricing, and frontend rendering

Math rendering: Formulas use standard MathJax-compatible TeX with $...$ inline and $$...$$ display delimiters. A MkDocs host must enable those delimiters, commonly through pymdownx.arithmatex plus MathJax 3.

Abstract¶

The application pays for lexical content in layers. A language-scoped catalog build acquires and parses every registered source, normalizes and merges every record, applies moderation, sorts the accepted entries, hashes their complete canonical content, and publishes a new immutable snapshot. Game/profile/theme views then scan that snapshot and retain references to eligible entries. Letter Golf and Reverse Cross build different indexes over those views. Puzzle requests reuse those objects while their process-local caches remain warm.

This architecture makes warm membership checks and candidate retrieval efficient, but it deliberately does not provide incremental catalog mutation. A source or policy change affecting only $X$ entries still requires a complete rebuild of the affected language, followed by lazy reconstruction of each requested view and game index. During replacement, the previous immutable graph can coexist with the new build, so peak memory is more important than final retained size.

Reverse Cross fill remains exponential in the theoretical worst case. Positional postings, minimum-remaining-values (MRV) slot selection, deterministic ordering, and hard time/node/attempt limits reduce practical work and bound each production request; they do not change the underlying complexity class. Letter Golf uses a sparse count trie. Its exact lookup follows one signature path, while playable and hole-in-one searches are output-sensitive traversals whose worst case visits the complete trie.

Reading the Bounds¶

Unless noted otherwise:

Time bounds describe CPU work and exclude unpredictable remote transfer latency.
Space bounds describe additional live managed memory, not artifact bytes held by an external HTTP stack or operating-system buffers.
Dictionary and hash-set operations are $O(1)$ expected time. Adversarial collision behavior can degrade a table operation to $O(n)$, although .NET string hashing mitigates ordinary collision attacks.
Comparing or hashing a string of length $q$ is $O(q)$. Several keys in this system, such as SHA-256-derived entry IDs, have fixed bounded length; comparing those keys is effectively constant with respect to catalog size.
$O(V+Z)$ means output-sensitive work: $V$ is explored structure and $Z$ is returned results.
Bounds state what the current implementation does, including avoidable scans. They are not claims about an ideal implementation.
Small alphabets and 9x9 boards make some factors modest in practice, but the factors remain explicit so the analysis generalizes to other languages and board sizes.

Notation¶

Symbol	Meaning
$S$	Number of lexical sources registered for one language
$B$	Total bytes parsed from those sources
$R$	Total raw records emitted by those sources, including duplicates and later rejections
$Q_p$	Total decoded text/code-point work performed while parsing source records
$Q_n$	Total raw display-form text/code-point work performed by normalization
$N$	Unique accepted entries in a published language snapshot
$G$	Total accepted grapheme references, $\sum_{i=1}^{N} \ell_i$
$Y$	Total UTF-8 byte volume of accepted canonical fields consumed by identity/version hashing
$P_r$	Total accepted source-reference associations across merged entries
$T_g$	Total accepted tag associations across merged entries
$V$	Number of entries in one catalog view
$G_V$	Total grapheme references in that view
$E_V$	Total source/tag/score associations inspected while evaluating one view
$A$	Number of distinct grapheme units represented in a frequency table
$d_i$	Number of distinct grapheme units in word $i$
$K$	Number of nodes in a Letter Golf sparse count trie
$Z$	Number of results returned by a query
$C$	Number of Reverse Cross cells, $rows \times columns$
$L$	Number of Reverse Cross slots in one mask
$\ell_i$	Grapheme length of word or slot $i$
$D_\ell$	Number of indexed Reverse Cross entries of length $\ell$
$P_i$	Size of the smallest applicable positional posting for slot $i$
$J$	Search nodes actually visited by bounded Reverse Cross backtracking
$M$	Number of mask candidates attempted
$X$	Number of source or policy entries changed by an update

The symbols are local to a language, snapshot, or request as appropriate. For example, $N_{es}$ and $N_{en}$ are independent Spanish and English catalog sizes.

Layer and Ownership Model¶

The retained object graph is layered as follows:

flowchart LR
    Sources[Language sources] --> Snapshot[Immutable language snapshot]
    Policy[Normalizer and content policy] --> Snapshot
    Snapshot --> ViewA[Game/profile/theme view]
    Snapshot --> ViewB[Another view]
    ViewA --> LG[Letter Golf count trie and frequencies]
    ViewB --> RC[Reverse Cross length buckets and postings]
    RC --> Fill[Bounded mask fill]
    LG --> Puzzle[Letter Golf generation and validation]

The snapshot owns LexicalEntry objects and one LexicalMetadataRegistry. Production entries store a source bitmask, sparse source-ordinal scores, and sorted category IDs instead of cloning source-reference objects and per-entry tag sets. Language, source descriptors, score scales, and category strings are resolved through the registry. Views and game indexes retain entry references, so any live view or game index also keeps its complete source snapshot and registry alive.

All caches discussed here are in-process singleton state. They are neither distributed nor persisted. In a deployment with $p$ replicas, each replica can independently pay cold-build cost and retain approximately the same catalog/view/index memory. A restart makes that replica cold again.

Shared Lexical Catalog¶

Acquisition and parsing¶

Each current pinned HTTP source obtains one HTTPS response and asks its source-specific parser to return a materialized IReadOnlyList<RawLexicalEntry> before yielding records to the catalog builder. The HTTP client permits at most three attempts, so retry count is bounded independently of input size.

For parsers that inspect the complete payload, acquisition and parsing require:

\[ T_{source} = O(B + Q_p + R) \]

The distinction between $B$ and $Q_p$ matters for Unicode and structured formats: input bytes, decoded text, and emitted records need not have equal sizes. Source-specific parser choices determine the exact transient space. The common lower bound is $\Omega(R)$ for the returned record list; a parser that materializes a complete JSON object can retain additional $O(B)$ decoded/parser state.

Sources are consumed sequentially by WordCatalogBuilder. Consequently, the aggregate mutable catalog overlaps with at least the current source's materialized result. Sequential processing avoids retaining every source list simultaneously, but it does not make parsing streaming end to end.

Normalize, moderate, and merge¶

For each of the $R$ records, the builder:

normalizes its display form and segments graphemes;
checks the deny set;
finds or creates the normalized grid-form entry;
rejects an unsupported normalized-display collision;
inserts one source reference and unions tags.

With expected $O(1)$ hash operations, this phase is:

\[ T_{merge} = O(Q_n + R + P_r + T_g) \]

The mutable map and its per-entry source/tag collections occupy:

\[ S_{merge} = O(N + G + P_r + T_g) \]

The deny check is expected $O(1)$ per normalized grid form in the current in-memory provider. A future remotely backed policy must preserve a local set/cache to retain this bound; a network request per record would dominate catalog construction.

LexicalEntry.Id is a fixed 32-byte value type LexicalId containing the SHA-256 digest of UTF-8 language + NUL + gridForm. Hashing all IDs is linear in the UTF-8 volume of those fields and is included in $O(Y)$. Comparison and hashing of fixed-width 32-byte keys is effectively $O(1)$ with respect to catalog size. Stack or pooled UTF-8 buffers avoid a fresh concatenated string and byte array for each entry, reducing allocation constants without changing the bound. Textual lex:-prefixed IDs are resolved to LexicalId only at boundary operations (API, persistence, compatibility, diagnostics); internal catalog operations use the typed LexicalId directly.

Finalization, ordering, and versioning¶

After merge, the builder creates the deterministic source/category registry, copies the $N$ grid-form references, removes mutable entries one at a time, and creates $N$ immutable entries. Each entry receives a source mask, sparse source-ordinal scores, and sorted category IDs. It then sorts entries by fixed-length LexicalId (32 bytes) and streams every canonical field through a content fingerprint. Fingerprinting resolves compact metadata through the registry directly rather than materializing Sources or Tags projections.

The finalization cost is:

\[ T_{finalize} = O\left( N\log N + Y + \sum_{i=1}^{N} p_i\log p_i + \sum_{i=1}^{N} t_i\log t_i \right) \]

where $p_i$ and $t_i$ are the source-reference and tag counts for entry $i$. Comparison of fixed-length 32-byte LexicalId keys is effectively $O(1)$ with respect to catalog size; the $N\log N$ term represents the sorting operation count, not per-comparison work. This notation assumes source IDs and tags have bounded practical length; otherwise their comparison-byte costs must also be included in $Y$. Since the number of configured sources is normally small, source sorting has a low constant. Tag cardinality is content-dependent.

The content fingerprint hashes each ID in its canonical 68-byte ASCII form (lex: plus 64 lowercase hexadecimal characters), then includes language, display/grid forms, forms flags, every grapheme, ordered source metadata, and ordered tags. The catalog version additionally includes schema version, normalizer version, content-policy version, and ordered source descriptors. Version construction therefore reads the complete accepted content; it is not a constant-time metadata operation. Retaining the legacy textual ID bytes in this stream intentionally preserves existing catalog versions.

WordCatalogSnapshot validates source IDs, entry IDs, languages, compact source/category references, and shared registry ownership. It builds immutable lookup dictionaries keyed by LexicalId (for FindById) and by normalized grid form (for FindByGridForm). Expected construction time remains $O(S + N + P_r + T_g)$ after entries exist, with $O(S+N)$ additional map storage plus one registry whose category storage is bounded by the accepted tag data. FindById and FindByGridForm lookups are expected $O(1)$ plus fixed-width key hashing/comparison.

Peak memory during publication¶

The builder deliberately removes each MutableEntry after conversion so its nested mutable collections can become collectible before conversion finishes. This addresses the earlier failure mode in which a complete mutable map and complete immutable result remained live for the entire conversion.

The asymptotic peak is still:

\[ S_{catalog\ peak} = O(B_{current} + N + G + Y + P_r + T_g) \]

but constants matter. At different points the process can hold a source parse result, the aggregate mutable dictionary, a grid-form reference array, an entry array, immutable snapshot arrays, and two immutable lookup maps. Garbage collection is nondeterministic, so removing references makes earlier collection possible but does not guarantee an immediate reduction in committed memory.

During refresh, the current immutable snapshot remains serviceable while a replacement is built. If old views/indexes or active requests retain it, peak process memory includes:

\[ S_{refresh\ peak} \approx S_{old\ retained} + S_{new\ build\ peak} + S_{new\ derived} \]

This overlap is the operationally important memory bound for large catalogs.

Catalog Views¶

A view cache is scoped by snapshot identity; inside that scope its key contains profile ID/version, game type, mode, and optional theme. Language is inherent in the parent snapshot. Building a view scans all $N$ snapshot entries and applies LexicalEligibilityProfile.Allows. Theme and required-tag membership checks are expected $O(1)$ each, while allowed-source and minimum-score predicates can scan an entry's source references. Let $E_V$ count those inspected associations and configured tag predicates.

For a view containing $V$ entries:

\[ T_{view} = O(N + E_V + V) \]

\[ S_{view} = O(V + N) \]

The view retains references for its $V$ eligible entries and one membership bit for each of the $N$ snapshot entries. The bitmap contributes approximately $\lceil N/8 \rceil$ payload bytes plus object overhead; its bit count is linear asymptotically but has a much smaller constant than a traditional ID-reference array. Each identity-bearing entry or dictionary-key field now has a 32-byte LexicalId payload rather than a reference to a per-entry textual lex:-prefixed ID string whose 68 UTF-16 characters alone require 136 bytes. The value is copied into the entry and lookup map, so $32N$ describes each such field, not the complete identity graph. Full object-graph savings require measurement and depend on dictionary layout, allocation patterns, and garbage collection. Snapshot textual payloads and the shared metadata registry remain snapshot-owned. Phase 4 reduces the constants associated with $P_r$ and $T_g$ but does not change these asymptotic bounds. FindByGridForm and FindById resolve through the corresponding snapshot maps keyed by fixed-width LexicalId and then test one bitmap position, all expected $O(1)$ plus fixed-width key hashing and comparison.

A theme changes the view key. Building a halloween view scans the complete snapshot even if only $H \ll N$ entries have that tag, so its construction cost is $O(N+E_V+H)$, not $O(H)$. With bounded per-entry provenance and a fixed profile this simplifies to $O(N+H)$. Once built, it is reused for that snapshot and key.

The provider coalesces concurrent requests for the same cold view. Views are associated with their snapshot, so publishing a different snapshot naturally creates a different view-cache scope. Old view state becomes collectible only after the old snapshot and all objects retaining it become unreachable.

Letter Golf¶

Signature construction¶

A LetterSignature is a sorted vector of (grapheme unit, count) pairs. For a word of length $\ell$ containing $d$ distinct units, counting is expected $O(\ell)$ and sorting keys is $O(d\log d)$:

\[ T_{signature} = O(\ell + d\log d), \qquad S_{signature}=O(d) \]

Covers currently iterates the candidate's $d_c$ units and binary-searches the target's flat sorted map of $d_t$ units. Its strict current bound is $O(d_c\log\max(2,d_t))$ and $O(1)$ additional space. A two-pointer merge could make this linear in $d_c+d_t$, but that is not the current implementation.

Sparse count-trie and frequency index build¶

The Letter Golf index builds signatures for eligible entries and inserts each signature into a sparse trie keyed in sorted order by (unit,count). Let $K$ be the number of distinct trie nodes after prefix sharing. It also computes one grapheme frequency table by visiting every grapheme in the relevant entries.

A useful complete build bound is:

\[ T_{LG\ index} = O\left(G_V + \sum_{i=1}^{V} d_i\log d_i + K\right) \]

\[ S_{LG\ index} = O(V + K + A) \]

The index stores the eligible view entries and materializes a sparse count trie over their signatures. Trie terminals are integer lists containing view-local ordinals. Production queries resolve those ordinals directly through the index's entry array; compatibility query methods project textual lex:-prefixed IDs. Parsing and formatting textual IDs is $O(1)$ because the textual representation has fixed length (68 characters for the hex encoding of the 32-byte LexicalId). The exact constants depend on how many signatures share prefixes and how many entries share one signature.

The frequency table itself is $O(G_V)$ to build and $O(A)$ space. FrequencyOf is expected $O(1)$. In the current code, RarityOf sums all $A$ frequencies on every call, so scoring a seed with $d$ distinct units costs $O(dA)$. Caching the total would reduce this factor, but $A$ is small for English and the implementation currently leaves it explicit.

Signature queries¶

Exact match follows exactly one trie edge for each distinct (unit,count) pair:

\[ T_{exact} = O(d + Z) \]

The $Z$ term applies when terminal ordinal lists are resolved to entry objects or compatibility textual lex:-prefixed IDs for return; constructing textual IDs is $O(1)$ per ID since the hexadecimal encoding has fixed length. Locating the terminal collection itself is $O(d)$.

Playable-word and hole-in-one queries use branch-and-bound traversal. Their cost is best expressed as:

\[ T_{trie\ search} = O(K_{visited}\log\max(2,d_t) + Z) \]

Each visited edge binary-searches the target signature's $d_t$ units. Because a word signature has few units, it is useful operationally to read this as $O(K_{visited}+Z)$ with a small bounded factor. Pruning often makes $K_{visited} \ll K$, but a permissive target or wildcard budget can visit the whole trie, yielding the strict worst case $O(K\log\max(2,d_t)+Z)$. These queries do not scan all words directly, but a full trie traversal can be proportional to total indexed signature structure.

Puzzle generation¶

Letter Golf is solution-first: it samples a real seed entry, reveals a weighted subset of distinct units, and then checks alternate hole-in-one and playable sub-par words. Solvability does not require random-letter retries, but difficulty constraints can reject a candidate up to MaxGenerationAttempts.

For each attempt, the current PickSeedWordCandidate filters the complete selected pool of size $P$ into a temporary list. This is $O(P)$ time and $O(P)$ temporary reference space per attempt. For a selected word, weighted reveal sorting is $O(d\log d)$, the two broad trie searches cost $O(K_h\log\max(2,d)+Z_h)$ and $O(K_p\log\max(2,d)+Z_p)$, and final strict exact matching costs $O(d+Z_e)$. Counting shorter playable results costs $O(Z_p)$.

With at most $a_g$ attempts, a conservative current bound is:

\[ T_{LG\ generate} = O\left( a_g\left(P + \ell + d\log d + (K_h+K_p)\log\max(2,d) + Z_h + Z_p + dA\right) \right) \]

The configured attempt limit makes one request finite, while the dominant warm cost depends on candidate-pool scans and how much of the trie the wildcard searches visit.

Word verification and play submission¶

On a warm catalog/view, verifying one word normalizes it and performs a deny-set lookup plus a view grid-form lookup:

\[ T_{verify}(w) = O(|w|) \text{ expected} \]

For $u$ submitted words with total normalized text length $W$, dictionary validation is $O(W)$ expected after the play evaluator has validated puzzle constraints. The first lexical request in a process can instead include catalog and view cold-start costs. Authentication or login does not intrinsically warm lexical state; identity, rate limiting, and persistence are separate request costs.

The compatibility adapter currently resolves verification through the default en-US normalizer. Its GetWordsAsync legacy path is intentionally more expensive: it filters and shuffles a complete view and materializes a new string set, so it is linear in view size even when the requested count is small.

Reverse Cross¶

Positional fill index¶

The fill index groups entries by grapheme length. Within each length bucket it stores a flat entry array and, for every (position, grapheme) pair, a posting array of entry offsets. Each indexed word contributes one posting occurrence per grapheme.

For the $V_I$ view entries whose lengths are in the configured range:

\[ T_{RC\ index} = O(V_I + G_I) \text{ expected} \]

\[ S_{RC\ index} = O(V_I + G_I + U_p) \]

where $U_p$ is the number of distinct posting keys and $G_I$ is the sum of indexed entry lengths. The $G_I$ posting offsets are the dominant structural term. Entries remain snapshot-owned and are retained by reference.

Board dimensions are not part of this index. A warm index covering lengths 3 through 15 can serve 7x7, 9x9, and 15x15 generation as long as each request asks the provider for those same indexed limits and each generated slot falls within them. The current provider keeps one current index per language and keys replacement/reuse by catalog version, profile ID/version, exact minimum/maximum indexed lengths, and index-options version.

The current provider always requests the fixed catalog-index view context, so its key does not include mode, theme, or the complete view fingerprint. That is safe for today's API because callers cannot vary those values. Adding themed Reverse Cross indexing requires extending both the provider request and its index key with the view fingerprint or equivalent theme/context identity; otherwise two different views could incorrectly reuse one index.

Candidate retrieval¶

For a slot of length $\ell$, the index inspects postings for each known position, chooses the smallest posting, and fully verifies every candidate from that posting against the grid. If there are $k$ known positions and the smallest posting contains $P$ offsets:

\[ T_{candidate} = O(k + P\ell) \]

If the slot has no known graphemes, the candidate range is the complete length bucket and $P=D_\ell$. Choosing the smallest posting is therefore a selectivity optimization, not an asymptotic guarantee. Full Fits verification is required because one posting proves only one positional constraint.

MRV backtracking¶

At each search node, the filler counts compatible candidates for every unassigned slot and chooses the slot with the fewest candidates. For unassigned slots $U$, MRV selection costs approximately:

\[ T_{MRV\ node} = O\left(\sum_{i\in U}(k_i + P_i\ell_i)\right) \]

The selected slot is traversed again to try candidates. Placement and removal are $O(\ell_i)$, and used-entry membership is expected $O(1)$ via integer-ordinal hashing. Candidate ordering and all-different entry constraints can reduce explored branches, but a fill with slot domain sizes $b_1,\ldots,b_L$ still has a theoretical search tree bounded by their product:

\[ T_{fill\ theoretical} = O\left(\prod_{i=1}^{L} b_i\right) \]

A coarser bound is $O(D_{max}^{L})$. Positional constraints and MRV normally reduce actual branching substantially; neither changes the exponential worst case.

Production operation is bounded by cancellation, elapsed time, and a global search-node budget. If at most $J_{max}$ nodes are admitted, CPU work attributable to admitted nodes is bounded by the sum of their MRV/candidate costs, plus the checks required to notice a time or cancellation limit. A time budget is a wall-clock guard rather than a deterministic CPU-operation count.

The recursive search retains assignments/grid state proportional to $O(C+L)$ plus recursion depth $O(L)$. Candidate postings belong to the shared index and are not copied per node.

Mask construction and quality¶

For each candidate mask, the generator assigns a deterministic ordering key to all $C$ cells and sorts them, costing $O(C\log C)$. It tentatively blocks up to all cells. After each tentative block it extracts all across/down slots, checks slot lengths, marks covered cells, and scans the board. Each structural check is $O(C)$ time and space, so current worst-case candidate construction is:

\[ T_{mask} = O(C^2 + C\log C), \qquad S_{mask}=O(C) \]

The coordinator performs one additional structural check. Optional blocked-ratio, checked-cell, and connected-open-cell quality checks are each $O(C)$; connectivity uses a breadth-first traversal. Slot extraction is $O(C)$ because every cell is inspected once horizontally and once vertically.

For at most $M$ mask attempts and at most $J$ admitted fill nodes, the request-level model is:

\[ T_{RC\ generate} = O\left( M(C^2 + C\log C) + \sum_{j=1}^{J} T_{MRV\ node,j} \right) \]

The coordinator divides remaining wall time and search nodes among remaining mask attempts, preventing an early mask from consuming the full global allowance. MaxMaskAttempts, MaxSearchNodes, the time budget, cancellation, and the production concurrency semaphore jointly bound operational exposure. When generation cannot proceed or does not succeed, the production provider returns a fixture where its fallback contract supports the request.

Final validation and identity¶

After a successful fill, the validator re-extracts slots; scans public/private cells; builds maps for slots, entries, and placements; and checks lengths, graphemes, crossings, and coverage. With $E$ entries/placements and total placed grapheme count $G_P$:

\[ T_{RC\ validate} = O(C + L + E + G_P) \text{ expected} \]

Validation uses $O(C+L+E)$ auxiliary maps/sets, excluding emitted error messages.

Mask order and fill order are deterministic functions of the seed and ordered indexed content. Replay identity includes generator version, content version, and generation options. The generated puzzle ID hashes that complete replay identity. A seed alone is therefore insufficient for replay: the same seed against a different content/profile version or generator/options version denotes a different generation experiment.

Cache and Invalidation Lifecycle¶

Cold process¶

The first request for a supported language starts one catalog build. Concurrent callers for that language await the same in-flight task. Once published, later snapshot requests are expected constant-time cache access plus requested-version comparison.

The first request for each profile/game/mode/theme combination over that snapshot builds one view. The first game request needing a derived index then builds that game index. These stages are lazy, so a cold end-to-end request can pay:

\[ T_{cold} = T_{source} + T_{merge} + T_{finalize} + T_{snapshot} + T_{view} + T_{game\ index} + T_{request} \]

Concurrent same-key work is coalesced at the catalog/view/index boundaries. Different languages or view keys are distinct work.

Warm process¶

A request with the same active language snapshot, view key, and game-index key reuses all lexical structures:

\[ T_{warm} = O(1)_{cache\ access} + T_{request} \]

For Letter Golf, $T_{request}$ still includes candidate-pool scans and trie searches. For Reverse Cross, it still includes mask generation and bounded backtracking. Warm means the content structures are present, not that puzzle generation is precomputed.

New dimensions, theme, profile, or language¶

Change	Catalog	View	Game index	Request work
Reverse Cross dimensions only	Reused	Reused	Reused if length range is covered	New mask/fill work with new $C,L$
New mode/theme/profile on same snapshot	Reused	Full $O(N+E_V)$ eligibility scan	Provider extension required; key by view fingerprint/context before building a new index	Normal generation
New language	Independent full build	New	New	Normal generation
Same seed only	Reused	Reused	Reused	Deterministic generation replay
New content version	Replaced	New cache scope	New	Normal generation

Source or policy refresh¶

An explicit refresh first refreshes source-owned state and the word-list provider, then rebuilds the complete requested language. Publication is atomic: success replaces the current snapshot, while failure retains the last known good snapshot.

There is no incremental entry patching. If a policy update removes $X$ entries, or a source adds $X$ entries, current rebuild time is governed by all $R$ records and all resulting $N'$ accepted entries:

\[ T_{change}(X) = T_{catalog}(R,N') + \sum T_{requested\ new\ views/indexes} \]

not $O(X)$. The changed count affects output size and may slightly affect constants, but every source is read, every record is normalized/moderated/merged, all accepted entries are sorted, and the complete canonical content is hashed again.

A content-policy version bump changes catalog identity even when accepted entries happen to be identical. A source descriptor/version or canonical entry change also changes catalog identity. This conservative invalidation ensures derived data cannot be mistaken for data built from a different policy or source set.

Changing dependency-injection registrations, such as adding an entirely new source or normalizer, requires a process deployment/restart before refresh can see that registration. Refresh changes source content, not the process's service graph.

Worked Scenario: Spanish 9x9 Halloween Reverse Cross¶

Assume a player logs in and requests a 9x9 Spanish Halloween Reverse Cross puzzle. Later, operators add a Spanish sailing-word source and update moderation to remove 20 words.

Exact behavior in the current Phase 4 implementation¶

This scenario is not currently supported end to end:

Only EnglishLexicalNormalizer for en-US is registered.
Production Reverse Cross request validation accepts only en-US, the crossword profile, no requested difficulty, and no theme.
Reverse Cross fixture selection also does not provide Spanish/theme variants.
The in-memory curated-list provider has no populated theme lists.

Therefore login does not trigger a Spanish catalog build. With generated serving enabled, production validation rejects Spanish before acquiring the generation gate or requesting a fill index. With generated serving disabled, the fixture provider receives the request and rejects the unsupported language/theme contract. No 9x9 mask search occurs. Production generation is feature-flagged off by default unless operators enable it.

The following cost ledger is explicitly hypothetical: it describes the existing architecture after real Spanish normalization/sources and themed Reverse Cross request support are implemented, not a capability Phase 3 currently exposes.

First request on a cold, fully provisioned replica¶

Let the Spanish source composition contain $R_{es}$ records/$B_{es}$ bytes and produce $N_{es}$ accepted entries with $G_{es}$ graphemes. Let $H$ entries pass the crossword profile and halloween tag.

Login pays identity/persistence costs only. It does not warm lexical caches.
The first Spanish lexical request downloads/parses all registered Spanish sources: $O(B_{es}+Q_{p,es}+R_{es})$ plus remote latency and bounded retries.
The catalog normalizes, moderates, and merges all $R_{es}$ records, then finalizes, sorts, fingerprints, validates, and publishes all $N_{es}$ entries. This is a complete language build, dominated by content volume and $N_{es}\log N_{es}$ ordering.
The Halloween crossword view scans all $N_{es}$ entries and retains $H$: $O(N_{es}+E_{V,es}+H)$ time and $O(H)$ direct view storage. With bounded provenance/profile predicates, the time simplifies to $O(N_{es}+H)$.
A theme-aware Reverse Cross provider keys the derived index by this view's fingerprint/context. The fill index processes the eligible $H$ entries in its length range: $O(H+G_H)$ time and space for references and posting offsets.
The 9x9 request has $C=81$. Each mask attempt costs at most $O(81^2+81\log81)$ structural work, followed by bounded MRV fill work. Board size does not rebuild the Spanish catalog or theme view.
On success, replay/puzzle identity binds the seed to the Spanish content version and generation options. On bounded failure, the provider attempts fixture fallback, which would also need a compatible Spanish/theme fixture contract to return a puzzle.

The process can temporarily retain source parse data, the mutable Spanish build, the immutable Spanish snapshot, the Halloween view, and its postings. Other replicas repeat this work independently.

Repeated warm request¶

A second 9x9 Spanish Halloween request on the same replica and content version reuses the snapshot, Halloween view, and fill index. It pays cache lookup plus fresh $C=81$ mask generation and bounded fill search. A different seed changes deterministic ordering but does not alter cache keys. A 7x7 request can reuse the same fill index if its slot lengths remain in the indexed range.

Adding the Spanish sailing source¶

Registering a new source requires deploying/restarting the service graph. On the next Spanish build, the source's complete artifact is acquired and parsed alongside all existing Spanish sources. Even if it contributes only $X_s$ new unique sailing words, the builder reprocesses all $R'_{es}$ records and publishes a complete new snapshot of $N'_{es}$ entries.

The source descriptor and canonical content change the catalog version. The old Halloween view/index cannot be reused under that version. Their replacements are built lazily on the next matching request. If sailing words lack the halloween tag, $H$ might not change, but the theme view still scans all $N'_{es}$ entries and receives a new fingerprint because its parent catalog version changed.

A sailing source by itself would not necessarily form a valid production catalog: current production configuration requires at least 300,000 accepted entries for a language, and individual sources can impose their own minimums. It must participate in a sufficiently large, correctly licensed and versioned Spanish source composition, with thresholds configured deliberately for that content set.

Removing 20 words through moderation¶

Suppose a refreshed deny list newly rejects $X=20$ words. The refresh observes the policy content only if the configured IWordListProvider.RefreshAsync implementation actually reloads it; today's in-memory implementation is a no-op with an empty deny set.

Under a real provider, all Spanish sources are still read and all $R'_{es}$ records are normalized and checked. The resulting snapshot has at most 20 fewer unique entries, but rebuild complexity is based on $R'_{es}$ and $N''_{es}$, not 20. The complete content fingerprint and snapshot maps are rebuilt. A content-policy version bump should accompany semantic policy changes so identity records why content changed, even if none of the 20 words were present.

After atomic publication, the next Halloween request builds a new $O(N''_{es})$ view and new postings. Active requests holding the old index may finish safely; that also means old and new snapshots/indexes can overlap in memory until references are released.

Summary Matrix¶

Operation	Expected/current time	Additional or retained space	Important worst case or caveat
Parse all sources for a language	$O(B+Q_p+R)$	Parser-dependent, at least $\Omega(R)$ for current materialized source result	Remote latency/retries dominate wall time; source parsers are not end-to-end streaming
Merge catalog records	$O(Q_n+R+P_r+T_g)$	$O(N+G+P_r+T_g)$	Hash collision behavior can degrade table operations
Finalize/version catalog	$O(N\log N+Y+\sum p_i\log p_i+\sum t_i\log t_i)$; sorting by fixed-width 32-byte `LexicalId` key is $O(1)$ per comparison	$O(N+G+Y+P_r+T_g)$	Complete content is hashed on every build; fingerprint preserves existing versions
Snapshot exact lookup	$O(1)$ expected; fixed-width 32-byte `LexicalId` key hashing/comparison is $O(1)$	$O(1)$ per query	Requires warm snapshot; cold request pays build; ID lookup map is $O(N)$
Build profile/theme view	$O(N+E_V+V)$	$O(V)$ plus retaining snapshot	A small themed result still scans all $N$ entries
Build Letter Golf index	$O(G_V+\sum d_i\log d_i+K)$	$O(V+K+A)$	Trie shape depends on signature prefix sharing
Letter Golf exact signature	$O(d+Z)$	$O(Z)$ if materialized	One trie path
Letter Golf playable/hole-in-one	$O(K_{visited}\log\max(2,d_t)+Z)$	Traversal/result-dependent	Worst case visits all $K$ nodes
Letter Golf generation	Attempt-bounded formula above	$O(P+Z_h+Z_p+d)$ temporary, excluding shared index	Current seed filtering rescans/materializes pool each attempt
Warm word verification	$O(\lvert w\rvert)$ expected	$O(\lvert w\rvert)$ normalization-dependent	First request can pay catalog/view cold start
Build Reverse Cross fill index	$O(V_I+G_I)$ expected	$O(V_I+G_I+U_p)$	One posting occurrence per indexed grapheme
Reverse Cross slot candidates	$O(k+P\ell)$	Shared posting plus returned range	No known letters means $P=D_\ell$
Reverse Cross MRV node	$O(\sum_{i\in U}(k_i+P_i\ell_i))$	$O(C+L)$ shared search state	Complete fill remains exponential theoretically
Build one mask candidate	$O(C^2+C\log C)$	$O(C)$	Structural legality is recomputed after tentative blocks
Validate filled puzzle	$O(C+L+E+G_P)$ expected	$O(C+L+E)$	Error output adds its own space
Refresh after $X$ content changes	Full catalog plus requested new views/indexes	Old retained graph plus new build/derived graph	Not $O(X)$; publication is whole-snapshot atomic

Implementation Anchors¶

Catalog construction and complete version hashing: WordCatalogBuilder
Atomic process-local publication and single-flight builds: InMemoryWordCatalogProvider
Snapshot arrays and exact maps: WordCatalogSnapshot
View filtering and caching: WordCatalogViewProvider and WordCatalogView
Letter Golf signatures and sparse trie: LetterSignature and WordSignatureIndex
Letter Golf index and request algorithm: LetterGolfCatalogIndex and LetterGolfGenerator
Reverse Cross postings and bounded MRV fill: ReverseCrossFillIndex and ReverseCrossKnownMaskFiller
Reverse Cross mask and request coordination: ReverseCrossMaskGenerator, ReverseCrossGenerator, and ReverseCrossProductionPuzzleProvider

Engineering Conclusions¶

Treat catalog refresh as a bulk data-plane operation. Schedule and observe it like a full rebuild even when the semantic delta is tiny.
Size replica memory for old/new immutable overlap and derived indexes, not only for the steady-state current snapshot.
Keep policy membership local and hash-backed during construction. Per-record remote policy calls would destroy the current linear build model.
Measure themed view selectivity and positional-posting sizes. They are the strongest predictors of practical Reverse Cross fill cost after board shape.
Preserve bounded generation controls. MRV and postings improve typical behavior, while time, node, attempt, cancellation, and concurrency limits provide the operational guarantee.
Interpret a seed together with content version, profile/view identity, generator version, and options. Reproducibility is a versioned-data property, not a random-number property alone.
Optimize only from measurements. The current Letter Golf pool materialization, repeated frequency totals, theme full scans, and repeated mask legality checks are clear candidates, but each should be changed with benchmark and allocation evidence rather than asymptotic arguments alone.

Symbol	Meaning
\(S\)	Number of lexical sources registered for one language
\(B\)	Total bytes parsed from those sources
\(R\)	Total raw records emitted by those sources, including duplicates and later rejections
\(Q_p\)	Total decoded text/code-point work performed while parsing source records
\(Q_n\)	Total raw display-form text/code-point work performed by normalization
\(N\)	Unique accepted entries in a published language snapshot
\(G\)	Total accepted grapheme references, \(\sum_{i=1}^{N} \ell_i\)
\(Y\)	Total UTF-8 byte volume of accepted canonical fields consumed by identity/version hashing
\(P_r\)	Total accepted source-reference associations across merged entries
\(T_g\)	Total accepted tag associations across merged entries
\(V\)	Number of entries in one catalog view
\(G_V\)	Total grapheme references in that view
\(E_V\)	Total source/tag/score associations inspected while evaluating one view
\(A\)	Number of distinct grapheme units represented in a frequency table
\(d_i\)	Number of distinct grapheme units in word \(i\)
\(K\)	Number of nodes in a Letter Golf sparse count trie
\(Z\)	Number of results returned by a query
\(C\)	Number of Reverse Cross cells, \(rows \times columns\)
\(L\)	Number of Reverse Cross slots in one mask
\(\ell_i\)	Grapheme length of word or slot \(i\)
\(D_\ell\)	Number of indexed Reverse Cross entries of length \(\ell\)
\(P_i\)	Size of the smallest applicable positional posting for slot \(i\)
\(J\)	Search nodes actually visited by bounded Reverse Cross backtracking
\(M\)	Number of mask candidates attempted
\(X\)	Number of source or policy entries changed by an update

Operation	Expected/current time	Additional or retained space	Important worst case or caveat
Parse all sources for a language	\(O(B+Q_p+R)\)	Parser-dependent, at least \(\Omega(R)\) for current materialized source result	Remote latency/retries dominate wall time; source parsers are not end-to-end streaming
Merge catalog records	\(O(Q_n+R+P_r+T_g)\)	\(O(N+G+P_r+T_g)\)	Hash collision behavior can degrade table operations
Finalize/version catalog	\(O(N\log N+Y+\sum p_i\log p_i+\sum t_i\log t_i)\); sorting by fixed-width 32-byte `LexicalId` key is \(O(1)\) per comparison	\(O(N+G+Y+P_r+T_g)\)	Complete content is hashed on every build; fingerprint preserves existing versions
Snapshot exact lookup	\(O(1)\) expected; fixed-width 32-byte `LexicalId` key hashing/comparison is \(O(1)\)	\(O(1)\) per query	Requires warm snapshot; cold request pays build; ID lookup map is \(O(N)\)
Build profile/theme view	\(O(N+E_V+V)\)	\(O(V)\) plus retaining snapshot	A small themed result still scans all \(N\) entries
Build Letter Golf index	\(O(G_V+\sum d_i\log d_i+K)\)	\(O(V+K+A)\)	Trie shape depends on signature prefix sharing
Letter Golf exact signature	\(O(d+Z)\)	\(O(Z)\) if materialized	One trie path
Letter Golf playable/hole-in-one	\(O(K_{visited}\log\max(2,d_t)+Z)\)	Traversal/result-dependent	Worst case visits all \(K\) nodes
Letter Golf generation	Attempt-bounded formula above	\(O(P+Z_h+Z_p+d)\) temporary, excluding shared index	Current seed filtering rescans/materializes pool each attempt
Warm word verification	\(O(\lvert w\rvert)\) expected	\(O(\lvert w\rvert)\) normalization-dependent	First request can pay catalog/view cold start
Build Reverse Cross fill index	\(O(V_I+G_I)\) expected	\(O(V_I+G_I+U_p)\)	One posting occurrence per indexed grapheme
Reverse Cross slot candidates	\(O(k+P\ell)\)	Shared posting plus returned range	No known letters means \(P=D_\ell\)
Reverse Cross MRV node	\(O(\sum_{i\in U}(k_i+P_i\ell_i))\)	\(O(C+L)\) shared search state	Complete fill remains exponential theoretically
Build one mask candidate	\(O(C^2+C\log C)\)	\(O(C)\)	Structural legality is recomputed after tentative blocks
Validate filled puzzle	\(O(C+L+E+G_P)\) expected	\(O(C+L+E)\)	Error output adds its own space
Refresh after \(X\) content changes	Full catalog plus requested new views/indexes	Old retained graph plus new build/derived graph	Not \(O(X)\); publication is whole-snapshot atomic