Project Euler 98: Find the largest square number formed by pairs of encoded anagrams

Project Euler 98 Problem Description

Project Euler 98: By replacing each of the letters in the word CARE with 1, 2, 9, and 6 respectively, we form a square number: 1296 = 36². What is remarkable is that, by using the same digital substitutions, the anagram, RACE, also forms a square number: 9216 = 96². We shall call CARE (and RACE) a square anagram word pair and specify further that leading zeroes are not permitted, neither may a different letter have the same digital value as another letter.

Using words.txt (right click and ‘Save Link/Target As…’), a 16K text file containing nearly two-thousand common English words, find all the square anagram word pairs (a palindromic word is NOT considered to be an anagram of itself).

What is the largest square number formed by any member of such a pair?

NOTE: All anagrams formed must be contained in the given text file.

Analysis

A simple and straightforward implementation that performs as follows:
1. Read words into a list from network resource. Trim first and last quote characters. Store each word as a tuple: the word and a list of the sorted letters in the word. Ignore words shorter than 5 letters (ignoring quotes).

2. Build anagram word pair list for the word list. Clearly, 3 and fewer letter words are non-contenders, nor are 4 letter words. We are given 96², and 97², 98², and 99² wouldn’t work because they repeat a digit or contain the dreaded zero and unable to leave a maximum greater than the given 9216.

3. Find all combinations of values using the pattern set in word’s anagram. You could check duplicate patterns for the same words size and ignore those, but I didn’t do that. Also note that I’m convinced zero will never be a factor.

4. Collect maximum square values for an ultimate global maximum.

5. Print the maximum.

Project Euler 98 Solution

Afterthoughts

• Find the top anagram for a set of digits 4 through 13:
  

from collections import defaultdict
for digits in range(3,14):
	d = defaultdict(list)
	for i in xrange(int((10**(digits-1))**0.5), int((10**digits)**0.5)+1):
		j = ''.join(sorted(str(i*i)))
		d[j].append(i)
	max_key = max(d, key= lambda x: len(set(d[x])))
	print d[max_key][-1]**2