Skip to content

Instantly share code, notes, and snippets.

@gilbertw1
Created February 16, 2017 20:18
Show Gist options
  • Save gilbertw1/a417418d9d019ffd3aa9e121bbff7e1e to your computer and use it in GitHub Desktop.
Save gilbertw1/a417418d9d019ffd3aa9e121bbff7e1e to your computer and use it in GitHub Desktop.
Binary Word Game Cheater
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment