Search code examples
haskellanagram

Square anagram word pairs of project Euler

I'm trying to solve the "square anagram word pair" problem of project Euler (here) in Haskell, but I'm stucked...

The problem is the following (I shortened it):

  • take one word, say "CARE" and one of its anagram, for example "RACE".
  • replace each letter of "CARE" by a unique digit, for example C = 1, A = 2, R = 9 and E = 6. It happens to be 1296 and is a square number.
  • replace the anagram's letters ("RACE") following the same substitution policy, it generates 9216 which also is a square number !

Given a list of words, what's the largest square number formed by any member of such a pair?

I managed to extract all the anagrams pairs from the file and I have them in a [(String,String)] form i.e [("CARE","RACE")..].

In the next step (map anasquare), and for each pair of words, I want to link the biggest square number that can be generated so it'd look like[(9216,"CARE","RACE")..].

Well, there is a trick (there must be !) to avoid the brute force approach but so far I didn't find it... Actually the problem isn't here, let's say I want to take the brute force approach and check every letter -> digit transformations. I just don't know how to do it in Haskell. Maybe I'm tired but I'm just dumbstruck in front of this. There must be a short an elegant yet not too obscure way to write it, someone has an idea ?

Here's what I do, I spare you the anagram searching and the file parsing functions:

-- Read the file -> store the content into a list -> work on that list -> print the output
result98 = do contents <- readFile ".\\resources\\98.txt"
              putStrLn $ (process.words.format) contents

-- Find anagram pairs -> Find corresponding square number -> get the biggest one
process::[String]->String
process = toString . maximum . map anasquare . anagrams
    where toString (a,b,c) = "Yay ! the result is " ++ show a

-- Generate the maximum square number possible, 0 when none exist
anasquare::(String,String)->(Integer,String,String)
anasquare (x,y) = (anasquareValue,x,y)
    where anasquareValue = 0 -- TODO
Solution

  • Though the mathematical insight is useful (especially on project euler), it didn't help me much on that one since I was missing some knowledge on the 'how to' part.

    Without going too much into the details, one solution path would consist in transforming an anagram word ("CARE","RACE") into a pair such as (1234,4213). Straightforward stuff. If a similar pattern is detected in the square number pairs, then there's a match.