5 ms·

This is great! Inspired me to make a little script in spark-shell: > val words = oxforddict. filter{case s => s.exists(_.isLetter) && s.for

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.

normac 11y ago
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.

normac 11y ago

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.