Problem #98 asks us:
By replacing each of the letters in the word CARE with 1, 2, 9, and 6 respectively, we form a square number: 1296 = \(36^{2}\). What is remarkable is that, by using the same digital substitutions, the anagram, RACE, also forms a square number: 9216 = \(96^{2}\). 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 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.
So we break this down into several parts. 1) Anagrams have to be the same length. 2) Remove words we’ve already paired up or failed to find an anagram for. 3) Each letter must have 1 numerical value assigned to it and used consistently. 4) Likewise each number can only be assigned to one letter.
With those four tips we can structure our solution like this. Build all of the anagram pairs and remove the words we’ve paired up from the main word list. Build a list of all of the square numbers from 2 – 1000000000. For each pair take the first word and find a square that is the same length. Assign each letter to a number without repeats of either letters or numbers (each pairing must be unique in both directions). Map the letter->number combination onto the second word. Parse the mapped second word to a ulong and make sure that it matches the length of the square assigned to word one. If they are the same length check (this will mean that there is not leading zero’s etc) then check the list of square numbers to see if the number created by mapping the second number appears in the list. If the mapped second word is a square then all we have to check is which is higher either the square assigned to the first word or the square we generated with the second. Take the highest one and go to the next anagram word pair.
This approach makes it so we don’t have to check to see if the square number assigned to word one and the generated square are the same because the only way that could happen is if word one and word two are the same words. There are no duplicates in the word list so we can eliminate all checking for that condition. Also the way we move through the list makes it impossible to compare a word to itself meaning we don’t have to waste time checking that either.
Despite the code being a mess it runs far faster than it looks like it should. Solution provided in c#/mono and runs in ~1.5 seconds.
* It’s left as an exercise to the reader to figure out how to get the word list into the words variable. I don’t want to screw up search engines by posting 1786 random words.
using System;
using System.Collections.Generic;
namespace Problem98
{
class MainClass
{
public static List<string> words = new List<string>();
public static List<List<string>> AnagramWordPairings = new List<List<string>>();
public static List<ulong> squares = new List<ulong>();
public static void Main (string[] args)
{
for (ulong i = 2; i <= 31700; i++)
{
squares.Add(i*i);
}
Max("rat","tar");
while (words.Count > 0)
{
string primary = words[0];
List<string> anagramset = new List<string>();
anagramset.Add(primary);
for (int i = 1; i < words.Count;i++)
{
if (Anagrams(primary,words[i]))
anagramset.Add(words[i]);
}
if (anagramset.Count ==1)
words.Remove(primary);
else
{
foreach (string s in anagramset)
words.Remove(s);
AnagramWordPairings.Add(anagramset);
}
}
ulong max = 0;
foreach(List<string> s in AnagramWordPairings)
{
ulong tmax = Max(s[0],s[1]);
if (tmax > max)
max = tmax;
}
Console.WriteLine(max);
}
public static ulong Max (string s1,string s2)
{
ulong max = 0;
foreach(ulong sq in squares)
{
if (sq.ToString().Length == s1.Length)
{
char[] premap = s1.ToCharArray();
int digits = sq.ToString().Length;
Dictionary<char,char> map = new Dictionary<char, char>();
foreach (char c in premap)
{
if (!map.ContainsKey(c) &&
!map.ContainsValue(sq.ToString()[s1.IndexOf(c.ToString())]))
map.Add(c,sq.ToString()[s1.IndexOf(c.ToString())]);
}
string ts2 = (string)s2.Clone();
foreach (char c in map.Keys)
{
ts2 = ts2.Replace(c,map[c]);
}
try
{
ulong tp = ulong.Parse(ts2);
if (tp.ToString().Length != sq.ToString().Length)
continue;
if (squares.Contains(tp))
max = Math.Max(sq,tp);
}
catch{}
}
}
return max;
}
public static bool IsSquare (ulong i)
{
double sqrt = Math.Sqrt((double)i);
return Math.Ceiling(sqrt) == Math.Floor(sqrt);
}
public static bool Anagrams (string s1, string s2)
{
if (s1.Length != s2.Length)
return false;
char[] c1 = s1.ToUpper().ToCharArray();
char[] c2 = s2.ToUpper().ToCharArray();
Array.Sort(c1);
Array.Sort(c2);
string ns1 = new string(c1);
string ns2 = new string(c2);
return (ns1==ns2);
}
}
}