Problem Analysis
On the surface this looks like a number puzzle, but it is really a constrained search for a structure-preserving map. We are given a word list and must find pairs of anagrams - words built from exactly the same multiset of letters - for which one consistent substitution of letters by digits turns both members into perfect squares. The substitution must be a bijection on the letters used: each distinct letter maps to one distinct digit, no two letters share a digit, and no number may have a leading zero. Among every valid pair we want the largest square.
Two observations collapse this from a frightening search space into a handful of cheap checks. First, only words that are anagrams of each other can ever pair, so I group words by a canonical form (their letters sorted alphabetically) and discard any group with a single member. Second, a candidate square must not only have the same number of digits as the word has letters, it must have the same shape: the multiset of repetition counts of its symbols. The word CARE has four distinct letters each appearing once (shape "1111"), so it can only map onto a four-digit square with four distinct digits. Because a bijection preserves repetition structure, this shape is an invariant that any valid mapping must respect - comparing shapes rejects the overwhelming majority of (word, square) pairs before any mapping is constructed. With fewer than two thousand words and at most a few thousand squares of any given length, the effective work is proportional to (anagram words) x (candidate squares per length), which is tiny in practice.
Solution Approach
Anagram Grouping with Shape-Hash Prefiltering (Python and C)
Both files implement the same algorithm; they differ only in language idioms and data structures. I will describe the shared logic and note where each language diverges.
Step 1 - Load and group by canonical form. The file is comma-separated and quote-wrapped, so I strip
quotes and split on commas. For each word I compute its canonical form by sorting its letters; all
anagrams
share one canonical form and therefore one bucket. In Python the buckets live in a nested
dict keyed first by length and then by canonical form, wrapped in a frozen
dataclass
(Anagrams). In C they are a static array of Bucket structs located by a linear scan over
canonical strings, with the sort done by a small insertion sort in place.
Step 2 - Prune singletons. A bucket holding one word can never form a pair, so I drop it before any
numeric work. The Python prune() method removes singleton classes and any now-empty length groups; the C
code collects buckets with word_count > 1 into a valid_buckets array. Pruning early keeps
the inner loops working only on viable candidates.
Step 3 - Process lengths largest first. I sort the surviving word lengths in descending order. Because
a longer square is numerically larger than any shorter one, the first length that yields a valid pair must contain the
global maximum. The Python solution returns on the first hit; the C solution guards its outer loop with
best == 0 so it stops once a length produces a result. This is
early termination
driven by the search ordering.
Step 4 - Generate candidate squares. For the current length n I enumerate every square
with exactly n digits by iterating the integer roots from ceil(sqrt(10^(n-1))) to
floor(sqrt(10^n - 1)) and squaring each. Python stores them in a set[str] for O(1)
membership; C uses a growable StrList with linear-scan membership, which is fine for a few thousand
strings.
Step 5 - Shape-hash prefilter. For each word and each square I compute the shape hash - the per-symbol repetition counts sorted descending and concatenated (for example "1111" or "211"). If two shape hashes differ, no bijection can connect them, so I skip the pair immediately. This is the central optimization.
Step 6 - Build and validate the bijection. I zip the word's characters with the square's digits to
form a proposed map. It is valid only if it is consistent (a letter never maps to two different digits) and
injective (no two letters map to the same digit). Python verifies both by comparing dict and
set sizes against the word length; C performs explicit linear scans over its parallel
char_map_key/char_map_val arrays, checking coverage and collisions separately.
Step 7 - Apply to anagram partners. A valid map is applied to every other word in the same bucket. If the resulting digit string is itself a square in the precomputed collection and has no leading zero, I have a valid pair, and I record the maximum of the two square values. The first valid pair at the longest length is the answer, 18769.