We are given a list of English words. Two words matter only if they are anagrams, meaning they contain exactly the same letters in a different order. A valid solution chooses one such pair together with a bijection from letters to digits so that both words become decimal integers, neither integer begins with 0, and both integers are perfect squares.
The goal is to find the largest square that appears anywhere in such a pair. Because a word of length \(L\) must map to an \(L\)-digit number, the search is finite and can be organized by word length.
The efficient viewpoint is to treat the problem as a comparison between two kinds of patterns: sorted-letter signatures for finding anagram classes, and repetition signatures for deciding whether a word can match a square at all. Once those invariants are identified, the remaining work is a finite scan over the relevant square numbers.
Sort the letters of each word alphabetically. Words with the same sorted form belong to the same anagram class, and only such classes can contribute a valid pair. If one class contains \(m\) words, then only its \(\binom{m}{2}\) unordered pairs need to be examined.
For a chosen pair \((W_1,W_2)\), the common word length is \(L\). Therefore any candidate square must lie in the interval
$$10^{L-1} \le n^2 < 10^L.$$
The number of \(L\)-digit squares is
$$S_L=\left\lfloor \sqrt{10^L-1} \right\rfloor-\left\lceil \sqrt{10^{L-1}} \right\rceil+1.$$
That already cuts the problem down from all digit assignments to a concrete list of square numbers of the correct length.
A valid substitution must be a bijection: the same letter must always receive the same digit, and two different letters cannot share one digit. So the real question is whether the pattern of repeated letters in a word matches the pattern of repeated digits in a square.
Define the pattern signature \(\pi(s)\) of a string \(s=s_1s_2\cdots s_L\) by numbering symbols in order of first appearance. For example,
$$\pi(\text{CARE})=(0,1,2,3),\qquad \pi(\text{MEET})=(0,1,1,2),$$
and similarly
$$\pi(1296)=(0,1,2,3),\qquad \pi(1225)=(0,1,1,2).$$
A word \(W\) can match a digit string \(D\) under a bijection if and only if \(\pi(W)=\pi(D)\), together with the extra rule that the leading digit is nonzero. This is the main mathematical filter used by the strongest implementation: squares are pre-grouped by pattern, so a word with pattern \((0,1,1,2)\) never needs to be tested against a square with pattern \((0,1,2,3)\).
Suppose \(W_1\) is matched with some \(L\)-digit square \(D_1\). If that match is valid, then every letter occurring in the anagram pair has been assigned exactly one digit. Because \(W_2\) uses the same multiset of letters, the second digit string \(D_2\) is completely determined by the same bijection; there is no independent second search.
Each candidate test therefore has a precise structure: choose \(D_1\), verify the bijection \(W_1 \leftrightarrow D_1\), construct \(D_2\) by reading the letters of \(W_2\), reject it if it begins with 0, and finally check whether \(D_2\) is also a square. If all those conditions hold, \((D_1,D_2)\) is a valid square anagram pair.
The pair CARE/RACE has length \(L=4\), so only four-digit squares are relevant. Those are the squares from \(32^2\) through \(99^2\), because
$$1000 \le n^2 \le 9999.$$
Take \(D_1=1296=36^2\). Its digit pattern is \((0,1,2,3)\), which matches CARE, so we obtain the bijection
$$C\mapsto 1,\qquad A\mapsto 2,\qquad R\mapsto 9,\qquad E\mapsto 6.$$
Applying the same map to RACE gives
$$RACE \mapsto 9216 = 96^2.$$
Both numbers are squares, so this is a genuine solution pair. By contrast, a four-digit square such as \(1225\) fails immediately for CARE because its repeated-digit pattern does not match a word with four distinct letters.
The C++, Python, and Java implementations first parse the quoted word list, normalize it to plain words, and group those words by sorted letters. Any group of size 1 is discarded immediately, while each larger group contributes all unordered anagram pairs.
All three implementations organize perfect squares by digit length so that a word of length \(L\) is only tested against \(L\)-digit squares. The C++ implementation goes one step further: it also groups the square strings by repetition pattern and keeps a fast lookup structure for square values. The Python and Java implementations keep the length buckets and validate the mapped second number by an integer-square-root check.
For each anagram pair, the implementation iterates over candidate squares of the same length, builds the two-way letter-to-digit and digit-to-letter correspondence, rejects any collision that breaks bijectivity, constructs the mapped value for the partner word, rejects leading zeros, and then verifies that the partner value is square. Whenever both numbers are square, the larger of the two is compared with the current global maximum.
Let \(A_L\) be the number of anagram pairs of length \(L\), and let \(S_L\) denote the number of \(L\)-digit squares. Checking one square against one word pair costs \(O(L)\), because each character position is examined a constant number of times while building and validating the bijection.
The Python and Java implementations therefore run in
$$O\!\left(\sum_L A_L S_L L\right),$$
with space \(O\!\left(\sum_L S_L\right)\) for the stored square strings plus the word groups. The C++ implementation has the same outer structure but reduces the practical candidate count by restricting each word pattern to the matching square-pattern bucket. In all cases the search is manageable because the number of relevant word lengths is small and \(S_L\) grows only like the width of a square-root interval.
Gegeben ist eine Liste englischer Wörter. Relevant sind nur Wortpaare, die Anagramme sind, also aus genau denselben Buchstaben in anderer Reihenfolge bestehen. Gesucht ist eine Bijektion zwischen Buchstaben und Ziffern, unter der beide Wörter zu Dezimalzahlen werden, keine der beiden Zahlen mit 0 beginnt und beide Zahlen perfekte Quadrate sind.
Am Ende zählt das größte Quadrat, das in irgendeinem gültigen Paar auftaucht. Weil ein Wort der Länge \(L\) nur auf eine \(L\)-stellige Zahl abgebildet werden kann, lässt sich die Suche sauber nach Wortlängen aufteilen.
Der Kern der Aufgabe ist nicht eine rohe Suche über alle möglichen Zuordnungen, sondern die Identifikation der richtigen Invarianten: Anagrammklassen, Wiederholmuster der Buchstaben und der endliche Bereich der \(L\)-stelligen Quadratzahlen. Genau diese Struktur verwenden die Implementierungen.
Man sortiert die Buchstaben jedes Wortes alphabetisch. Wörter mit derselben sortierten Form liegen in derselben Anagrammklasse, und nur solche Klassen können überhaupt eine Lösung liefern. Enthält eine Klasse \(m\) Wörter, dann müssen nur die \(\binom{m}{2}\) ungeordneten Paare betrachtet werden.
Für ein festes Paar \((W_1,W_2)\) ist die gemeinsame Wortlänge \(L\). Daher kommen genau die Quadratzahlen in Frage, die den Bereich
$$10^{L-1} \le n^2 < 10^L$$
erfüllen. Ihre Anzahl ist
$$S_L=\left\lfloor \sqrt{10^L-1} \right\rfloor-\left\lceil \sqrt{10^{L-1}} \right\rceil+1.$$
Damit schrumpft die Aufgabe von allen Ziffernbelegungen auf eine endliche Menge von Quadratzahlen der richtigen Länge.
Eine gültige Substitution muss bijektiv sein: Derselbe Buchstabe muss immer dieselbe Ziffer erhalten, und zwei verschiedene Buchstaben dürfen nicht auf dieselbe Ziffer fallen. Deshalb ist das Wiederholmuster der Symbole wichtiger als ihre konkreten Werte.
Definiere die Mustersignatur \(\pi(s)\) einer Zeichenkette \(s=s_1s_2\cdots s_L\), indem jedes neue Symbol nach seinem ersten Auftreten nummeriert wird. Dann gilt zum Beispiel
$$\pi(\text{CARE})=(0,1,2,3),\qquad \pi(\text{MEET})=(0,1,1,2),$$
und ebenso
$$\pi(1296)=(0,1,2,3),\qquad \pi(1225)=(0,1,1,2).$$
Ein Wort \(W\) kann genau dann bijektiv auf eine Ziffernfolge \(D\) abgebildet werden, wenn \(\pi(W)=\pi(D)\) gilt und die führende Ziffer nicht 0 ist. Darum gruppiert die effizienteste Implementierung die Quadratzahlen zusätzlich nach Mustersignaturen: Ein Wortmuster \((0,1,1,2)\) muss nie gegen eine Quadratzahl mit Muster \((0,1,2,3)\) geprüft werden.
Nehmen wir an, \(W_1\) werde auf eine \(L\)-stellige Quadratzahl \(D_1\) abgebildet. Wenn diese Abbildung gültig ist, hat jeder im Anagrammpaar vorkommende Buchstabe bereits genau eine Ziffer erhalten. Da \(W_2\) denselben Buchstabenmultimengengehalt besitzt, ist die zweite Ziffernfolge \(D_2\) durch dieselbe Bijektion vollständig bestimmt; es gibt keinen unabhängigen zweiten Suchbaum.
Jeder Kandidatentest hat daher eine klare Form: Wähle \(D_1\), prüfe die Bijektion \(W_1 \leftrightarrow D_1\), konstruiere \(D_2\) aus den Buchstaben von \(W_2\), verwerfe den Fall bei führender 0 und teste dann, ob auch \(D_2\) eine Quadratzahl ist. Genau dann erhält man ein gültiges Quadrat-Anagramm-Paar.
Das Paar CARE/RACE hat Länge \(L=4\), also kommen nur vierstellige Quadrate in Frage. Das sind die Quadrate von \(32^2\) bis \(99^2\), denn
$$1000 \le n^2 \le 9999.$$
Nehmen wir \(D_1=1296=36^2\). Sein Ziffernmuster ist \((0,1,2,3)\) und passt damit zu CARE. Es entsteht die Bijektion
$$C\mapsto 1,\qquad A\mapsto 2,\qquad R\mapsto 9,\qquad E\mapsto 6.$$
Auf RACE angewendet ergibt dieselbe Zuordnung
$$RACE \mapsto 9216 = 96^2.$$
Beide Zahlen sind Quadrate, also ist dies ein echtes Lösungspaar. Dagegen scheitert eine Zahl wie \(1225\) schon sofort, weil ihr Wiederholmuster nicht zu einem Wort mit vier verschiedenen Buchstaben passt.
Die C++-, Python- und Java-Implementierungen lesen zuerst die in Anführungszeichen gespeicherte Wortliste ein, bereinigen sie zu reinen Wörtern und gruppieren diese über ihre sortierten Buchstaben. Gruppen der Größe 1 werden direkt verworfen; größere Gruppen liefern alle ungeordneten Anagrammpaare.
Alle drei Implementierungen organisieren perfekte Quadrate nach ihrer Stellenzahl, damit ein Wort der Länge \(L\) nur gegen \(L\)-stellige Quadrate geprüft wird. Die C++-Variante geht noch weiter: Sie gruppiert die Quadratstrings zusätzlich nach Wiederholmuster und speichert eine schnelle Nachschlagestruktur für Quadratwerte. Die Python- und Java-Versionen behalten die Längenklassen und prüfen die zweite Zahl mit einem ganzzahligen Wurzeltest.
Für jedes Anagrammpaar iteriert die Implementierung über alle Kandidatquadrate der passenden Länge, baut die Zuordnung Buchstabe-zu-Ziffer und Ziffer-zu-Buchstabe auf, verwirft jede Kollision, konstruiert die abgebildete Zahl des Partnerwortes, schließt führende Nullen aus und prüft anschließend, ob die Partnerzahl wieder ein Quadrat ist. Wenn beide Zahlen Quadrate sind, wird das größere davon mit dem bisherigen Maximum verglichen.
Sei \(A_L\) die Anzahl der Anagrammpaare der Länge \(L\), und sei \(S_L\) die Anzahl der \(L\)-stelligen Quadrate. Ein einzelner Test von Quadrat gegen Wortpaar kostet \(O(L)\), weil jede Position nur konstant oft gelesen oder beschrieben wird.
Damit laufen die Python- und Java-Implementierungen in
$$O\!\left(\sum_L A_L S_L L\right),$$
bei einem Speicherbedarf von \(O\!\left(\sum_L S_L\right)\) für die gespeicherten Quadratstrings plus die Wortgruppen. Die C++-Implementierung besitzt dieselbe äußere Struktur, reduziert aber die praktische Kandidatenzahl, weil pro Wortmuster nur Quadrate aus dem passenden Muster-Bucket betrachtet werden. Für die Problemgröße von Project Euler bleibt die Suche daher komfortabel beherrschbar.
Bize bir İngilizce kelime listesi veriliyor. Yalnızca anagram olan kelime çiftleri önemlidir; yani aynı harfleri farklı sırada içeren çiftler. Amaç, harflerden rakamlara bire bir bir eşleme kurup her iki kelimeyi de onluk tabanda birer sayıya dönüştürmek, bu sayıların hiçbirinin 0 ile başlamamasını sağlamak ve ikisinin de tam kare olmasını istemektir.
Aranan şey, herhangi bir geçerli çiftte ortaya çıkan en büyük karedir. Bir kelime uzunluğu \(L\) ise karşılık gelen sayı da \(L\) basamaklı olmak zorundadır; bu yüzden arama doğal olarak kelime uzunluklarına göre sonlu parçalara ayrılır.
Bu problemde verimli bakış açısı, tüm eşlemeleri körlemesine denemek değildir. Asıl yapı üç yerde saklıdır: anagram sınıfları, harf tekrar desenleri ve \(L\) basamaklı karelerin sonlu aralığı. Uygulamalar tam olarak bu nesneleri kullanır.
Her kelimenin harflerini alfabetik olarak sıralayalım. Aynı sıralı biçime sahip kelimeler aynı anagram sınıfındadır ve ancak bu sınıflar çözüm üretebilir. Bir sınıfta \(m\) kelime varsa incelenmesi gereken çift sayısı yalnızca \(\binom{m}{2}\) olur.
Sabit bir \((W_1,W_2)\) çifti için ortak uzunluk \(L\) olsun. O zaman aday kareler tam olarak
$$10^{L-1} \le n^2 < 10^L$$
eşitsizliğini sağlayan karelerdir. Bunların sayısı
$$S_L=\left\lfloor \sqrt{10^L-1} \right\rfloor-\left\lceil \sqrt{10^{L-1}} \right\rceil+1$$
şeklindedir. Böylece problem, tüm rakam atamalarını dolaşmaktan çıkıp doğru uzunluktaki sonlu kare listelerine iner.
Geçerli bir eşleme bire bir olmak zorundadır: aynı harf her zaman aynı rakamı almalı, farklı iki harf de aynı rakamı paylaşmamalıdır. Bu nedenle asıl bakılması gereken şey, harflerin tekrar yapısının kare sayının rakam tekrar yapısıyla uyuşup uyuşmadığıdır.
Bir \(s=s_1s_2\cdots s_L\) dizgesinin desen imzası \(\pi(s)\), sembolleri ilk göründükleri sıraya göre numaralandırılarak tanımlansın. Örneğin
$$\pi(\text{CARE})=(0,1,2,3),\qquad \pi(\text{MEET})=(0,1,1,2),$$
ve benzer biçimde
$$\pi(1296)=(0,1,2,3),\qquad \pi(1225)=(0,1,1,2).$$
Bir kelime \(W\), bir rakam dizisi \(D\) ile ancak ve ancak \(\pi(W)=\pi(D)\) olduğunda eşleşebilir; buna ek olarak ilk rakam 0 olamaz. En güçlü uygulamanın kareleri desenlerine göre önceden gruplayabilmesinin sebebi budur: \((0,1,1,2)\) desenli bir kelime, \((0,1,2,3)\) desenli bir kareyle hiç test edilmez.
\(W_1\) kelimesi bir \(L\) basamaklı kare \(D_1\) ile eşleşsin. Bu eşleşme geçerliyse anagram çiftinde geçen her harfin hangi rakama karşılık geldiği artık kesinleşmiştir. \(W_2\) aynı harf çokluğunu kullandığı için ikinci sayı \(D_2\), aynı eşleme altında tamamen belirlenir; bağımsız ikinci bir arama yoktur.
Dolayısıyla her aday kontrolü şu biçimdedir: \(D_1\) seçilir, \(W_1 \leftrightarrow D_1\) eşlemesinin bire bir olup olmadığı doğrulanır, aynı eşleme \(W_2\) üzerine uygulanarak \(D_2\) üretilir, \(D_2\) 0 ile başlıyorsa aday atılır ve son olarak \(D_2\)'nin de kare olup olmadığı test edilir. Tüm koşullar sağlanıyorsa geçerli bir kare anagram çifti bulunmuştur.
CARE/RACE çifti için \(L=4\) olduğundan yalnızca dört basamaklı kareler önemlidir. Bunlar \(32^2\) ile \(99^2\) arasındaki karelerdir; çünkü
$$1000 \le n^2 \le 9999.$$
\(D_1=1296=36^2\) değerini deneyelim. Bunun rakam deseni \((0,1,2,3)\) olup CARE ile aynıdır. Böylece
$$C\mapsto 1,\qquad A\mapsto 2,\qquad R\mapsto 9,\qquad E\mapsto 6$$
eşlemesini elde ederiz. Aynı eşleme RACE üzerine uygulanınca
$$RACE \mapsto 9216 = 96^2$$
çıkar. Her iki sayı da tam kare olduğundan bu gerçek bir çözüm çiftidir. Buna karşılık \(1225\) gibi bir sayı, tekrar deseni CARE ile uyuşmadığı için daha ilk adımda elenir.
C++, Python ve Java uygulamaları önce tırnaklı kelime listesini okuyup düz kelimelere dönüştürür, ardından kelimeleri sıralanmış harflerine göre gruplar. Tek elemanlı gruplar anında atılır; daha büyük gruplar içlerindeki tüm sırasız anagram çiftlerini üretir.
Üç uygulamanın hepsi tam kareleri basamak sayılarına göre düzenler; böylece uzunluğu \(L\) olan bir kelime yalnızca \(L\) basamaklı karelerle karşılaştırılır. C++ uygulaması bunun da ötesine geçerek kare dizilerini tekrar desenlerine göre de ayırır ve kare değerleri için hızlı bir üyelik yapısı tutar. Python ve Java ise uzunluk kovalarını saklayıp ikinci sayının kare olup olmadığını tam sayı karekök testiyle doğrular.
Her anagram çifti için uygulama, uygun uzunluktaki kare adaylarını dolaşır; harf-rakam ve rakam-harf eşlemesini kurar; bire birliği bozan çakışmaları reddeder; partner kelimenin eşlenmiş sayısını üretir; baştaki sıfır durumlarını eler; sonra bu yeni sayının kare olup olmadığını kontrol eder. Her iki sayı da kareyse büyük olanı mevcut küresel maksimumla karşılaştırılır.
\(A_L\), uzunluğu \(L\) olan anagram çiftlerinin sayısı; \(S_L\) ise \(L\) basamaklı kare sayısı olsun. Tek bir kareyi tek bir kelime çifti üzerinde doğrulamak \(O(L)\) zaman alır; çünkü her konum sabit sayıda kez işlenir.
Böylece Python ve Java uygulamalarının çalışma süresi
$$O\!\left(\sum_L A_L S_L L\right)$$
olur. Bellek kullanımı, saklanan kare dizileri ve kelime grupları için \(O\!\left(\sum_L S_L\right)\) mertebesindedir. C++ uygulaması aynı dış yapıyı korur, fakat her kelime deseni için yalnızca uyumlu kare deseni kovasına baktığı için pratikte aday sayısını azaltır. Problem boyutu küçük kaldığından bütün sürümler rahatça çalışır.
Se da una lista de palabras inglesas. Solo interesan los pares que son anagramas, es decir, los que contienen exactamente las mismas letras en distinto orden. Buscamos una biyección entre letras y dígitos tal que ambas palabras se conviertan en enteros decimales, ninguno empiece con 0 y ambos sean cuadrados perfectos.
La respuesta es el mayor cuadrado que aparezca en cualquier par válido. Como una palabra de longitud \(L\) solo puede transformarse en un número de \(L\) cifras, la búsqueda es finita y se puede organizar por longitudes.
La clave no es probar todas las sustituciones posibles, sino identificar las invariantes correctas: las clases de anagramas, el patrón de repeticiones de letras y el intervalo finito de cuadrados de \(L\) cifras. Las implementaciones siguen exactamente esa estructura.
Ordenamos alfabéticamente las letras de cada palabra. Las palabras con la misma forma ordenada pertenecen a la misma clase de anagramas, y solo esas clases pueden producir una solución. Si una clase contiene \(m\) palabras, solo hay que revisar sus \(\binom{m}{2}\) pares no ordenados.
Para un par fijo \((W_1,W_2)\), la longitud común es \(L\). Por tanto, los cuadrados candidatos son exactamente los que satisfacen
$$10^{L-1} \le n^2 < 10^L.$$
Su cantidad viene dada por
$$S_L=\left\lfloor \sqrt{10^L-1} \right\rfloor-\left\lceil \sqrt{10^{L-1}} \right\rceil+1.$$
Así, el problema deja de ser una búsqueda sobre todas las asignaciones de dígitos y pasa a ser un barrido finito sobre cuadrados de la longitud correcta.
Una sustitución válida debe ser biyectiva: la misma letra siempre recibe el mismo dígito y dos letras distintas no pueden compartirlo. Por eso importa más la estructura de repeticiones que los valores concretos.
Definamos la firma de patrón \(\pi(s)\) de una cadena \(s=s_1s_2\cdots s_L\) numerando los símbolos por orden de primera aparición. Entonces
$$\pi(\text{CARE})=(0,1,2,3),\qquad \pi(\text{MEET})=(0,1,1,2),$$
y también
$$\pi(1296)=(0,1,2,3),\qquad \pi(1225)=(0,1,1,2).$$
Una palabra \(W\) puede emparejarse con una cadena de dígitos \(D\) si y solo si \(\pi(W)=\pi(D)\), además de exigir que el primer dígito no sea 0. Esta observación explica la optimización más importante: los cuadrados pueden agruparse por firma de patrón, de modo que una palabra con repeticiones como \((0,1,1,2)\) nunca se compara con un cuadrado de patrón \((0,1,2,3)\).
Supongamos que \(W_1\) se hace corresponder con un cuadrado \(D_1\) de \(L\) cifras. Si esa correspondencia es válida, entonces cada letra del alfabeto usado por el par ya tiene un dígito único asignado. Como \(W_2\) utiliza exactamente las mismas letras, la segunda cadena \(D_2\) queda fijada por la misma biyección; no existe una segunda búsqueda independiente.
Por tanto, cada prueba tiene una estructura precisa: elegir \(D_1\), verificar la biyección \(W_1 \leftrightarrow D_1\), construir \(D_2\) leyendo las letras de \(W_2\), rechazar el caso si \(D_2\) empieza con 0 y comprobar por último si \(D_2\) también es cuadrado. Si todo eso se cumple, se obtiene un par válido de cuadrados anagramáticos.
El par CARE/RACE tiene longitud \(L=4\), así que solo importan los cuadrados de cuatro cifras. Son los cuadrados desde \(32^2\) hasta \(99^2\), porque
$$1000 \le n^2 \le 9999.$$
Tomemos \(D_1=1296=36^2\). Su patrón de dígitos es \((0,1,2,3)\), igual que el de CARE, así que obtenemos la biyección
$$C\mapsto 1,\qquad A\mapsto 2,\qquad R\mapsto 9,\qquad E\mapsto 6.$$
Aplicada a RACE produce
$$RACE \mapsto 9216 = 96^2.$$
Como ambos valores son cuadrados perfectos, el par es válido. En cambio, un cuadrado como \(1225\) falla enseguida porque su patrón repetido no encaja con una palabra de cuatro letras distintas.
Las implementaciones en C++, Python y Java empiezan leyendo la lista de palabras entrecomilladas, limpiándola para obtener solo palabras y agrupándolas por su firma de letras ordenadas. Las clases de tamaño 1 se descartan inmediatamente; las demás generan todos los pares de anagramas sin orden.
Las tres implementaciones organizan los cuadrados perfectos por número de cifras, de manera que una palabra de longitud \(L\) solo se compara con cuadrados de \(L\) cifras. La implementación en C++ añade una capa extra: también agrupa las cadenas numéricas por patrón de repetición y mantiene una estructura rápida de pertenencia para los valores cuadrados. Las versiones en Python y Java conservan los cubos por longitud y validan el segundo número con una raíz cuadrada entera.
Para cada par de anagramas, la implementación recorre los cuadrados candidatos de la longitud correcta, construye la correspondencia letra-dígito y dígito-letra, rechaza cualquier colisión que rompa la biyección, forma el valor asignado a la palabra compañera, descarta ceros iniciales y comprueba después si ese valor también es cuadrado. Cuando ambos números son cuadrados, el mayor de los dos se compara con el mejor valor global hallado hasta ese momento.
Sea \(A_L\) el número de pares de anagramas de longitud \(L\), y sea \(S_L\) el número de cuadrados de \(L\) cifras. Verificar un cuadrado frente a un par cuesta \(O(L)\), porque cada posición se procesa solo un número constante de veces.
Por tanto, las versiones de Python y Java ejecutan
$$O\!\left(\sum_L A_L S_L L\right),$$
con un uso de memoria \(O\!\left(\sum_L S_L\right)\) para almacenar las cadenas de cuadrados y las agrupaciones de palabras. La versión en C++ mantiene la misma estructura global, pero reduce el número real de candidatos restringiendo cada palabra al cubo de cuadrados con el mismo patrón. En la práctica, el tamaño del problema sigue siendo suficientemente pequeño para que la búsqueda sea cómoda.
题目给出一组英文单词。真正有机会产生答案的，只是那些互为变位词的单词对，也就是字母完全相同但排列顺序不同的单词。我们要寻找一个字母到数字的双射，使得这两个单词都能被转换成十进制整数，两个整数都不能以 0 开头，而且都必须是完全平方数。
最终答案是所有有效配对中出现的最大平方数。由于长度为 \(L\) 的单词只能映射成 \(L\) 位数，所以搜索空间天然可以按单词长度拆开，而且每一部分都是有限的。
这道题的关键不是暴力枚举所有字母数字替换，而是先抓住几个真正决定问题结构的数学对象：变位词分组、重复模式、以及固定长度平方数的有限区间。题目中的实现正是围绕这些对象展开的。
把每个单词的字母按字典序排序。排序结果相同的单词属于同一个变位词类，只有这样的类才可能产生合法答案。若某一类中有 \(m\) 个单词，那么真正需要检查的只是其中的 \(\binom{m}{2}\) 个无序单词对。
对于固定的一对 \((W_1,W_2)\)，它们的公共长度记为 \(L\)。于是候选平方数只能来自区间
$$10^{L-1} \le n^2 < 10^L.$$
\(L\) 位平方数的个数为
$$S_L=\left\lfloor \sqrt{10^L-1} \right\rfloor-\left\lceil \sqrt{10^{L-1}} \right\rceil+1.$$
这一步已经把问题从“所有可能的数字赋值”缩减成“长度正确的一批平方数”。
合法映射必须是双射：同一个字母在所有位置上必须对应同一个数字，不同字母又不能共用一个数字。因此，最重要的并不是某个具体数字是多少，而是“哪些位置必须相同，哪些位置必须不同”这一重复结构。
定义字符串 \(s=s_1s_2\cdots s_L\) 的模式签名 \(\pi(s)\)：按照字符第一次出现的顺序给它们编号。例如
$$\pi(\text{CARE})=(0,1,2,3),\qquad \pi(\text{MEET})=(0,1,1,2),$$
而数字串也同样可以这样编码：
$$\pi(1296)=(0,1,2,3),\qquad \pi(1225)=(0,1,1,2).$$
于是，一个单词 \(W\) 能够和某个数字串 \(D\) 建立双射，当且仅当 \(\pi(W)=\pi(D)\)，再加上首位数字不能为 0 这一条件。这个观察非常重要，因为它说明很多平方数根本不用试。最优化的实现会先把同长度平方数按照模式签名分桶，这样具有 \((0,1,1,2)\) 模式的单词绝不会去尝试 \((0,1,2,3)\) 模式的平方数。
设 \(W_1\) 对应某个 \(L\) 位平方数 \(D_1\)。如果这种对应是合法的，那么该变位词对里出现的每个字母都已经获得唯一数字。由于 \(W_2\) 使用的是同一组字母，所以第二个数字串 \(D_2\) 不需要重新搜索，它会被同一个字母到数字的双射逐位唯一决定。
因此，每次检查都遵循同一个逻辑：先选一个候选平方数 \(D_1\)，验证 \(W_1 \leftrightarrow D_1\) 是否确实构成双射，再把同一映射应用到 \(W_2\) 上得到 \(D_2\)，若 \(D_2\) 以 0 开头就直接舍弃，否则判断 \(D_2\) 是否仍然是平方数。全部条件同时成立时，才得到一个有效的平方变位词对。
CARE/RACE 的长度是 \(L=4\)，所以只需要考虑四位平方数。它们正好是从 \(32^2\) 到 \(99^2\)，因为
$$1000 \le n^2 \le 9999.$$
取 \(D_1=1296=36^2\)。它的数字模式是 \((0,1,2,3)\)，与 CARE 的字母模式完全一致，因此可以得到映射
$$C\mapsto 1,\qquad A\mapsto 2,\qquad R\mapsto 9,\qquad E\mapsto 6.$$
把同一映射应用到 RACE，得到
$$RACE \mapsto 9216 = 96^2.$$
这说明 \((1296,9216)\) 是一个真正合法的平方数配对。反过来，如果尝试 \(1225\) 这样的四位平方数，它的模式中有重复数字，而 CARE 四个字母互不相同，因此这种候选会在模式比较阶段被立刻排除。
C++、Python 和 Java 三个实现都会先读入带引号的单词列表，去掉格式外壳后得到纯单词，再按排序后的字母序列进行分组。只有大小至少为 2 的分组会继续保留，并从中生成全部无序变位词对。
三种实现都会先按位数整理平方数，使长度为 \(L\) 的单词只和 \(L\) 位平方数比较。C++ 实现还多做了一层预处理：把平方数字符串再按重复模式分组，并为平方值建立快速查找结构。Python 和 Java 保留位数分组后，在生成第二个数时使用整数平方根来判断它是否为平方数。
对于每一对变位词，程序遍历同长度的候选平方数，构造字母到数字以及数字到字母的双向对应关系；一旦发现同字母映到不同数字或不同字母映到同一数字，就立即舍弃；然后构造另一个单词对应的整数，排除前导 0，最后检查这个整数是否也是平方数。若两个值都为平方数，就用其中较大的那个更新全局最优答案。
记 \(A_L\) 为长度为 \(L\) 的变位词对数量，\(S_L\) 为 \(L\) 位平方数数量。把一个平方数与一个单词对进行验证，需要 \(O(L)\) 时间，因为每个位置只会被读取和写入常数次。
因此，Python 和 Java 实现的时间复杂度为
$$O\!\left(\sum_L A_L S_L L\right),$$
空间复杂度则由平方数字符串存储和单词分组主导，为 \(O\!\left(\sum_L S_L\right)\)。C++ 实现的外层框架相同，但它通过“只查看模式匹配的平方数桶”显著降低了实际候选数量，所以常数因子更小。由于题目中的单词长度范围并不大，整体搜索规模是完全可控的。
Дан список английских слов. Нас интересуют только те пары, которые являются анаграммами, то есть состоят из одних и тех же букв в разном порядке. Нужно найти биекцию между буквами и цифрами, при которой оба слова превращаются в десятичные числа, ни одно из них не начинается с нуля, и оба оказываются полными квадратами.
Ответом служит наибольший квадрат, возникающий хотя бы в одной такой допустимой паре. Поскольку слово длины \(L\) может перейти только в \(L\)-значное число, поиск естественным образом разбивается по длинам слов и остается конечным.
Эффективное решение строится не на переборе всех замен, а на выделении правильных инвариантов: классов анаграмм, шаблона повторений символов и конечного диапазона \(L\)-значных квадратов. Именно эти объекты лежат в основе реализации.
Отсортируем буквы каждого слова по алфавиту. Слова с одинаковой отсортированной формой принадлежат одному классу анаграмм, и только внутри такого класса вообще может появиться решение. Если в классе \(m\) слов, то проверять нужно лишь \(\binom{m}{2}\) неупорядоченных пар.
Для фиксированной пары \((W_1,W_2)\) общая длина равна \(L\). Следовательно, кандидатами являются только квадраты, удовлетворяющие
$$10^{L-1} \le n^2 < 10^L.$$
Число таких \(L\)-значных квадратов равно
$$S_L=\left\lfloor \sqrt{10^L-1} \right\rfloor-\left\lceil \sqrt{10^{L-1}} \right\rceil+1.$$
Тем самым задача сводится к конечному списку квадратов нужной длины, а не к бесконечному пространству подстановок.
Допустимая замена обязана быть биекцией: одна и та же буква всегда получает одну и ту же цифру, а две разные буквы не могут разделять одну цифру. Поэтому решающее значение имеет не само значение цифр, а схема совпадений и различий по позициям.
Определим сигнатуру шаблона \(\pi(s)\) для строки \(s=s_1s_2\cdots s_L\), нумеруя символы в порядке их первого появления. Тогда, например,
$$\pi(\text{CARE})=(0,1,2,3),\qquad \pi(\text{MEET})=(0,1,1,2),$$
а для числовых строк аналогично
$$\pi(1296)=(0,1,2,3),\qquad \pi(1225)=(0,1,1,2).$$
Слово \(W\) может быть биективно сопоставлено строке цифр \(D\) тогда и только тогда, когда \(\pi(W)=\pi(D)\), плюс требуется, чтобы первая цифра не была нулем. Именно поэтому самая сильная реализация заранее группирует квадраты по шаблону: слово с шаблоном \((0,1,1,2)\) не нужно сравнивать с квадратами шаблона \((0,1,2,3)\).
Пусть \(W_1\) сопоставлено некоторому \(L\)-значному квадрату \(D_1\). Если сопоставление корректно, то каждая буква, встречающаяся в паре анаграмм, уже получила ровно одну цифру. Так как \(W_2\) использует тот же мультимножество букв, вторая строка цифр \(D_2\) полностью определяется той же биекцией; отдельного второго поиска здесь нет.
Поэтому каждая проверка устроена одинаково: выбирается \(D_1\), проверяется биекция \(W_1 \leftrightarrow D_1\), из букв \(W_2\) строится \(D_2\), случай с ведущим нулем отбрасывается, а затем выясняется, является ли \(D_2\) полным квадратом. Если все условия выполнены, получаем допустимую пару квадратов-аннаграмм.
У пары CARE/RACE длина \(L=4\), значит нужны только четырехзначные квадраты. Это квадраты от \(32^2\) до \(99^2\), поскольку
$$1000 \le n^2 \le 9999.$$
Возьмем \(D_1=1296=36^2\). Его шаблон цифр равен \((0,1,2,3)\), что совпадает с шаблоном слова CARE, поэтому получаем биекцию
$$C\mapsto 1,\qquad A\mapsto 2,\qquad R\mapsto 9,\qquad E\mapsto 6.$$
Применяя ту же замену к RACE, получаем
$$RACE \mapsto 9216 = 96^2.$$
Оба числа являются квадратами, следовательно, это корректная пара. Напротив, число \(1225\) отсекается сразу, потому что его шаблон повторений несовместим со словом из четырех различных букв.
Реализации на C++, Python и Java сначала читают список слов в кавычках, очищают его до обычных строк и группируют слова по подписи, полученной сортировкой букв. Группы размера 1 немедленно отбрасываются, а из остальных строятся все неупорядоченные пары анаграмм.
Все три реализации раскладывают полные квадраты по длине записи, чтобы слово длины \(L\) сравнивалось только с \(L\)-значными квадратами. Реализация на C++ идет дальше: она дополнительно разбивает числовые строки по шаблону повторений и хранит быстрый тест принадлежности для квадратных значений. Версии на Python и Java ограничиваются корзинами по длине и проверяют второе число через целочисленный квадратный корень.
Для каждой пары анаграмм реализация перебирает квадраты подходящей длины, строит двустороннее соответствие буква-цифра и цифра-буква, отбрасывает любые конфликты, формирует число для второго слова, исключает ведущий ноль и затем проверяет, является ли это число квадратом. Если оба значения квадратные, большее из них сравнивается с текущим глобальным максимумом.
Пусть \(A_L\) обозначает число пар анаграмм длины \(L\), а \(S_L\) - число \(L\)-значных квадратов. Проверка одного квадрата для одной пары занимает \(O(L)\), потому что каждая позиция просматривается лишь константное число раз.
Отсюда время работы реализаций на Python и Java равно
$$O\!\left(\sum_L A_L S_L L\right),$$
а память определяется хранением квадратных строк и групп слов, то есть имеет порядок \(O\!\left(\sum_L S_L\right)\). У варианта на C++ та же внешняя схема, но фактическое число проверок меньше, потому что он ограничивает каждый шаблон слова только соответствующей корзиной квадратов. Для размеров входа из Project Euler этого более чем достаточно.
تعطينا المسألة قائمة من الكلمات الإنجليزية. الأزواج المهمة فقط هي أزواج الأناغرام، أي الكلمات التي تحتوي على الحروف نفسها ولكن بترتيب مختلف. المطلوب إيجاد تقابل واحد لواحد بين الحروف والأرقام بحيث تتحول الكلمتان إلى عددين عشريين، ولا يبدأ أي منهما بالصفر، ويكون العددان معًا مربعين كاملين.
الجواب المطلوب هو أكبر مربع يظهر داخل أي زوج صالح من هذا النوع. وبما أن كلمة طولها \(L\) لا يمكن أن تقابل إلا عددًا مكوّنًا من \(L\) خانات، فإن مساحة البحث تصبح منتهية ويمكن تقسيمها طبيعيًا بحسب طول الكلمات.
الفكرة الفعالة هنا ليست تجربة كل تعيين ممكن للحروف والأرقام، بل تحديد البنى الرياضية التي تحكم المسألة فعلاً: فئات الأناغرام، ونمط التكرار داخل الكلمة أو العدد، ومجال المربعات ذات \(L\) خانات. هذا هو الإطار الذي تتبعه الحلول البرمجية.
نرتب حروف كل كلمة ترتيبًا أبجديًا. الكلمات التي تعطي الصيغة المرتبة نفسها تنتمي إلى الفئة نفسها من الأناغرام، ولا يمكن أن يأتي حل صحيح إلا من داخل هذه الفئات. إذا احتوت فئة ما على \(m\) كلمات، فكل ما نحتاجه هو فحص الأزواج غير المرتبة وعددها \(\binom{m}{2}\).
ولزوج ثابت \((W_1,W_2)\) يكون الطول المشترك هو \(L\). إذًا فالمربعات المرشحة هي فقط التي تحقق
$$10^{L-1} \le n^2 < 10^L.$$
وعدد هذه المربعات يساوي
$$S_L=\left\lfloor \sqrt{10^L-1} \right\rfloor-\left\lceil \sqrt{10^{L-1}} \right\rceil+1.$$
وبذلك تنتقل المسألة من فضاء ضخم من التعيينات الممكنة إلى قائمة منتهية من المربعات ذات الطول الصحيح.
أي تعيين صالح يجب أن يكون تقابلًا: الحرف نفسه يجب أن يأخذ الرقم نفسه دائمًا، وحرفان مختلفان لا يجوز أن يشتركا في الرقم نفسه. لهذا السبب لا تكون القيم نفسها هي العامل الحاسم، بل مواضع التساوي والاختلاف بين الرموز.
لنعرّف توقيع النمط \(\pi(s)\) للسلسلة \(s=s_1s_2\cdots s_L\) بترقيم الرموز حسب أول ظهور لها. عندئذ نحصل مثلًا على
$$\pi(\text{CARE})=(0,1,2,3),\qquad \pi(\text{MEET})=(0,1,1,2),$$
وكذلك
$$\pi(1296)=(0,1,2,3),\qquad \pi(1225)=(0,1,1,2).$$
يمكن لكلمة \(W\) أن تطابق سلسلة أرقام \(D\) إذا وفقط إذا تحقق \(\pi(W)=\pi(D)\)، مع شرط إضافي هو أن الرقم الأول ليس صفرًا. ولهذا السبب تجمع أفضل نسخة من التنفيذ المربعات مسبقًا بحسب هذا التوقيع: كلمة ذات نمط \((0,1,1,2)\) لا حاجة أبدًا إلى اختبارها أمام مربع ذي نمط \((0,1,2,3)\).
افترض أن \(W_1\) طابقت مربعًا ذا \(L\) خانات نرمز له بـ \(D_1\). إذا كانت هذه المطابقة صحيحة، فهذا يعني أن كل حرف موجود في زوج الأناغرام قد حصل بالفعل على رقم وحيد. وبما أن \(W_2\) تستعمل مجموعة الحروف نفسها، فإن السلسلة الثانية \(D_2\) تتحدد حتميًا من خلال التقابل نفسه، ولا توجد شجرة بحث مستقلة ثانية.
إذن كل اختبار مرشح يسير وفق الخطوات التالية: اختيار \(D_1\)، التحقق من صحة التقابل \(W_1 \leftrightarrow D_1\)، بناء \(D_2\) من حروف \(W_2\) بالتقابل نفسه، رفض الحالة إذا بدأ \(D_2\) بصفر، ثم فحص ما إذا كان \(D_2\) مربعًا كاملًا أيضًا. إذا تحققت الشروط كلها نحصل على زوج صحيح من مربعات الأناغرام.
الزوج CARE/RACE طوله \(L=4\)، لذلك نهتم فقط بالمربعات ذات الأربع خانات. وهذه هي المربعات من \(32^2\) إلى \(99^2\)، لأن
$$1000 \le n^2 \le 9999.$$
لنأخذ \(D_1=1296=36^2\). نمطه الرقمي هو \((0,1,2,3)\)، وهو يطابق نمط CARE، ومنه نحصل على التقابل
$$C\mapsto 1,\qquad A\mapsto 2,\qquad R\mapsto 9,\qquad E\mapsto 6.$$
وعند تطبيق هذا التقابل على RACE نحصل على
$$RACE \mapsto 9216 = 96^2.$$
بما أن العددين مربعان كاملان، فهذا زوج صالح فعلاً. أما عدد مثل \(1225\) فيُستبعد مباشرة، لأن نمط تكراره لا ينسجم مع كلمة مكوّنة من أربعة أحرف مختلفة.
تبدأ تطبيقات C++ و Python و Java بقراءة قائمة الكلمات المكتوبة بين علامتي اقتباس، ثم تحويلها إلى كلمات صافية وتجميعها بحسب ترتيب حروفها بعد الفرز. المجموعات التي تحتوي على كلمة واحدة فقط تُهمل فورًا، أما المجموعات الأكبر فتنتج كل أزواج الأناغرام غير المرتبة بداخلها.
كل التطبيقات الثلاثة ترتب المربعات الكاملة بحسب عدد الخانات، بحيث لا تُقارن كلمة طولها \(L\) إلا بمربعات من \(L\) خانات. نسخة C++ تضيف خطوة أقوى: فهي تجمع السلاسل الرقمية أيضًا بحسب نمط التكرار، وتحفظ بنية سريعة لفحص كون القيمة مربعًا. أما نسختا Python و Java فتكتفيان بالتجميع حسب الطول، ثم تتحققان من العدد الثاني عبر جذر تربيعي صحيح.
لكل زوج أناغرام، يمر التنفيذ على المربعات المرشحة ذات الطول المناسب، ويبني المطابقة في الاتجاهين حرف إلى رقم ورقم إلى حرف، ويرفض أي تعارض يخرق شرط التقابل، ثم ينشئ القيمة المقابلة للكلمة الثانية، ويستبعد الصفر البادئ، وأخيرًا يفحص هل هذه القيمة مربع كامل أيضًا. إذا كان العددان مربعين، فإن الأكبر بينهما يُقارَن مع أفضل قيمة عالمية تم الوصول إليها.
لنرمز بـ \(A_L\) إلى عدد أزواج الأناغرام ذات الطول \(L\)، وبـ \(S_L\) إلى عدد المربعات ذات \(L\) خانات. التحقق من مربع واحد مع زوج كلمات واحد يكلف \(O(L)\)، لأن كل موضع يُفحص عددًا ثابتًا من المرات.
وعليه فإن زمني التنفيذ في نسختي Python و Java يساويان
$$O\!\left(\sum_L A_L S_L L\right),$$
أما الذاكرة فتكون من رتبة \(O\!\left(\sum_L S_L\right)\) لتخزين سلاسل المربعات وتجميعات الكلمات. تحتفظ نسخة C++ بالبنية العامة نفسها، لكنها تقلل عدد المرشحين فعليًا لأنها لا تختبر إلا المربعات الموجودة في السلة المطابقة لنمط الكلمة. لذلك يبقى الحجم العملي للبحث مناسبًا تمامًا لهذه المسألة.