Ano passado, nós tivemos um coding dojo em AdaptWorks. Lá, decidimos usar Scala como a linguagem de codificação, e o problema a ser resolvido foi o Anagram Puzzle. Infelizmente, não conseguimos resolver o problema durante a sessão de codificação, mas eu tenho certeza de que todos aprenderam um pouco mais sobre Scala, o que é sempre o objetivo principal =)
Agora, é claro que eu queria ter resolvido esse enigma. Então, finalmente usei algum tempo livre e codei uma solução. Ela não é a melhor possível, mas funciona e foi muito divertido trabalhar nela.
Antes de mostrar a solução, segue uma breve explicação sobre o problema, traduzida a partir da descrição em português:
Escreva um programa que gere todos os anagramas possíveis de uma determinada string.
Por exemplo, os possíveis anagramas de “biro” são os seguintes:
biro brio biou broi boir bori
ibro Ibor irbo irob iobr iorb
rbio rboi ribo riob roib robi
obir obri oibr oirb orbi orib
Eu ainda estou tentando encontrar soluções melhores e mais legíveis, mas por enquanto a atual é a seguinte:
01 class Anagram { 02 def anagrams(word: String): Set[String] = anagram(word).toSet 03 04 def anagram(word: String): List[String] = { 05 if (word.length == 1) { 06 List(word) 07 08 } else { 09 var anagrams = ListBuffer[String]() 10 0 to word.length-1 foreach { i => 11 anagrams ++= (anagram(without(i, word)) map (word.charAt(i) + _)) 12 } 13 14 anagrams.toList 15 } 16 } 17 18 def without(index: Int, word: String): String = new StringBuilder(word).deleteCharAt(index).toString 19 }
Em resumo, o que eu tentei fazer foi combinar o char ‘atual’ com todas as combinações do resto da string de entrada. Espero que isso faça sentido durante a leitura do código. O código funciona – tenho alguns unit tests que geramos durante o coding dojo mais alguns testes que eu adicionei depois. No entanto, eu não estou feliz com o anagrama ListBuffer … Eu acho que isso poderia ser resolvido de uma forma mais elegante. Ideias?
Uma curiosidade extra. Ao olhar para a API do Scala Docs para encontrar formas possíveis de resolver o quebra-cabeça, eu descobri uma função muito útil que pode ser chamada nas strings (e outros tipos de coleções também): permutações. Ela resolve basicamente este quebra-cabeça em um único método de chamada…
***
Texto original disponível em http://jcranky.com/2011/08/02/the-anagram-puzzle-in-scala/