Twitter Bot Finds Anagrams of Twitter Statuses

Post by cmyr » Wed, Aug 13, 2014, 5:14 PM UTC

jcampbell1 wrote: post #19

joopxiv wrote: post #18

I find it interesting that they're manually approving the hits, because, as they indicate, most hits are (nearly) identical. It shouldn't be too difficult to solve this automatically though. Identical hits can be discarded very easily. The ones that only have a few words or letters reversed can be detected with some kind of similarity algorithm.

I had a look at the source code, and it does quite a bit of filtering, particularly around making sure the words are unique, and there is a primitive character comparison algorithm. The code could be simplified by using Python's set() and improved by doing a copy'n'paste on a Levenshtein function.

Post by madcaptenor » Thu, Aug 14, 2014, 1:39 PM UTC

Strilanc wrote: post #20

madcaptenor wrote: post #6

I'm a bit surprised that there are anagrams to be found. It's easy to find them if they exist, but there's no guarantee at all that there actually should be collisions.

Fermi estimate time! Anagrams are just sentences with the same letter counts. The anagrams they're posting have 25ish letters... how many ways are there to distribute 25 balls into 26 bins? (25+26)!/25!/26! is ~250 trillion. The birthday paradox square roots that down to ~10 million, and the fact that we prefer some bins (fewer Zs, more Es) probably cuts it down even further to ~1 million. So one anagram per million…