7 ms·
Use Letterpest to win at Letterpress
- boundsj 14y agogithub: https://github.com/boundsj/letterpest https://github.com/boundsj/letterpest
- alexmchale 14y agoI 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.
- labo 14y agoI find you oddly humorous and I'm not saying that's a bad thing. Letterpest is aw3som3!
- kmfrk 14y agoIsn't a trie structure the data structure you'd always go for with a dictionary-based project? EDIT: Title just changed and doesn't mention it (as a feature) anymore.
- zwily 14y agoI think I'd have used a bloom filter for something like Letterpress.
- kmfrk 14y agoInteresting, 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?
- buss 14y agoI'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. What do you gain from the bloom filter?
- buss 14y agoOn 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.
- baddox 14y agoI suspect zwily was talking about the word verification for the Letterpress app itself, not the cheating app.
- zwily 14y agoRight - 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.
- MrScruff 14y agoI don't really understand this - has someone really gone to all this trouble to help people cheat at a free word game?
- labo 14y agoIt's actually a pretty cool experiment... is it not?
- gojomo 14y agoIt'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.)
- boundsj 14y agore "solved game" http://www.wired.com/gamelife/2012/11/letterpress-solved-games/ http://www.wired.com/gamelife/2012/11/letterpress-solved-gam...
- MrScruff 14y agoI 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.
- gojomo 14y agoThere 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.
- jzting 14y agoNice work! Small bug: "Q" is getting recognized as "O" on a few boards I've tested.
- boundsj 14y agothanks! will work on that
- pwthornton 14y agoThis 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.
- baddox 14y agoA 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.
- pwthornton 14y agoWould 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.
- baddox 14y agoI'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.
- gojomo 14y agoThat 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.