Project Euler Problem #98

April 10, 2010

Read the details of the problem here

Summary

Investigating words, and their anagrams, which can represent square numbers.

Solution

When I first read this question I had visions of having to create mappings of characters to a full set of digit permutations from 0-9. As it happens though it wasn’t necessary to do this and instead just map potential solutions onto the given strings which greatly reduced the search space.

The solution begins by constructing a map of lists of squares of appropriate lengths. Then there’s a boilerplate method of reading the file and breaking the words up into a list, before grouping words and finding all the entries with anagrams.

For each of those entries, the list of words is then run through, with the intent of comparing each word with each other in the list. (There is only one word that has three anagrams, so usually this just checks two words against each other.) For each number in the appropriate list of matching squares, it will try to get a mapping of characters to digits for the first word, calculate the value of the second word (after ruling out palindromes) using that mapping and then check to see if that value is a valid square. (It’s not necessary to do an explicit check for leading zeroes as, if the solution included one, the value wouldn’t be found on the specific list of squares.) If a valid square number is found then the maximum value is tracked as the answer.

def ( nums, answer ) = [ [:], 0 ]

(2..10).each {
  def min = Math.ceil(Math.sqrt(10 ** (it-1)))
  def max = Math.floor(Math.sqrt((10 ** it)-1))
  nums[it] = (min..max).collect { (it * it).toInteger() }
}

new File("euler_p98_words.txt").text.replace("\"","").tokenize(",")
    .groupBy { it.toList().sort().join() }
    .findAll { it.value.size() > 1 }
    .each { key, words ->
       for (i in 0..<words.size()-1) {
         def len = words[i].size()
         for (n1 in nums[len]) {
           def map = getMapping(words[i], n1.toString())
           if (map.size() == 0) continue
           for (j in i+1..<words.size()) {
             if (words[i].reverse() == words[j]) continue
             def n2 = words[j].collect { map[it] }.join().toInteger()
             if (n2 in nums[len]) answer = [ n1, n2, answer ].max()
           }
         }
       }
     }

The getMapping() function (shown below) takes two string arguments; a word to be mapped, along with the number (which will be a valid square solution) that it’s to be mapped to. It returns the appropriate mapping, or an empty map if the mapping was not possible due to trying to map a character to multiple digits, or if a digit is mapped against multiple characters.

def getMapping(word, number) {
  def map = [:]
  for (i in 0..<word.size()) {
    def ( c, digit ) = [ word[i], number[i] ]
    if (!((map[c] == null) || (map[c] == digit))) return [:]
    map[c] = digit
  }
  if (map.groupBy { it.value }.any { it.value.size() > 1 }) map = [:]
  return map
}

This runs in 1.82 seconds. It would faster in native Java (of course!) but would require considerable more code.

Conclusion

Groovy’s features were used a lot here in: specifically in reading and filtering the original list of words and again in decoding the subsequent anagrams against the map. I’d say that Groovy is a winner on this one but I don’t know how performant it would be on much larger volumes of data.

Advertisements

2 Responses to “Project Euler Problem #98”

  1. dave dobbs Says:

    Hi KeyZero,

    I was intrigued by your use of Groovy, a language I hadn’t even heard of, so I installed it on my Ubuntu 10.04 system
    and ran your script in the console. I was surprised to see that the only output was a dictionary of valid word permutations, not the associated numbers and certainly not what the problem asked for, the maximum square number. Since the script seemed to run just fine I have to ask: did you leave out a key ingredient? 😉

    Incidentally, my Python script to form the equivalent map (dictionary) runs in 0.03 seconds, but I don’t know if you would be interested in seeing that. Probably pretty crude code, but it does the job quickly.

    Anyway, if I’m doing something inane that prevented your script from doing its intended job I would much appreciate being set strait – groovy looks rather, well, groovy ;-)…Dave

    • keyzero Says:

      Assuming you’ve got the datafile, you’ll need to print out the value of “answer” at the end of the script. Groovy listops are just syntactic sugar over the usual Java collections classes and can behave quite poorly so I’m not surprised that Python is faster – that and my code might not be the most efficient in the world either! Take a look at pe098.groovy on my github repository for something you should be able to run more easily – it pulls the data file directly from PE at runtime too.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: