Problem 98: Anagramic Squares

Project Euler Problem 98 Solution

EulerSolve provides an optimized solution for Project Euler Problem 98, Anagramic Squares, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary 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. Mathematical Approach 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. Anagram Classes Fix the Search Domain 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$....

Detailed mathematical approach

Problem Summary

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.

Mathematical Approach

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.

Anagram Classes Fix the Search Domain

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.

Repetition Pattern Is the Key Invariant

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)$.

Once the First Square Is Chosen, the Second Number Is Forced

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.

Worked Example: CARE and RACE

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.

How the Code Works

Grouping the Words

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.

Preparing Square Candidates

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.

Testing and Updating the Best Answer

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.

Complexity Analysis

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.

Footnotes and References

Problem page: https://projecteuler.net/problem=98
Anagram: Wikipedia - Anagram
Perfect square: Wikipedia - Square number
Bijection: Wikipedia - Bijection
Integer square root: Wikipedia - Integer square root

Problem 98 source code

C++

#include <algorithm>
#include <cmath>
#include <cstdint>
#include <fstream>
#include <iostream>
#include <map>
#include <sstream>
#include <stdexcept>
#include <string>
#include <unordered_set>
#include <vector>
#include <array>
#include <functional>

namespace {

using u64 = std::uint64_t;

struct Options {
    std::string file = "resources/documents/0098_words.txt";
    bool run_checkpoints = true;
};

struct SquareCache {
    std::map<std::string, std::vector<std::string>> pattern_to_squares;
    std::unordered_set<u64> square_values;
};

bool parse_string_after_prefix(const std::string& arg,
                               const std::string& prefix,
                               std::string& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    value = tail;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);

        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_string_after_prefix(arg, "--file=", options.file)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return true;
}

std::vector<std::string> parse_words_csv(const std::string& text) {
    std::vector<std::string> words;
    std::string token;
    std::istringstream input(text);

    while (std::getline(input, token, ',')) {
        std::string word;
        for (char c : token) {
            if (c >= 'A' && c <= 'Z') {
                word.push_back(c);
            }
        }
        if (!word.empty()) {
            words.push_back(word);
        }
    }

    return words;
}

std::string pattern_key(const std::string& s) {
    std::unordered_map<char, int> index;
    int next_index = 0;
    std::string key;

    for (char c : s) {
        auto it = index.find(c);
        if (it == index.end()) {
            it = index.emplace(c, next_index++).first;
        }
        key += std::to_string(it->second);
        key.push_back(',');
    }

    return key;
}

u64 pow10_u64(int n) {
    u64 value = 1;
    for (int i = 0; i < n; ++i) {
        value *= 10ULL;
    }
    return value;
}

SquareCache build_square_cache_for_length(const int length) {
    const u64 low = pow10_u64(length - 1);
    const u64 high = pow10_u64(length) - 1ULL;

    const u64 start = static_cast<u64>(std::ceil(std::sqrt(static_cast<long double>(low))));
    const u64 end = static_cast<u64>(std::floor(std::sqrt(static_cast<long double>(high))));

    SquareCache cache;
    for (u64 x = start; x <= end; ++x) {
        const u64 sq = x * x;
        const std::string digits = std::to_string(sq);
        cache.square_values.insert(sq);
        cache.pattern_to_squares[pattern_key(digits)].push_back(digits);
    }

    return cache;
}

bool map_word_to_digits(const std::string& word,
                        const std::string& digits,
                        std::array<int, 26>& letter_to_digit,
                        std::array<int, 10>& digit_to_letter) {
    letter_to_digit.fill(-1);
    digit_to_letter.fill(-1);

    for (std::size_t i = 0; i < word.size(); ++i) {
        const int letter = word[i] - 'A';
        const int digit = digits[i] - '0';

        const int mapped_digit = letter_to_digit[static_cast<std::size_t>(letter)];
        if (mapped_digit != -1 && mapped_digit != digit) {
            return false;
        }
        const int mapped_letter = digit_to_letter[static_cast<std::size_t>(digit)];
        if (mapped_letter != -1 && mapped_letter != letter) {
            return false;
        }

        letter_to_digit[static_cast<std::size_t>(letter)] = digit;
        digit_to_letter[static_cast<std::size_t>(digit)] = letter;
    }

    return true;
}

