Binary Word Game Cheater

BinaryWordGameCheater.scala

import scala.io.Source
import scala.util.Sorting
import scala.collection.mutable.ListBuffer
import scala.math._
import Stream._
 
object PrimeChompWordGameDictionary {
 
    private val dictionary = createDictionary()
 
    def getDictionary(): PrimeChompWordGameDictionary = {
        return dictionary
    }
 
    private def createDictionary(): PrimeChompWordGameDictionary = {
        val lines = Source.fromFile("wordList.txt").getLines
        return new PrimeChompWordGameDictionary(lines)
    }
}
 
class PrimeChompWordGameDictionary(words: Iterator[String]) {
    private val directedWordGraph: DirectedWordGraph = {
        val wordGraph = new DirectedWordGraph
        words foreach { word =>
            wordGraph.addWord(word)
        }
        wordGraph.annotateOccurrences()
        wordGraph
    }
     
    def sumBranches(): List[(Char,Int)] = {
        directedWordGraph.sumBranches
    }
 
    def lookupMatches(query: String): List[String] = {
        val mask = BooleanMaskCreator.createQueryMask(query)
        val queryArray = QueryArrayCreator.createQueryArray(query)
        val resultListBuffer = new ListBuffer[String]
        directedWordGraph.lookupMatchingWords(mask, queryArray, resultListBuffer)
        return resultListBuffer.toList
    }
}
 
 
class DirectedWordGraph() {
     
    val graph = new Node('@')
 
    def sumBranches(): List[(Char,Int)] = {
        var sumList = List[(Char,Int)]()
        graph.children foreach { child =>
            sumList ::= (child.myLetter, child.sumTree)
        }
        return sumList
    }
 
    def addWord(word: String): Unit = {
        val wordPackage = new WordPackage(word,sortWord(word))
        graph.addWord(wordPackage)
    }
 
    def annotateOccurrences(): Unit = {
        val letterMap = new LetterMap
        graph.annotate(letterMap)
    }
 
    def lookupMatchingWords(mask: Long, queryArray: Array[Int], listBuffer: ListBuffer[String]) = {
        graph.lookupInChildren(mask, queryArray, listBuffer)
    }
 
    def sortWord(word: String): String = {
        val wordArr = word.toCharArray
        Sorting.quickSort(wordArr)
        return (new String(wordArr))
    }
 
    class Node(val myLetter: Char) {        
        var occurrence: Int = 0
        var children: List[Node] = List[Node]()
        var myWords: List[String] = List[String]()
        val myMask = BooleanMaskCreator.getLetterMask(myLetter)
        val myLetterValue = ArrayLetterNumberMap.getNumber(myLetter)
 
        def sumTree(): Int = {
            var sum = myWords.length
            children foreach { child =>
                val tsum = child.sumTree
                if(myLetter == 'a') {
                     
                }
                sum = sum + tsum
            }
            return sum
        }
 
        def addWord(wordPackage: WordPackage): Unit = {
            if(wordPackage.letters.length > 0) {
                addWordToChild(wordPackage) 
            } else {
                myWords ::= wordPackage.word
            }
        }
 
        private def addWordToChild(wordPackage: WordPackage): Unit = {
            val letter = wordPackage.letters.charAt(0)
            wordPackage.letters = wordPackage.letters.drop(1)
            val childOption = getChild(letter)
            childOption match {
                case None => 
                    val child = new Node(letter)
                    child.addWord(wordPackage)
                    children ::= child
                case Some(child) =>
                    child.addWord(wordPackage)
            }
        }
 
        private def getChild(letter: Char): Option[Node] = {
            children find { child =>
                child.myLetter == letter
            }
        }
 
        def annotate(letterMap: LetterMap): Unit = {
            if(myLetter != '@') {
                occurrence = letterMap.getLetter(myLetter)+1
            }
            val newMap = letterMap.addLetter(myLetter)
            children foreach { child =>
                child.annotate(newMap)
            }
        }
 
        def lookupMatchingWords(mask: Long, queryArray: Array[Int], listBuffer: ListBuffer[String]): ListBuffer[String] = {
            if((mask & myMask) == myMask) {
                listBuffer.++=:(myWords)
                lookupInChildren(updateMask(mask, queryArray), queryArray, listBuffer)
            }
            return listBuffer
        }
 
        def lookupInChildren(mask: Long, queryArray: Array[Int], listBuffer: ListBuffer[String]) = {
            children foreach { child => 
                child.lookupMatchingWords(mask, queryArray, listBuffer)
            } 
        }
 
        private def updateMask(mask: Long, queryArray: Array[Int]): Long = {
            if(queryArray(myLetterValue) <= occurrence) {
                return mask - myMask
            } else {
                return mask
            }
        }
    }
 
    class WordPackage(val word: String, var letters: String) {}
}
 
class LetterMap(map: Map[Char,Int] = ('a' to 'z').map((_,0)).toMap) {
 
    def addLetter(letter: Char): LetterMap = {
        if(letter != '@') {
            new LetterMap(map + ((letter, map(letter)+1)))
        } else {
            this
        }
    }
 
    def getLetter(letter: Char): Int = {
        map(letter)
    }
}
 
object ArrayLetterNumberMap {
    val map = ('a' to 'z').zip(0 to 25).toMap
 
    def getNumber(letter: Char): Int = {
        if(letter != '@') {
            map(letter)
        } else {
            -1
        }
    }
}
 
object QueryArrayCreator {
    def createQueryArray(word: String): Array[Int] = {
        var arr = new Array[Int](26)
        word foreach { letter =>
            val lvalue = ArrayLetterNumberMap.getNumber(letter)
            arr(lvalue) = arr(lvalue)+1
        }
        return arr
    }
}
 
object BooleanMaskCreator {
    private val letterValueMap = ('a' to 'z').zip(1 to 26).map(t => (t._1, Math.pow(2,t._2).toLong)).toMap
 
    def getLetterMask(letter: Char): Long = {
        if(letter != '@') {
            letterValueMap(letter)
        } else {
            -1
        }
    }
 
    def createQueryMask(word: String): Long = {
        val letters = word.toList.distinct
        var sum: Long = 0
        letters foreach { letter =>
            sum += getLetterMask(letter)
        }
        return sum
    }
}
 
val dictionary = PrimeChompWordGameDictionary.getDictionary
 
val runtimes = 10000
var query = "djopeitmvmxzmajfpqoeutyghb"
val start = System.currentTimeMillis
val matches = dictionary.lookupMatches(query)
var count = 0
while(count < runtimes) {
    //query = (scala.util.Random.alphanumeric.take(30).force.toList.mkString.replaceAll("[^a-zA-Z]","").toLowerCase)
    dictionary.lookupMatches(query)
    count += 1
}
val end = System.currentTimeMillis
 
println("matches = " + matches.length)
println("query length = " + query.length)
println("times run = " + runtimes)
println("time = " + (end-start))
println("avg = " +  (end-start) / runtimes)