anagrams.scala

object scratch {

	type SentenceAnagram = Set[String]
	type SolutionSpace = Set[SentenceAnagram]
	type CharacterCounts = Map[Char, Int]
  def frequencyCount(word: String): CharacterCounts = {
  	val grouped: Map[Char, String] = word.toLowerCase.replaceAll("[^a-z]", "").groupBy(c => c)
  	grouped.map((pair: Tuple2[Char, String]) => (pair._1, pair._2.length))
  }

  val start = "West London Hack Night"
  val testCount = frequencyCount(start)

  val dictionary = scala.io.Source.fromFile("/usr/share/dict/words")
    .getLines.map(x => x.toLowerCase)
    .toSet.toList
    
    val foo = dictionary.filter(x => frequencyCount(x).forall(p => testCount.getOrElse(p._1, 0) >= p._2))
      .sortBy(_.length).reverse
  
  
  
  
  def findAnagram(unmatched: CharacterCounts, matched: SentenceAnagram, dict: List[String]): SolutionSpace = {
  	dict match {
  		case Nil => Set()
  		case h :: t => {
  			val testing = frequencyCount(h)
    		if (testing == unmatched) {
    			Set(matched + h) ++ findAnagram(unmatched, matched, t)
    		} else {
	 				val isSubset: Boolean = testing.forall(p => unmatched.getOrElse(p._1, 0) >= p._2)
   				if (isSubset) {
   					val newUnmatched: CharacterCounts = unmatched.map(m => (m._1, m._2 - testing.getOrElse(m._1, 0)))
    				findAnagram(newUnmatched, matched + h, t) ++ findAnagram(unmatched, matched, t)
    			} else {
    				findAnagram(unmatched, matched, dict.tail)
    			}
    		}
 
    	}
  	}
	}
	
  foo.length
  
  
  findAnagram(testCount, Set(), foo)
}