u64 mapped_value(const std::string& word, const std::array<int, 26>& letter_to_digit) {
    if (word.empty()) {
        return 0;
    }

    if (letter_to_digit[static_cast<std::size_t>(word[0] - 'A')] == 0) {
        return 0;
    }

    u64 value = 0;
    for (char c : word) {
        const int digit = letter_to_digit[static_cast<std::size_t>(c - 'A')];
        if (digit < 0) {
            return 0;
        }
        value = value * 10ULL + static_cast<u64>(digit);
    }
    return value;
}

u64 solve_from_words(const std::vector<std::string>& words) {
    std::map<std::string, std::vector<std::string>> anagram_groups;
    for (const std::string& word : words) {
        std::string sorted = word;
        std::sort(sorted.begin(), sorted.end());
        anagram_groups[sorted].push_back(word);
    }

    std::map<int, SquareCache> cache_by_length;
    for (const auto& [_, group] : anagram_groups) {
        if (group.size() < 2) {
            continue;
        }
        const int length = static_cast<int>(group[0].size());
        if (cache_by_length.find(length) == cache_by_length.end()) {
            cache_by_length.emplace(length, build_square_cache_for_length(length));
        }
    }

    u64 best = 0;
    std::array<int, 26> letter_to_digit{};
    std::array<int, 10> digit_to_letter{};

    for (const auto& [_, group] : anagram_groups) {
        if (group.size() < 2) {
            continue;
        }

        const int length = static_cast<int>(group[0].size());
        const SquareCache& cache = cache_by_length.at(length);

        for (std::size_t i = 0; i < group.size(); ++i) {
            for (std::size_t j = i + 1; j < group.size(); ++j) {
                const std::string& a = group[i];
                const std::string& b = group[j];

                const std::string key = pattern_key(a);
                auto it = cache.pattern_to_squares.find(key);
                if (it == cache.pattern_to_squares.end()) {
                    continue;
                }

                for (const std::string& sq_digits : it->second) {
                    if (!map_word_to_digits(a, sq_digits, letter_to_digit, digit_to_letter)) {
                        continue;
                    }
                    if (letter_to_digit[static_cast<std::size_t>(a[0] - 'A')] == 0) {
                        continue;
                    }

                    const u64 va = std::stoull(sq_digits);
                    const u64 vb = mapped_value(b, letter_to_digit);
                    if (vb == 0) {
                        continue;
                    }
                    if (cache.square_values.find(vb) == cache.square_values.end()) {
                        continue;
                    }

                    best = std::max(best, std::max(va, vb));
                }
            }
        }
    }

    return best;
}

u64 solve(const std::string& file_path) {
    std::ifstream input(file_path);
    if (!input) {
        throw std::runtime_error("Could not open words file: " + file_path);
    }

    std::ostringstream buffer;
    buffer << input.rdbuf();
    return solve_from_words(parse_words_csv(buffer.str()));
}

bool run_checkpoints() {
    const std::vector<std::string> words = {"CARE", "RACE", "STOP"};
    if (solve_from_words(words) != 9216ULL) {
        std::cerr << "Checkpoint failed for CARE/RACE" << '\n';
        return false;
    }

    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    try {
        std::cout << solve(options.file) << '\n';
    } catch (const std::exception& ex) {
        std::cerr << ex.what() << '\n';
        return 3;
    }

    return 0;
}

Python

# Problem 98: Anagramic squares
# Find the largest square number formed by anagram word pairs.

import os
from collections import defaultdict
from itertools import permutations
import math

