Anagramic Squares

Itertools to the rescue! But first, we'll read the words we're working with.

with open("txt/0098_words.txt") as f:
    words = [word.strip('"') for line in f for word in line.split(',')]

We can then make groups where each word is an anagram of the other words in the group.

from itertools import groupby

anagram_groups = []
for _, g in groupby(sorted(words, key=sorted), key=sorted):
    g = tuple(g)
    if len(g) > 1:
        anagram_groups.append(g)

anagram_groups

[('BOARD', 'BROAD'),
 ('CREATION', 'REACTION'),
 ('CARE', 'RACE'),
 ('ACT', 'CAT'),
 ('DANGER', 'GARDEN'),
 ('DEAL', 'LEAD'),
 ('PHASE', 'SHAPE'),
 ('EARTH', 'HEART'),
 ('HATE', 'HEAT'),
 ('ARISE', 'RAISE'),
 ('MALE', 'MEAL'),
 ('LEAST', 'STEAL'),
 ('MEAN', 'NAME'),
 ('EARN', 'NEAR'),
 ('RATE', 'TEAR'),
 ('EAST', 'SEAT'),
 ('EAT', 'TEA'),
 ('INTRODUCE', 'REDUCTION'),
 ('CREDIT', 'DIRECT'),
 ('CENTRE', 'RECENT'),
 ('EXCEPT', 'EXPECT'),
 ('COURSE', 'SOURCE'),
 ('DOG', 'GOD'),
 ('SHEET', 'THESE'),
 ('FILE', 'LIFE'),
 ('FORMER', 'REFORM'),
 ('IGNORE', 'REGION'),
 ('ITEM', 'TIME'),
 ('QUIET', 'QUITE'),
 ('NOTE', 'TONE'),
 ('SURE', 'USER'),
 ('FORM', 'FROM'),
 ('NIGHT', 'THING'),
 ('SIGN', 'SING'),
 ('THROW', 'WORTH'),
 ('SHOUT', 'SOUTH'),
 ('HOW', 'WHO'),
 ('SHUT', 'THUS'),
 ('ITS', 'SIT'),
 ('NO', 'ON'),
 ('NOW', 'OWN'),
 ('POST', 'SPOT', 'STOP')]

When looking for square mappings, we only need to consider square numbers with the same number of digits as a given word. This means if word has $n$ characters, we'll only try to map squares between $10^{n-1}$ and $10^n$. Here's a function to iterate over all square numbers with a given number of digits.

def n_digit_square_numbers(n):
    low = ceil(sqrt(10^(n-1)))
    high = floor(sqrt(10^n - 1))
    for k in range(low, high + 1):
        yield k^2

Next, a function to generate those mappings. Per the problem, we'll only consider mappings that map distinct characters to distinct digits (i.e. injective mappings).

def square_mappings(word):
    n = len(word)
    for k in n_digit_square_numbers(n):
        tr = dict(zip(word, str(k)))
        if len(set(tr.values())) != len(tr):
            continue
            
        yield str.maketrans(tr)

Then, given two anagrams, we'll determine if they are a square anagram word pair by generating square mappings for one word, and checking if any of those mappings also result in a square number for the other word. If there are multiple such mappings, we'll return the one that makes the largest square number.

def square_anagram_word_pair_mapping(s, t):
    best = None
    maximum = float('-inf')
    
    for tr in square_mappings(s):
        m, n = s.translate(tr), t.translate(tr)
        if m[0] == '0' or n[0] == '0':
            continue

        m, n = int(m), int(n)
        if is_square(m) and is_square(n) and maximum < max(m, n):
            maximum = max(m, n)
            best = tr
            
    return best

Now we'll look at every anagram pair and find their best square mapping, if it exists.

from itertools import combinations

pairs = dict()
for group in anagram_groups:
    for s, t in combinations(group, 2):
        pairs[(s, t)] = square_anagram_word_pair_mapping(s, t)

With the best mappings, we can find the largest square that can be made from each pair.

max_squares = {(s, t): max(int(s.translate(tr)), int(t.translate(tr))) for ((s, t), tr) in pairs.items() if tr is not None}
max_squares

{('BOARD', 'BROAD'): 18769,
 ('CARE', 'RACE'): 9216,
 ('DEAL', 'LEAD'): 4761,
 ('HATE', 'HEAT'): 1936,
 ('MALE', 'MEAL'): 1936,
 ('MEAN', 'NAME'): 9604,
 ('RATE', 'TEAR'): 9604,
 ('EAST', 'SEAT'): 2916,
 ('EAT', 'TEA'): 961,
 ('DOG', 'GOD'): 961,
 ('FILE', 'LIFE'): 9216,
 ('NOTE', 'TONE'): 9216,
 ('HOW', 'WHO'): 961,
 ('SHUT', 'THUS'): 4761,
 ('ITS', 'SIT'): 961,
 ('NOW', 'OWN'): 961,
 ('POST', 'SPOT'): 2916,
 ('POST', 'STOP'): 9604}

max(max_squares.values())

18769

Copyright (C) 2025 filifa

This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International license and the BSD Zero Clause license.