Hamlet’s Monkey
We’ve all heard the jokes before that a monkey could do that job, or a monkey could type better than you. You may have even heard of the Infinite Monkey Theorem, well its something that made me laugh and an interesting programmatic problem:
http://en.wikipedia.org/wiki/Infinite_monkey_theorem
Given infinite time, could a monkey actually type out the works of William Shakespeare? Well I decided the complete works was a bit hard on our poor monkey. Lets start with just Hamlet!
A friend at work and I got to talking, how would we approach this programmatically? How would the monkey actually get on?
So it occurred to me there are two way of approaching this, the easy way and the hard way.
A few notes
- My random character generator just generates A-Z
- Case is just not fair, so I’ve made all strings lowercase
- I’ve removed all punctuation
Green Light
I called it this because as soon as the monkey guesses a letter correctly, he gets a green light and moves onto the next letter. The correct letter is “banked” and he never has to start over. The hard bit here was really only how to progress, should we be removing the last letter added or just moving on?
Pastebin
<!--- Static Variables --->
<cfset variables.lstAlphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ">
<cfset variables.intNumLoops = 100>
<cfset variables.Shakespeare = "All your base are belong to me">
<cffunction name="generateRandomLetter" access="public" returntype="string" output="false">
<cfset var strLowerCaseAlpha = "abcdefghijklmnopqrstuvwxyz">
<cfreturn Mid(strLowerCaseAlpha,RandRange( 1, Len( strLowerCaseAlpha ) ),1)>
</cffunction>
<cfscript>
variables.intCount = 0;
variables.bProgress = true;
variables.strSubString = "";
variables.strShakespeare = lcase(variables.Shakespeare.replaceAll("[^a-zA-Z]", "")); //Shakespeare without spaces etc
variables.stuJson = {};
variables.strMonkeyString = "";
while (variables.intCount < variables.intNumLoops) {
variables.intCount++;
if(variables.bProgress EQ true){
//we're adding a new letter
variables.strMonkeyString = variables.strMonkeyString & generateRandomLetter();
}else if(len(variables.strMonkeyString) EQ 1){
//monkey string is just 1 char, just re-guess
variables.strMonkeyString = generateRandomLetter();
}else{
//we're re-guessing the last letter, so we need to remove it, then add a new one.
variables.strMonkeyString = left(variables.strMonkeyString,len(variables.strMonkeyString)-1) & generateRandomLetter();
}
//what we're expecting so far
variables.strSubString = left(variables.strShakespeare,len(variables.strMonkeyString));
//Did monkey do it?
if(variables.strMonkeyString EQ variables.strSubString){
if(variables.strMonkeyString EQ variables.strShakespeare){
//100%
customOutput("**WINNER**: " & variables.strMonkeyString);
break;
}else{
//Good so far, progress to next letter
variables.bProgress = true;
}
}else{
variables.bProgress = false;
}
}
writeoutput(variables.intCount);
writeoutput("<br />");
writeoutput(left(variables.strMonkeyString,len(variables.strMonkeyString)-1));
</cfscript>
Red Light
This is the hard way, the monkey has to get every letter of Hamlet correct and sequentially. If he makes a mistake, he starts from the beginning. I think this is the way the theorem is intended, but it probably won’t result in much success for the poor monkey! The code is actually pretty simple.
Pastebin
<!--- Static Variables --->
<cfset variables.lstAlphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ">
<cfset variables.intNumLoops = 500>
<cfset variables.Shakespeare = "All your base are belong to me">
<cffunction name="generateRandomLetter" access="public" returntype="string" output="false">
<cfset var strLowerCaseAlpha = "abcdefghijklmnopqrstuvwxyz">
<cfreturn Mid(strLowerCaseAlpha,RandRange( 1, Len( strLowerCaseAlpha ) ),1)>
</cffunction>
<cfscript>
variables.intCount = 0;
variables.strSubString = "";
variables.strShakespeare = lcase(variables.Shakespeare.replaceAll("[^a-zA-Z]", "")); //Shakespeare without spaces etc
variables.strMonkeyString = "";
variables.strBestSoFar = "";
while (variables.intCount LT variables.intNumLoops) {
variables.intCount++;
//generate the random guess, one keystroke at a time
variables.strMonkeyString = variables.strMonkeyString & generateRandomLetter();
variables.strSubString = left(variables.strShakespeare,len(variables.strMonkeyString));
//check if we have a match
if(variables.strMonkeyString EQ variables.strSubString){
if(len(variables.strSubString) GT len(variables.strBestSoFar)){
variables.strBestSoFar = variables.strSubString;
}
}else{
variables.strMonkeyString = "";
}
}
writeoutput(variables.intCount);
writeoutput("<br />");
writeoutput(variables.strBestSoFar);
</cfscript>
Critisicm, comments and feedback welcome, but just a bit of fun.
