prisoners_riddle.cpp

// Prisoners Puzzle YT Video by Veritasium ////////////////////////////////////

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>

#define EXPERIMENTS 100000
#define PRISONERS 1000

using namespace std;

// Box ////////////////////////////////////////////////////////////////////////

class Box {
public:
    int slip;
};

// Prisoner ///////////////////////////////////////////////////////////////////

class Prisoner {
public:
    int number;
    int search_for_number(Box boxes[]);
};

int Prisoner::search_for_number(Box boxes[]) {
    int loop_size = 0;
    int next_box = this->number;
    do {
        next_box = boxes[next_box].slip;
        loop_size ++;
    } while(next_box != this->number);
    return loop_size;
}

// Warden /////////////////////////////////////////////////////////////////////

class Warden {
    Box boxes[PRISONERS];
    Prisoner prisoners[PRISONERS];

public:
    void init();
    int start_procedure();
};

void Warden::init() {
    for(int i = 0; i < PRISONERS; i++) {
        boxes[i].slip = i;
    }
    random_shuffle(boxes, boxes + PRISONERS);

    for(int i = 0; i < PRISONERS; i++) {
        prisoners[i].number = i;
    }
    random_shuffle(prisoners, prisoners + PRISONERS);

}

int Warden::start_procedure() {
    int longest_loop = 0;
    for(int i = 0; i < PRISONERS; i++) {
        int loop_size = prisoners[i].search_for_number(boxes);
        if (loop_size > longest_loop) {
            longest_loop = loop_size;
        }
    }
    return longest_loop;
}

// Main ///////////////////////////////////////////////////////////////////////

int main() {
    srand(time(NULL));
    Warden warden;

    for(int k = 0; k < 1; k++) {
        int success = 0;
        for(int i = 0; i < EXPERIMENTS; i++) {
            warden.init();
            int r = warden.start_procedure();
            if(r <= (PRISONERS / 2)) success ++;
        }

        cout << ((double) success * 100) / (double) EXPERIMENTS << "\%" <<endl;
    }
    return 0;
}

// Prisoners' Riddle //////////////////////////////////////////////////////////