infinite monkey theorem

InfiniteMoneky.cpp

// https://runestone.academy/runestone/books/published/cppds/Introduction/DefiningFunctions.html

#include <iostream>
#include <random>
#include <string>
#include <chrono>

std::mt19937 rng;

std::string gerateRandomString(int length) {
    int from = 'a' - 1; // So we can use the previus ascii code as a space
    int max = 'z';
    std::uniform_int_distribution<uint32_t> uint_dist10(from, max);
    std::string random;
    random.resize(length);
    for (int i = 0; i < length; i++) {
        int randomInt = uint_dist10(rng);
        char randomChar = randomInt == from ? ' ' : randomInt;
        random[i] = randomChar;
    }
    return random;
}

int scoreStrings(std::string text1, std::string text2) {
    int result = 0;
    for (int i = 0; i < text1.size(); i++) {
        if (text1[i] == text2[i]) {
            result++;
        } else {
            break;
        }
    }
    return result;
}

int main() {
    std::string target = "methinks it is like a weasel";
    rng.seed(time(NULL));

    int bestScore = 0;
    std::string bestString = "";

    int logOnEvery = 100;
    int i = 1;
    
    auto start = std::chrono::high_resolution_clock::now();

    while (bestString != target) {
        int left = target.size() - bestScore; // Genrate only the missing letters
        std::string nextChunk = gerateRandomString(left);
        std::string nextBestString = bestString + nextChunk;
        int nextScore = scoreStrings(target, nextBestString);
        
        if (nextScore > bestScore) {
            nextBestString.resize(nextScore); // So only keep the good values
            bestString = nextBestString;
            bestScore = nextScore;
        }

        if ((i % logOnEvery) == 0) {
            std::cout << "iteration= " << i << ", score= " << bestScore << ", string= " << bestString << std::endl;
        }
        i++;
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::seconds>( end - start ).count();
    std::cout << "FOUND!" << std::endl;
    std::cout << bestString << std::endl;
    std::cout << "DONE on iteration " << i << " generated in " << duration << " seconds!!" << std::endl;
}