Project Euler - Problem 98

• Problem 98
• Solution
• Console output

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.

First of all we need to find out all anagrams in the given file.For the few of you who may think what is an anagram.Anagram is a word, phrase, or name formed by rearranging the letters of another word.A Simple example of that are the words ITEM and TIME.Both of the words have same set of characters,but give different meanings when rearranged.The following piece of LINQ gets all anagrams in the file.

var anagrams_1=textContent.Split(',')
                          .Select(str => new CustomString(str));
var anagrams =  anagrams_1.GroupBy(cstr => cstr.sortedString)
                            .Where(g => g.Count() > 1)
                            .Select(g => g.Key);

textContent is a string datatype housing the entire textual content pulled off from word.txt file.The CustomString struct is created for every word in the file and it stores two different states.Sorted String state and the  Original string.A sorted string will have its letters sorted left to right in a alphabetical order.The unsorted string will maintain its original arrangement of letters.In the case of words TIME and ITEM ,the sorted and unsorted original state would look like below.

          CustomString for TIME : Sorted String : EIMT, Original String: TIME

          CustomString for ITEM : Sorted String : EIMT, Original String: ITEM

       

          If we compare the Sorted string(EIMT)of both the words we can conclude quickly that these

          two are anagrams.

struct CustomString {

 public char[] charArrayOrg;
 public char[] sortedCharArr;
 public string sortedString;
 public string originalString;

 public CustomString(String source) {

   charArrayOrg = source.ToCharArray();
   sortedCharArr = source.ToCharArray();
   Array.Sort(sortedCharArr);
   sortedString = new String(sortedCharArr);
   originalString = new String(charArrayOrg);

}}

The extension method Select() takes every string and transforms it to a CustomString object.Then all the objects are grouped by its SortedString state.Each group in the LINQ result set will correspond to a unique anagram from the word.txt file.

Next we need to generate all possible square numbers that match the length of every anagram word(Brute Force). And we need to positionally apply each of the digits to every character in the word starting from left to right.
Lets take the anagrams TIME and ITEM(both 4 letters) to get the explanation straight.Our squares should match the length of the anagrams,in this case we will consider 1225(4 digits) which is the square of 35.

                                    1  2  2   5

                                    T  I  M  E

In the next step we rearrange the letters to form its anagram ITEM.As we rearrange the numbers get shuffled as you can see below.

                                   2  1   5  2

                                   I   T  E  M 


ForEach loop for Rearranging the letters.

    
foreach (char ch in match.originalString)
{
    bool elePlaced = false;
    while (!elePlaced)
    {
        var idx = ele.originalString.IndexOf(ch, startSearchAt);
        if (shufflerList[idx] == '\0')
        {
            shufflerList.RemoveAt(idx);
            shufflerList.Insert(idx,    
                        sqrSeedString[match.originalString.IndexOf(ch)]);
            elePlaced = true;
        }
        else
            startSearchAt = idx + 1;
    }
    startSearchAt = 0;
}

Lastly we need to check whether the newly formed number is a square or not.2152 is not a square number.