notes.html
problem 98 · 87 lines
<article>
<h3>Problem Analysis</h3>
<p>
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
<a class="reference-source" href="https://en.wikipedia.org/wiki/Anagram" rel="noopener noreferrer" target="_blank">anagrams</a>
- words built from exactly the same multiset of letters - for which one consistent substitution of letters by digits
turns both members into
<a class="reference-source" href="https://en.wikipedia.org/wiki/Square_number" rel="noopener noreferrer" target="_blank">perfect squares</a>.
The substitution must be a
<a class="reference-source" href="https://en.wikipedia.org/wiki/Bijection" rel="noopener noreferrer" target="_blank">bijection</a>
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.
</p>
<p>
Two observations collapse this from a frightening search space into a handful of cheap checks. First, only words that
are <a class="reference-source" href="https://en.wikipedia.org/wiki/Anagram" rel="noopener noreferrer" target="_blank">anagrams</a>
of each other can ever pair, so I group words by a <em>canonical form</em> (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 <em>shape</em>: 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
<a class="reference-source" href="https://en.wikipedia.org/wiki/Bijection" rel="noopener noreferrer" target="_blank">bijection</a>
preserves repetition structure, this shape is an
<a class="reference-source" href="https://en.wikipedia.org/wiki/Invariant_(mathematics)" rel="noopener noreferrer" target="_blank">invariant</a>
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.
</p>
<h3>Solution Approach</h3>
<h4>Anagram Grouping with Shape-Hash Prefiltering (Python and C)</h4>
<p>
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.
</p>
<p>
<strong>Step 1 - Load and group by canonical form.</strong> The file is comma-separated and quote-wrapped, so I strip
quotes and split on commas. For each word I compute its <em>canonical form</em> by sorting its letters; all
<a class="reference-source" href="https://en.wikipedia.org/wiki/Anagram" rel="noopener noreferrer" target="_blank">anagrams</a>
share one canonical form and therefore one bucket. In Python the buckets live in a nested
<code>dict</code> keyed first by length and then by canonical form, wrapped in a frozen
<a class="reference-source" href="https://docs.python.org/3/library/dataclasses.html" rel="noopener noreferrer" target="_blank">dataclass</a>
(<code>Anagrams</code>). In C they are a static array of <code>Bucket</code> structs located by a linear scan over
canonical strings, with the sort done by a small insertion sort in place.
</p>
<p>
<strong>Step 2 - Prune singletons.</strong> A bucket holding one word can never form a pair, so I drop it before any
numeric work. The Python <code>prune()</code> method removes singleton classes and any now-empty length groups; the C
code collects buckets with <code>word_count > 1</code> into a <code>valid_buckets</code> array. Pruning early keeps
the inner loops working only on viable candidates.
</p>
<p>
<strong>Step 3 - Process lengths largest first.</strong> 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
<code>best == 0</code> so it stops once a length produces a result. This is
<a class="reference-source" href="https://en.wikipedia.org/wiki/Branch_and_bound" rel="noopener noreferrer" target="_blank">early termination</a>
driven by the search ordering.
</p>
<p>
<strong>Step 4 - Generate candidate squares.</strong> For the current length <code>n</code> I enumerate every square
with exactly <code>n</code> digits by iterating the integer roots from <code>ceil(sqrt(10^(n-1)))</code> to
<code>floor(sqrt(10^n - 1))</code> and squaring each. Python stores them in a <code>set[str]</code> for O(1)
membership; C uses a growable <code>StrList</code> with linear-scan membership, which is fine for a few thousand
strings.
</p>
<p>
<strong>Step 5 - Shape-hash prefilter.</strong> 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
<a class="reference-source" href="https://en.wikipedia.org/wiki/Bijection" rel="noopener noreferrer" target="_blank">bijection</a>
can connect them, so I skip the pair immediately. This is the central optimization.
</p>
<p>
<strong>Step 6 - Build and validate the bijection.</strong> I zip the word's characters with the square's digits to
form a proposed map. It is valid only if it is <em>consistent</em> (a letter never maps to two different digits) and
<em>injective</em> (no two letters map to the same digit). Python verifies both by comparing <code>dict</code> and
<code>set</code> sizes against the word length; C performs explicit linear scans over its parallel
<code>char_map_key</code>/<code>char_map_val</code> arrays, checking coverage and collisions separately.
</p>
<p>
<strong>Step 7 - Apply to anagram partners.</strong> 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.
</p>
</article>