無限の猿定理を試してみた。

「時間をしっかりかけてランダムに文字を作り続けることで、どんな文章でも多分作成できる。」というのが無限の猿定理らしいのですが、実際プログラムして動かしてみたらどれくらい時間がかかるのだろうかと試してみました。

色々なページですとタイプライターのキーボードは約100とあるのですが、ascii コードで32( )から126(~)までの95キャラクターで組んでおります。

見たまんまなのですが、monkey_aim に目標にする言葉 hamlet を入れていますので、適宜入れ替えてみてください。

import random
import time
from tqdm.notebook import tqdm
monkey_aim=list("hamlet")

monkey_word=[]
before_time=time.time()
for i in tqdm(range(95**len(monkey_aim))):
    monkey_word.append(chr(random.randint(32,127)))
    if len(monkey_word)>len(monkey_aim):
        del monkey_word[0]
    if monkey_aim==monkey_word:
        print(i)
        break
print(time.time()-before_time)

試してみると3文字くらいまで僕の環境では1秒程度で終わるのですが、4文字で当たりが無く最後まで検索して143秒程度、なので6文字にチャレンジしようとすると単純に143*95*95で1290575秒、14日22時間29分35秒になります。

そんなことはやってられないので rust で最適化してスピードアップを図ってみようかと思います。

use rand::Rng;
use std::char;
use std::time::{Instant};

fn rnd_word() -> char{
    let mut rng = rand::thread_rng();
    let n1: u32 = rng.gen_range(32..=126);
    unsafe { char::from_u32_unchecked(n1) }
    //char::from_u32(n1).unwrap()
}

fn main() {
    let monkey_aim: Vec<char> = "hamlet".chars().collect();

    let mut monkey_word: Vec<char> = Vec::new();

    let start = Instant::now();
    let end = 95_u128.pow(monkey_aim.len() as u32);

    'outer:for _a in 1..=end{
        monkey_word.push(rnd_word());
        if monkey_word.len() > monkey_aim.len(){
            monkey_word.remove(0);
        }
        if monkey_aim == monkey_word{
            println!("{}/{},{}%",_a,end,(100*_a)/end);
            break 'outer;
        }
    }
    let duration = start.elapsed();
    println!("{:?}",duration);
}

まぁ、コピペの塊で python のとほぼ一緒のハズです。*1

これだと、5文字で当たりが無く最後まで検索して僕の環境では135秒くらいなので、6文字で当たりが無しの予測値が12825秒、3時間33分45秒なので３-4時間で終わる予定で、実測13016秒。*2

いや、わかってはいたのですが、Hello world! の12文字すらも遠い道です。

何がやりたかったんだ？と言われたら、ただやってみたかったとしか言いようがありません。

*1:時間さえ考えなければこのままでも19文字くらいまではいけるはず。ただ、7文字以上だと時間が1日以上かかるのでテストするのはやめておきました。

*2:この2つからだと rust は python の大体100倍くらいの処理速度って計算になりますね。6文字でも3.88秒で出たこともあるので本当に運。