Skip to content

Instantly share code, notes, and snippets.

@vladmiller
Last active December 30, 2015 07:39
Show Gist options
  • Save vladmiller/7797387 to your computer and use it in GitHub Desktop.
Save vladmiller/7797387 to your computer and use it in GitHub Desktop.
Find anagrams for words using dictionary
import scala.collection.JavaConversions._
object Solution {
/**
* Read dictionary
*/
val dictionary = scala.io.Source.fromFile("/tmp/wl.txt").mkString.split("\n");
def annagramm(word: List[String], dictionary: Array[String]): List[String] = {
/**
* Take all same size words
*/
val mappedDictionary = dictionary.toList.filter { e =>
e.length == word.length && word.exists( c => c == e(0).toString )
} map { e =>
(e toString) :: word
}
def removeIndex(list: List[String], ix: Int) = if (list.size < ix) list
else list.take(ix) ++ list.drop(ix+1);
def isAnnagramm(word: List[String], n: Int = 0): Boolean = {
word match {
case word :: Nil => true
case word :: tail => {
val indexOf = tail.indexOf(word(n).toString);
if (indexOf >= 0) {
isAnnagramm( word :: removeIndex(tail, indexOf), n + 1 )
} else false
}
case Nil => false
}
}
/**
* Reduce dictionary
*/
mappedDictionary filter { e =>
isAnnagramm(e)
} map { e =>
e(0)
}
}
println( annagramm("horse".toList.map { e => e.toString }, dictionary) )
// > List(heros, horse, shore)
println( annagramm("abundance".toList.map { e => e.toString }, dictionary) )
// > List(abundance)
println( annagramm("acadia".toList.map { e => e.toString }, dictionary) )
// > List(acadia)
println( annagramm("asdfkalskdjflaksjdf".toList.map { e => e.toString }, dictionary) ) // If there is no options, then return empty list
// > List()
println( annagramm("shore".toList.map { e => e.toString }, dictionary) )
// > List(heros, horse, shore)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment