I find it oddly humorous that the instructions tell you that you must use the Light theme, then the illustration of taking a screenshot shows a dark theme.
Interesting, never knew too much about Bloom filters. Let me flip the question, then: is there any reason you wouldn't use a Bloom filter over tries for a dictionary?
I'm not seeing how a bloom filter would help you here. The only application of a bloom filter that I can see is checking whether or not the word candidate you generated is in a dictionary. All n-choose-k sets is enormous and you'd spend a very long time just generating the candidates.
A prefix trie, as the GP mentioned, seems like a very good and obvious approach. You avoid most of the work generating non-words because all paths lead to complete words unless you run out of letters and you're not on a terminal.
On further thought, you could use a bloom filter to test if a given set of letters has any valid words, then look up that set in a normal hash table (or use an associate bloom filter).
I haven't done any calculations or experiments, but it doesn't seem like you'd save much computation time with the bloom filter vs just using a hash table that maps (letter sets) -> (words). I could see this being faster than a trie, though, since you aren't trying to do spelling suggestions and you lose a lot of time traversing the trie for all possible permutations of the letters.
Right - just for verification in Letterpress. The occasional false positive wouldn't be so bad, and you can tune your bloom filter so that it's really rare.
It's the interesting problem -- letter recognition, dictionary search, constrained ranking -- that likely motivates the author(s). The practical use in helping cheaters is just a bonus for bringing added attention to the engineering achievement.
Still, the Letterpress board is so fixed in its layout/fonts that I'm surprised they need a 'neural network' recognizer, and prefer a certain color scheme.
Advanced assignment: calculate whether any given board is a 'solved' game, with a predictable outcome given two 'perfect' players. (My guess is that all boards are, given the advantage of moving first in biasing the score balance in your direction.)
I understand why some might be motivated to solve it as a problem, but it doesn't seem a particular impressive technical achievement to me. It's just like how everyone and his dog was writing soduku solvers a few years back.
Except in this case it's basically contributing to ruining a game, or at least the 'play with strangers' component. I would have thought a blog post outlining the approach taken to solve the problem would have sufficed.
There were already cheap apps in the App Store for Letterpress cheating, so showing off open-source code (or a web service) doesn't change a cheater's prospects much. On the other hand it does serve as practice/illustration of the techniques involved.
This is why LetterPress needs a Lighting Press mode, where games have to be completed in five minutes, for instance. The ability to outright cheat, or troll around dictionaries and the Internet for words is not possible if you need to complete a move in 20 seconds.
A timer alone wouldn't help much. One could still take a screenshot of the game board during the first turn, upload it here, then have a list of good words to use for the rest of the game.
Would there be a way for these lightning rounds to disqualify someone if they put the app into a background process? You would have to be locked into the app in the foreground for the entire match.
I've never done iPhone development, but activities in Android have an onPause method that can be overridden and gets called whenever the activity gets temporarily hidden. There would probably be problems with getting disqualified for getting a phone call, etc. but I'm certain that something can be done in iPhone.
That might help, or other techniques used by some apps ('SnapChat'?) that purport to prevent the taking of screengrabs. But, it's also not that hard to type in 25 letters manually, to a nearby computer. Cheaters gonna cheat... you ultimately have to play with people you trust, or choose to trust.
26 comments
[ 3.0 ms ] story [ 48.6 ms ] threadEDIT: Title just changed and doesn't mention it (as a feature) anymore.
A prefix trie, as the GP mentioned, seems like a very good and obvious approach. You avoid most of the work generating non-words because all paths lead to complete words unless you run out of letters and you're not on a terminal.
What do you gain from the bloom filter?
I haven't done any calculations or experiments, but it doesn't seem like you'd save much computation time with the bloom filter vs just using a hash table that maps (letter sets) -> (words). I could see this being faster than a trie, though, since you aren't trying to do spelling suggestions and you lose a lot of time traversing the trie for all possible permutations of the letters.
Still, the Letterpress board is so fixed in its layout/fonts that I'm surprised they need a 'neural network' recognizer, and prefer a certain color scheme.
Advanced assignment: calculate whether any given board is a 'solved' game, with a predictable outcome given two 'perfect' players. (My guess is that all boards are, given the advantage of moving first in biasing the score balance in your direction.)
Except in this case it's basically contributing to ruining a game, or at least the 'play with strangers' component. I would have thought a blog post outlining the approach taken to solve the problem would have sufficed.
Small bug: "Q" is getting recognized as "O" on a few boards I've tested.