Pie`
July 6th, 2010, 05:16
The name may sound a little odd, but the 'Infinite Monkey Theorem' states that states that a monkey hitting keys at random on a typewriter keyboard for an infinite amount of time will almost surely type a given text, such as the complete works of William Shakespeare although in this case I scaled it down a little to search a phrase such as "hello" while generating a large string from a given array of Charaters.
Generic output:
[com.a.imonkey.Monkey-1] Working with 63 characters.
[com.a.imonkey.Monkey-1] Total str length: 14073282
[com.a.imonkey.Monkey-1] Total str length: 28528525
[com.a.imonkey.Monkey-1] Total str length: 43032198
[com.a.imonkey.Monkey-1] Total str length: 58119300
[com.a.imonkey.Monkey-1] Total str length: 72945880
[com.a.imonkey.Monkey-1] Total str length: 88215333
[com.a.imonkey.Monkey-1] Total str length: 102659451
[com.a.imonkey.Monkey-1] Total str length: 113370625
[com.a.imonkey.Monkey-1] Total str length: 126659535
[com.a.imonkey.Monkey-1] Total str length: 143059009
[com.a.imonkey.Monkey-1] Total str length: 158360036
[com.a.imonkey.Monkey-1] Total str length: 173260926
[com.a.imonkey.Monkey-1] Total str length: 187243843
[com.a.imonkey.Monkey-1] Total str length: 201289221
[com.a.imonkey.Monkey-1] Total str length: 216467931
[com.a.imonkey.Monkey-1] Total str length: 229475694
[com.a.imonkey.Monkey-1] Total str length: 242453772
[com.a.imonkey.Monkey-1] Total str length: 258707502
[com.a.imonkey.Monkey-1] Total str length: 273659243
[com.a.imonkey.Monkey-1] Total str length: 288759530
[com.a.imonkey.Monkey-1] Total str length: 304698775
[com.a.imonkey.Monkey-1] Total str length: 319279507
[com.a.imonkey.Monkey-1] Total str length: 333833352
[com.a.imonkey.Monkey-1] Total str length: 349791869
[com.a.imonkey.Monkey-1] Total str length: 365209732
[com.a.imonkey.Monkey-1] Total str length: 381135878
[com.a.imonkey.Monkey-1] Total str length: 396873504
[com.a.imonkey.Monkey-1] Total str length: 412728530
[com.a.imonkey.Monkey-1] Total str length: 428284092
[com.a.imonkey.Monkey-1] Total str length: 444331567
[com.a.imonkey.Monkey-1] Total str length: 459658953
[com.a.imonkey.Monkey-1] substring "hello" found after: 466655266 key presses.
[com.a.imonkey.Monkey-1] surrounding text: pC9dYhello
The total str length that is being displayed is shown every 5 seconds as an update on the programs process.
The source:
package com.a.imonkey;
import java.util.Random;
import java.util.Timer;
import java.util.TimerTask;
public class Monkey implements Runnable {
private char[] keys = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWX YZ1234567890 ".toCharArray();
private int id;
private String substr;
private StringBuilder str = new StringBuilder();
private long strlen = 0;
public void run() {
Random r = new Random();
Timer t = new Timer();
log("Working with "+keys.length+" characters.");
t.scheduleAtFixedRate(new TimerTask() {
public void run() {
log("Total str length: "+strlen);
}
}, 5000, 5000);
while(true) {
strlen++;
str.append(keys[r.nextInt(keys.length)]);
if(str.length() >= substr.length() && str.substring(str.length()-substr.length()).equals(substr)) {
log("substring \""+substr+"\" found after: "+strlen+" key presses.");
log("surrounding text: "+str.toString());
t.cancel();
Main.totalpresses += strlen;
break;
}
if(str.length() > (substr.length()*2))
str = new StringBuilder(str.substring(str.length()-substr.length()));
}
}
public Monkey(int id, String substr) {
this.id = id;
this.substr = substr;
}
private void log(String str) {
System.out.println("["+this.getClass().getName()+"-"+id+"] "+str);
}
}
Example executor:
package com.a.imonkey;
public class Main {
private int monkeys = 0;
public static long totalpresses = 0;
private String substr = "hello";
public Main() {
new Thread(new Monkey(++monkeys, substr)).run();
}
public static void main(String args[]) {
new Main();
}
}
Side note to anyone wondering why I didn't use str.endsWith(substr), the reason for this was that I discovered the endsWith() method badly hurts the performance. While using endsWith() it was only completing around 30k iterations in a 5 second block whereas with my method it's completing several million iterations in a 5 second block.
Generic output:
[com.a.imonkey.Monkey-1] Working with 63 characters.
[com.a.imonkey.Monkey-1] Total str length: 14073282
[com.a.imonkey.Monkey-1] Total str length: 28528525
[com.a.imonkey.Monkey-1] Total str length: 43032198
[com.a.imonkey.Monkey-1] Total str length: 58119300
[com.a.imonkey.Monkey-1] Total str length: 72945880
[com.a.imonkey.Monkey-1] Total str length: 88215333
[com.a.imonkey.Monkey-1] Total str length: 102659451
[com.a.imonkey.Monkey-1] Total str length: 113370625
[com.a.imonkey.Monkey-1] Total str length: 126659535
[com.a.imonkey.Monkey-1] Total str length: 143059009
[com.a.imonkey.Monkey-1] Total str length: 158360036
[com.a.imonkey.Monkey-1] Total str length: 173260926
[com.a.imonkey.Monkey-1] Total str length: 187243843
[com.a.imonkey.Monkey-1] Total str length: 201289221
[com.a.imonkey.Monkey-1] Total str length: 216467931
[com.a.imonkey.Monkey-1] Total str length: 229475694
[com.a.imonkey.Monkey-1] Total str length: 242453772
[com.a.imonkey.Monkey-1] Total str length: 258707502
[com.a.imonkey.Monkey-1] Total str length: 273659243
[com.a.imonkey.Monkey-1] Total str length: 288759530
[com.a.imonkey.Monkey-1] Total str length: 304698775
[com.a.imonkey.Monkey-1] Total str length: 319279507
[com.a.imonkey.Monkey-1] Total str length: 333833352
[com.a.imonkey.Monkey-1] Total str length: 349791869
[com.a.imonkey.Monkey-1] Total str length: 365209732
[com.a.imonkey.Monkey-1] Total str length: 381135878
[com.a.imonkey.Monkey-1] Total str length: 396873504
[com.a.imonkey.Monkey-1] Total str length: 412728530
[com.a.imonkey.Monkey-1] Total str length: 428284092
[com.a.imonkey.Monkey-1] Total str length: 444331567
[com.a.imonkey.Monkey-1] Total str length: 459658953
[com.a.imonkey.Monkey-1] substring "hello" found after: 466655266 key presses.
[com.a.imonkey.Monkey-1] surrounding text: pC9dYhello
The total str length that is being displayed is shown every 5 seconds as an update on the programs process.
The source:
package com.a.imonkey;
import java.util.Random;
import java.util.Timer;
import java.util.TimerTask;
public class Monkey implements Runnable {
private char[] keys = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWX YZ1234567890 ".toCharArray();
private int id;
private String substr;
private StringBuilder str = new StringBuilder();
private long strlen = 0;
public void run() {
Random r = new Random();
Timer t = new Timer();
log("Working with "+keys.length+" characters.");
t.scheduleAtFixedRate(new TimerTask() {
public void run() {
log("Total str length: "+strlen);
}
}, 5000, 5000);
while(true) {
strlen++;
str.append(keys[r.nextInt(keys.length)]);
if(str.length() >= substr.length() && str.substring(str.length()-substr.length()).equals(substr)) {
log("substring \""+substr+"\" found after: "+strlen+" key presses.");
log("surrounding text: "+str.toString());
t.cancel();
Main.totalpresses += strlen;
break;
}
if(str.length() > (substr.length()*2))
str = new StringBuilder(str.substring(str.length()-substr.length()));
}
}
public Monkey(int id, String substr) {
this.id = id;
this.substr = substr;
}
private void log(String str) {
System.out.println("["+this.getClass().getName()+"-"+id+"] "+str);
}
}
Example executor:
package com.a.imonkey;
public class Main {
private int monkeys = 0;
public static long totalpresses = 0;
private String substr = "hello";
public Main() {
new Thread(new Monkey(++monkeys, substr)).run();
}
public static void main(String args[]) {
new Main();
}
}
Side note to anyone wondering why I didn't use str.endsWith(substr), the reason for this was that I discovered the endsWith() method badly hurts the performance. While using endsWith() it was only completing around 30k iterations in a 5 second block whereas with my method it's completing several million iterations in a 5 second block.