Skip to content

Instantly share code, notes, and snippets.

@h4tr3d
Forked from anonymous/gist:8c59f44ee3c03eec81dc
Last active August 29, 2015 14:15
Show Gist options
  • Save h4tr3d/d79e2e7def7a907f473f to your computer and use it in GitHub Desktop.
Save h4tr3d/d79e2e7def7a907f473f to your computer and use it in GitHub Desktop.
// Test.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream> // std::cout
#include <algorithm> // std::random_shuffle
#include <vector> // std::vector
#include <ctime> // std::time
#include <cstdlib> // std::rand, std::srand
void dark_helper(std::vector<int> &myvector)
{
for (int i = 0; i < 100; i++)
{
bool bFound = false;
int currentNumber = i;
int previousNumber = -1;
for (int j = 0; j < 50; j++)
{
if (myvector[currentNumber] == i)
{
bFound = true;
break;
}
previousNumber = currentNumber;
currentNumber = myvector[currentNumber];
}
if (bFound == false) {
std::swap(myvector[currentNumber], myvector[previousNumber]);
}
}
}
bool experiment()
{
std::vector<int> myvector;
for (int i=0; i<100; ++i) myvector.push_back(i);
std::random_shuffle ( myvector.begin(), myvector.end() );
// dark friend
dark_helper(myvector);
for (int i=0; i <100;i++)
{
bool bFound = false;
int currentNumber = i;
for (int j = 0; j < 50; j++)
{
if (myvector[currentNumber] == i)
{
bFound = true;
break;
}
currentNumber = myvector[currentNumber];
}
if (bFound == false)
return false;
}
return true;
}
int _tmain(int argc, _TCHAR* argv[])
{
std::srand ( unsigned ( std::time(0) ) );
long experiments = 0;
long succeededExperiments = 0;
for(;;)
{
experiments++;
if (experiment())
succeededExperiments++;
if (experiments % 10000 == 0)
std::cout << experiments << " - " << (double)succeededExperiments / experiments << std::endl;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment