Back-End

5 nov, 2012

O Anagram Puzzle em Scala

100 visualizações
Publicidade

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/