Anagram Finder

There is only so far you can go with Hello World, so my next task was to solve a problem a friend of mine was given in an interview. How would you write an anagram solver in scala.

Don't expect a nice pithy solution, this will be a journey trying out various constructs along the way. I will be writing tests for everything, but things may get messy. For a start - I am too lazy/eager to start a new project so I am just hacking it on to my hello world app. Once I have a working tool I will look at refactoring and creating some sort of restful api.

The rules:

I'm unsure what constraints the interview question set, but mine are as follows:

• Given a word and a list of valid words, find all potential anagrams of that word.
• Any potential anagram must consist of one or more valid words that are, obviously, not the same word.

The code.

I have added the source code to my github account, feel free to check it out. I will include code snippets inline, but if you want to know what goes where in the file system, please browse the various tags I have created an linked to github.

So, to get started - I created a class called AnagramFinder and wrote a spec for that class.

import org.specs2.Specification

class AnagramFinderSpec extends Specification { def is = s2"""
  I can get an instance of an AnagramFinder
    valid instance          $anagramFinder1
    should contain the word that we are looking for anagrams of $hasword
  I can check that a word is entirely contained within another word
    hell is contained in hello $hello_contains_hell
    help is not contained in hello  $hello_does_not_contains_help
  """
  def anagramFinder1 = new AnagramFinder("hello") must beAnInstanceOf[AnagramFinder]
  def hasword = new AnagramFinder("hello").word must be_==("hello")
  def hello_contains_hell = new AnagramFinder("hello").contains("hell") must be_==(true)
  def hello_does_not_contains_help = new AnagramFinder("hello").contains("help") must be_==(false)
}

The code required to pass these tests is here:

class AnagramFinder(myword: String ) {
  var word: String = myword
  def contains(str: String) = {
    word.contains(str)
  }
}

so far so good, but nowhere near complete, for instance this wont work when asked if hello contains "leo", which it clearly does.

So lets add a test

leo is contained in hello  $hello_contains_leo
...
def hello_contains_leo = new AnagramFinder("hello").contains("leo") must be_==(true)

see here for code

Now this doesn't pass

[info] AnagramFinderSpec
[info]   I can get an instance of an AnagramFinder
[info]     + valid instance
[info]     + should contain the word that we are looking for anagrams of
[info] 
[info]   I can check that a word is entirely contained within another word
[info]     + hell is contained in hello
[info]     + help is not contained in hello
[error]     x leo is contained in hello
[error]  the value is not equal to 'true' (AnagramFinderSpec.scala:17)

So I tried a couple of ways of doing this, and to cut a long story short, word.toList.contains(str.toList) didn't work; and word.toCharArray.contains(str.toCharArray) didn't either

but thanks to StackOverflow I found this sugestion that did.

class AnagramFinder(myword: String ) {
  var word: String = myword

  def contains(str: String) = {
    str.toSet.subsetOf(word.toSet)
  }
}

running my tests again:

[info] AnagramFinderSpec
[info]   I can get an instance of an AnagramFinder
[info]     + valid instance
[info]     + should contain the word that we are looking for anagrams of
[info] 
[info]   I can check that a word is entirely contained within another word
[info]     + hell is contained in hello
[info]     + help is not contained in hello
[info]     + leo is contained in hello
[info] 
[info] Total for specification AnagramFinderSpec
[info] Finished in 39 ms
[info] 5 examples, 0 failure, 0 error

This is the point where I start to see the elegance of scala as a language