The Anagram Puzzle in Scala

A few weeks ago, we had a coding dojo in Adaptworks. There, we decided to use Scala as the coding language, and the problem to be solved was the Anagram puzzle. Unfortunately we didn’t manage to solve the problem during the coding session, but I’m sure everyone learned a bit more about Scala, which is always the main goal =)

Now, of course I wanted to have this puzzle solved. So I finally used some spare time and coded a solution. My solution is not the best possible one by any means, but it works and was really fun to work on.

Before showing the solution, a brief explanation of the problem, translated from the description in portuguese:

Write a program that generates all possible anagrams of a given string.

For instance, the possible anagrams of "biro" are:

biro bior brio broi boir bori
ibro ibor irbo irob iobr iorb
rbio rboi ribo riob roib robi
obir obri oibr oirb orbi orib

I’m still trying to find better and more readable solutions, but for now the current one is as follows:

class Anagram {
  def anagrams(word: String): Set[String] = anagram(word).toSet

  def anagram(word: String): List[String] = {
    if (word.length == 1) {
      List(word)

    } else {
      var anagrams = ListBuffer[String]()
      0 to word.length-1 foreach { i =>
        anagrams ++= (anagram(without(i, word)) map (word.charAt(i) + _))
      }

      anagrams.toList
    }
  }

  def without(index: Int, word: String): String = new StringBuilder(word).deleteCharAt(index).toString
}

In summary, what I tried to do was combining the ‘current’ char with all combinations of the rest of the input string. I hope this makes sense while reading the code. The code works – I have some unit tests that we generated during the coding dojo plus a couple more tests I added afterwards. Yet, I’m not happy with the anagram ListBuffer… I guess this could be solved in a more elegant way. Ideas?

An extra curiosity. While looking into the Scala Docs API to find possible ways to solve the puzzle, I discovered a very handy function that can be called on strings (and other kinds of collections as well): permutations. It basically solves this puzzle in a single method call…

Advertisements
This entry was posted in scala and tagged , , , , , , , . Bookmark the permalink.

4 Responses to The Anagram Puzzle in Scala

  1. Lucas Torri says:

    Maybe something like this:

    implicit def list2listPlus[T](l: List[T]) = new {
    def removeFirst[T](e: T) = {
    val (before, afterWith) = l.splitAt(l.indexOf(e))
    before ::: afterWith.tail
    }
    }

    object Anagram {
    def apply(s: String): List[String] = this(s.toList)
    def apply(chars: List[Char]): List[String] = chars.size match {
    case 1 => List(chars.head.toString)
    case _ => chars.flatMap( c => this(chars.removeFirst(c)).map(_ + c) ).distinct
    }
    }

    Anagram(“biro”)
    //List(orib, roib, oirb, iorb, riob, irob, orbi, robi, obri, bori, rboi, broi, oibr, iobr, obir, boir, ibor, bior, ribo, irbo, rbio, brio, ibro, biro)

  2. Vinicius says:

    Never code more than you should:

    “biro”,permutations foreach println

    Permutations does that job for you ūüôā

  3. Pingback: O Anagram Puzzle em Scala | iMasters

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