Guess my word - Hackdot

Re:Guess my word by bonobo3000 on Saturday September 05, 2015 @08:02AM (#10174591)

This is great! Inspired me to make a little script in spark-shell:

    > val words = oxforddict.
                filter{case s => s.exists(_.isLetter) && s.forall(Character.isUpperCase(_))}.
                distinct.
                map((_.toLowerCase,1))

    > def lcp(a:String,b:String) = { a.zip(b).takeWhile(Function.tupled(_ == _)).map(_._1).mkString }
    > implicit val wordOrdering = new Ordering[String] {
    >   override def compare(a:String, b:String) = { val lcpIdx = lcp(a,b).length; a.substring(lcpIdx).compareTo(b.substring(lcpIdx)) }
    > } 
    
    > def nextGuess(lower:String,upper:String,g:Int) = { val candidates = words.filterByRange(lower,upper).map(_._1).collect.sorted(wordOrdering).toList; val mid = candidates.length / 2; candidates.slice(mid-g/2,mid+g/2+1) }
    nextGuess: (lower: String, upper: String, g: Int)

    > nextGuess("prejudice","promise",1)
    res42: List[String] = List(primeness)
    > nextGuess("prime","promise",10)
    res47: List[String] = List(procris, procrustean, procrusteanize, procrustes, procrustesian, proctitis, proctocele, proctodaeum, proctor, proctorage, proctorial)
    > nextGuess("proctor","promise",10)
    res48: List[String] = List(profulgent, profundity, profuse, profusely, profuseness, profusion, profusive, prog, progenerate, progeneration, progenitor)
    > nextGuess("profuse","promise",12)
    ding ding!!

I love HN, and I love scala :D Thanks for posting OP. HN needs more great technical content like this and less opinion & news, in my opinion.

[ Parent | on HN ]

Re:Guess my word by normac on Saturday September 05, 2015 @09:11PM (#10176535)

This raises an interesting problem--could we find the word even faster by using something other than a standard binary search?

The first thing that comes to mind is skipping past letters that don't appear very often at that point in a word with the current prefix--or to be more granular, you could change your counter (here g) to a float and somehow weight each letter by how rarely it occurs after the letters you've established so far. So if you've currently established that the first four letters are "pro," and "z" almost never occurs after those letters, "z" might be given a weight above 1 so the counter skips right past it.

[ Parent | on HN ]