Dr. Lawlor's Code, Robots, & Things

October 23, 2014

Monkeys, Typewriters, and Shakespeare

Filed under: Random Thoughts — Dr. Lawlor @ 6:39 pm

This Wednesday we did our first ACM student chapter coding challenge, verifying the infinite monkey theorem:

“A monkey pounding keys on a typewriter for an infinite time will eventually generate the complete works of Shakespeare.”

Clearly, we don’t have infinite time, but computers are faster than monkeys, and a virtual monkey doesn’t need bananas or people to clear the typewriter jams (and clean the cage).  Also, the crucial role of “monkey editor” needs to be automated.

Surprisingly, the default C++11 random number generator std::default_random_engine repeats every 4 billion keystrokes, which happens within only a few minutes.  std::mt19937 did not repeat during the duration of this test.

Shakespeare’s word length distribution is approximately:

0 19 101 588 1871 3295 4443 4963 4486 3486 2372 1584 860 476 219 92 39 15 9 7 0 1 0 1 0

That is, there are 0 words with 0 letters, 19 words with one letter (a, i, and other letters counting section titles and abbreviations), 101 two-letter words, etc.

The spacebar is bigger than the other keys, which is good because otherwise the median monkey-word has length 26.  By varying the size of the spacebar, we can set the average word length.

In typing 1.8 trillion keystrokes (on a quad-core machine over the course of a few days), billions of short words were generated, but the longest Shakespearean words generated were only 9 letters long:

calipolis
cockscomb
followers
heaviness
interlude
petitions
reguerdon
sweetened

This is all of them.  The full bard is 5 million characters long.  Monkeys, get crackin’!

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: