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…
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)
Interesting and quite small solution =)
Never code more than you should:
“biro”,permutations foreach println
Permutations does that job for you 🙂
Pingback: O Anagram Puzzle em Scala | iMasters