def solve():
    script_dir = os.path.dirname(os.path.abspath(__file__))
    file_path = os.path.join(script_dir, '..', 'resources', 'documents', '0098_words.txt')
    with open(file_path) as f:
        content = f.read().strip()
    words = [w.strip('"') for w in content.split(',')]
    
    # Group anagrams
    groups = defaultdict(list)
    for w in words:
        key = ''.join(sorted(w))
        groups[key].append(w)
    
    anagram_pairs = []
    for key, ws in groups.items():
        if len(ws) >= 2:
            for i in range(len(ws)):
                for j in range(i+1, len(ws)):
                    anagram_pairs.append((ws[i], ws[j]))
    
    # Generate squares by digit count
    max_len = max(len(w) for pair in anagram_pairs for w in pair)
    squares_by_len = defaultdict(list)
    n = 1
    while len(str(n*n)) <= max_len:
        s = str(n*n)
        squares_by_len[len(s)].append(s)
        n += 1
    
    best = 0
    for w1, w2 in anagram_pairs:
        length = len(w1)
        for sq in squares_by_len[length]:
            # Try mapping w1 -> sq
            mapping = {}
            reverse = {}
            valid = True
            for c, d in zip(w1, sq):
                if c in mapping:
                    if mapping[c] != d:
                        valid = False; break
                else:
                    if d in reverse:
                        if reverse[d] != c:
                            valid = False; break
                    mapping[c] = d
                    reverse[d] = c
            if not valid:
                continue
            # Apply mapping to w2
            mapped = ''.join(mapping[c] for c in w2)
            if mapped[0] == '0':
                continue
            val = int(mapped)
            r = int(math.isqrt(val))
            if r * r == val:
                best = max(best, int(sq), val)
    
    print(best)

solve()

Java

import java.nio.file.*;
import java.util.*;

public class Euler98 {
    public static void main(String[] args) throws Exception {
        String content = Files.readString(Path.of("resources/documents/0098_words.txt")).trim();
        String[] words = content.split(",");
        for (int i = 0; i < words.length; i++)
            words[i] = words[i].replaceAll("\"", "");
        Map<String, List<String>> groups = new HashMap<>();
        for (String w : words) {
            char[] c = w.toCharArray();
            Arrays.sort(c);
            String k = new String(c);
            groups.computeIfAbsent(k, x -> new ArrayList<>()).add(w);
        }
        List<String[]> pairs = new ArrayList<>();
        int maxLen = 0;
        for (List<String> ws : groups.values())
            if (ws.size() >= 2) {
                for (int i = 0; i < ws.size(); i++)
                    for (int j = i + 1; j < ws.size(); j++) {
                        pairs.add(new String[] { ws.get(i), ws.get(j) });
                        maxLen = Math.max(maxLen, ws.get(i).length());
                    }
            }
        Map<Integer, List<String>> sqByLen = new HashMap<>();
        for (long n = 1; Long.toString(n * n).length() <= maxLen; n++)
            sqByLen.computeIfAbsent(Long.toString(n * n).length(), k -> new ArrayList<>()).add(Long.toString(n * n));
        long best = 0;
        for (String[] pair : pairs) {
            int len = pair[0].length();
            List<String> sqs = sqByLen.getOrDefault(len, Collections.emptyList());
            for (String sq : sqs) {
                Map<Character, Character> m = new HashMap<>();
                Map<Character, Character> r = new HashMap<>();
                boolean ok = true;
                for (int i = 0; i < len; i++) {
                    char c = pair[0].charAt(i), d = sq.charAt(i);
                    if (m.containsKey(c)) {
                        if (m.get(c) != d) {
                            ok = false;
                            break;
                        }
                    } else {
                        if (r.containsKey(d)) {
                            if (r.get(d) != c) {
                                ok = false;
                                break;
                            }
                        }
                        m.put(c, d);
                        r.put(d, c);
                    }
                }
                if (!ok)
                    continue;
                StringBuilder sb = new StringBuilder();
                for (char c : pair[1].toCharArray())
                    sb.append(m.get(c));
                String mapped = sb.toString();
                if (mapped.charAt(0) == '0')
                    continue;
                long val = Long.parseLong(mapped);
                long rt = (long) Math.sqrt(val);
                if (rt * rt == val)
                    best = Math.max(best, Math.max(Long.parseLong(sq), val));
            }
        }
        System.out.println(best);
    }
}