I am trying to solve the 280th problem in Project Euler, and for this I wrote the following simulation:
#include <stdio.h> #include <stdlib.h> #include <time.h> #include <sys/time.h> /* Directions 1 2 3 4 */ int grid[5][5] = { {0, 0, 0, 0, 2}, {0, 0, 0, 0, 2}, {0, 0, 0, 0, 2}, {0, 0, 0, 0, 2}, {0, 0, 0, 0, 2} }; int InitPos[2] = {2, 2}; int MaxExp = 5000000; bool Success = false; int StepCount = 0; int ExpNumber = 1; int AntsBag = 0; void Init(); void CarryFood(int * pos); void LeftFood(int * pos); bool checkMovability(int * pos, int direction); bool moveToDirection(int pos[2], int direction); bool checkSuccess(); void ShowResult(); int main(int argc, char const *argv[]) { timeval curTime; gettimeofday(&curTime, NULL); int milli = curTime.tv_usec / 1000; time_t t; srand((unsigned)time(&t)); //timeTData*.txt corresponds to using "time(&t)" above //milliData.txt corresponds to using "milli" variable above //timeTUnsigData*.txt corresponds to using "(unsigned)time(&t)" above printf("%% Experiment Number : %d \n", MaxExp); while(ExpNumber <= MaxExp) { Init(); int pos[2]; pos[0] = InitPos[0]; pos[1] = InitPos[1]; do{ int direction = (rand() % 4) + 1; if (moveToDirection(pos, direction)) { StepCount++; } if (pos[1] == 4&&grid[pos[0]][4]==2&&AntsBag==0) { CarryFood(pos); } if (pos[1] == 0&&grid[pos[0]][0]==0&&AntsBag==2) { LeftFood(pos); } checkSuccess(); } while(!Success); ShowResult(); ExpNumber++; } return 0; } void Init() { Success = false; StepCount = 0; AntsBag = 0; int gridInit[5][5] = { {0, 0, 0, 0, 2}, {0, 0, 0, 0, 2}, {0, 0, 0, 0, 2}, {0, 0, 0, 0, 2}, {0, 0, 0, 0, 2} }; for (int i = 0; i < 5; ++i) { for (int j = 0; j < 5; ++j) { grid[i][j] = gridInit[i][j]; } } } void ShowResult() { /* for (int i = 0; i < 5; ++i) { printf("\n"); for (int j = 0; j < 5; ++j) { printf("%d ", grid[i][j]); } } */ printf("%d %d\n", StepCount, ExpNumber); } void CarryFood(int * pos) { AntsBag = 2; grid[pos[0]][4] = 0; } void LeftFood(int * pos) { AntsBag = 0; grid[pos[0]][0] = 2; } bool checkMovability(int * pos, int direction) { switch(direction) { case 1: { if(pos[1]==0){ return false; } break; } case 2: { if (pos[0]==0) { return false; } break; } case 3: { if (pos[0]==4) { return false; } break; } case 4: { if (pos[1]==4) { return false; } break; } default: { printf("Wrong direction input is given!!\n"); return false; break; } } return true; } bool moveToDirection(int * pos, int direction) { if ( !checkMovability(pos, direction) ) { return false; } switch(direction){ case 1: { pos[1] -= 1; break; } case 2: { pos[0] -= 1; break; } case 3: { pos[0] += 1; break; } case 4: { pos[1] += 1; break; } default: { printf("I'm stunned!\n"); return false; break; } } return true; } bool checkSuccess() { for (int i = 0; i < 5; ++i) { if (grid[i][0] != 2) { return false; } } //printf("Success!\n"); Success = true; return true; }
And redirected the output to a * .txt file and found the expected value of the number of steps with the following octave code:
clear load data.txt n = data(:,1); output_precision(15); mean(n) %% The actual data %% milliData1 -> 430.038224000000 %% milliData2 -> 430.031745000000 %% timeTData1 -> 430.029882400000 %% timeTData2 -> 430.019626400000 %% timeUnsigData1 -> 430.028159000000 %% timeUnsigData2 -> 430.009509000000
However, even I run the same code twice, I get different results, as you can see from the above results. (Note that I tried this with different srand (..) inputs for the reason that I'm going to explain).
I thought the reason for this is that I generate a random integer from 1 to 4 for random ant directions, because as far as I was, the probability distribution of this experiment should be the same as I repeat the experiment a large amount of time (in this case 5,000,000 times).
So my first question is: is this really a problem with the random integer generation method? If so, how can we overcome this problem, I mean, how can we generate an integer random number so that when we repeat the same experiment many times, the expected value between them is less than this result, which I have there is?