Last active
February 2, 2016 02:35
-
-
Save cmcenearney/6d0e7e628c12b1a9ed8e to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import scala.collection.mutable | |
| /** | |
| * Code to solve a type of puzzle known as a "spelling bee" or "word hive". | |
| * | |
| * M I | |
| * T U A | |
| * N O | |
| * | |
| * Make a list of eligible words, where eligible means | |
| * - only the letters in the hive are used | |
| * - the central letter is used at least once | |
| * - words are five letters long or more | |
| * | |
| * Score words 3 points if all seven letters are used, 1 point for all others. | |
| * | |
| * For example the above hive could yield `ammunition` for 3 points, and `munition` for 1 point. | |
| * | |
| * val hive = WordHive('u', Set('a','m','n','i','u','t','o')) | |
| * val hiveTrie = new HiveTrie | |
| * val solution = hiveTrie.solve(hive) | |
| * | |
| * Using the default list of words that ships with most *nix distros, solution.score() should be 116. | |
| * | |
| * Using the international Scrabble list, "sowpods", it will be 95. | |
| * | |
| */ | |
| case class WordHive(centralChar: Char, chars: Set[Char], minLength: Int = 5) { | |
| private def centralCharUsed(word: String): Boolean = word.toSet.contains(centralChar) | |
| private def lengthOk(word: String): Boolean = word.length >= minLength | |
| private def onlyHiveCharsUser(word: String): Boolean = word.toSet.subsetOf(chars) | |
| def qualifies(word: String): Boolean = centralCharUsed(word) && lengthOk(word) && onlyHiveCharsUser(word) | |
| def scoreWord(word: String): Int = if (word.toSet.equals(chars)) 3 else 1 | |
| } | |
| class Solution(wordHive: WordHive) { | |
| val words = mutable.Set[String]() | |
| def addWord(word: String): Unit = words.add(word) | |
| def score(): Int = words.foldLeft(0)((acc, word) => acc + wordHive.scoreWord(word)) | |
| } | |
| class HiveTrie(pathToDict: String = "/usr/share/dict/words") extends Trie[Char] { | |
| init() | |
| def init(): Unit = { | |
| val dict = scala.io.Source.fromFile(pathToDict) | |
| dict.getLines().filter(_.length > 0).foreach(add(_)) | |
| } | |
| def solve(hive: WordHive): Solution = { | |
| val states: mutable.Stack[SearchState] = mutable.Stack(SearchState(hive, "", root)) | |
| val s = new Solution(hive) | |
| while (states.nonEmpty) { | |
| val srch = states.pop() | |
| if (srch.node.isWord && hive.qualifies(srch.word)) s.addWord(srch.word) | |
| srch.node.children | |
| .filter(n => srch.wordHive.chars.contains(n._1)) | |
| .foreach(n => states.push(srch.copy(word = srch.word + n._1, node = n._2))) | |
| } | |
| s | |
| } | |
| private case class SearchState(wordHive: WordHive, word: String, node: Node[Char]) | |
| } | |
| class Trie[T] { | |
| class Node[T]() { | |
| var children: Map[T, Node[T]] = Map[T, Node[T]]() | |
| var isWord: Boolean = false | |
| } | |
| val root = new Node[T]() | |
| private def getNode(s: Seq[T], n: Node[T]): Option[Node[T]] = { | |
| if (s.isEmpty) Some(n) | |
| else n.children.get(s.head).flatMap(nn => getNode(s.tail, nn)) | |
| } | |
| def contains(s: Seq[T]): Boolean = getNode(s, root) match { | |
| case Some(node) => node.isWord | |
| case None => false | |
| } | |
| def containsPrefix(s: Seq[T]): Boolean = getNode(s, root) match { | |
| case Some(node) => true | |
| case None => false | |
| } | |
| def add(s: Seq[T]): Node[T] = { | |
| def go(s: Seq[T], n: Node[T]): Node[T] = { | |
| if (s.isEmpty) { | |
| n.isWord = true | |
| n | |
| } | |
| else n.children.get(s.head) match { | |
| case Some(node) => go(s.tail, node) | |
| case None => | |
| val newNode = new Node[T]() | |
| n.children = n.children.updated(s.head, newNode) | |
| go(s.tail, newNode) | |
| } | |
| } | |
| go(s, root) | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment