#include <algorithm>
#include <chrono>
#include <iostream>
#include <random>
class Boxes
{
private:
unsigned * _boxes;
size_t _count;
std::default_random_engine _randomEngine;
public:
Boxes(size_t count) :
_count(count)
{
_boxes = new unsigned[_count];
for (size_t i = 0u; i < _count; i++)
_boxes[i] = i;
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
_randomEngine = std::default_random_engine(seed);
}
void Shuffle()
{
std::shuffle(_boxes, &_boxes[_count], _randomEngine);
}
bool Find(unsigned number) const
{
size_t index = number;
for (size_t steps = _count / 2u; steps > 0u; steps--)
{
if (_boxes[index] == number)
return true;
index = _boxes[index];
}
return false;
}
~Boxes()
{
delete[] _boxes;
}
};
int main()
{
const unsigned maxTestCases = 10000;
const unsigned max = 100;
Boxes boxes(max);
unsigned failureCount = 0u;
for (unsigned testCaseCount = 0u; testCaseCount < maxTestCases; testCaseCount++)
{
boxes.Shuffle();
for (unsigned i = 0; i < max; i++)
{
if (!boxes.Find(i))
{
failureCount++;
break;
}
}
}
std::cout << "Prisonner count: " << max << ", test case count: " << maxTestCases << " --> success rate: " << (double)(maxTestCases - failureCount) / maxTestCases << std::endl;
return 0;
}
