# Finding a path across a grid after randomly filling some proportion of it

Essentially, we must be able to get from one side of the grid to the opposite side of the grid. My code tests for up to down and left to right.

However, this is painfully slow and I'm wondering if there's some way to optimize it. I think the recursion makes sense, and it seems to be working properly based on some of the tests I had outputted. Essentially, I'm finding the proportion of the grid p that needs to be covered in random points to have nearly a 100% chance of there being a path to the other side. A path being defined as moving only left right up or down to get to the opposite side.

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

using namespace std;

const int SIDELENGTH = 2000;
int grid[SIDELENGTH][SIDELENGTH] = {{0}};
int temp[SIDELENGTH][SIDELENGTH] = {{0}};

void copyGrid(bool g2t){
if (g2t){
for (int i = 0; i < SIDELENGTH; i++){
for (int j = 0; j < SIDELENGTH; j++){
temp[i][j] = grid[i][j];
}
}
}

else{
for (int i = 0; i < SIDELENGTH; i++){
for (int j = 0; j < SIDELENGTH; j++){
grid[i][j] = temp[i][j];
}
}
}
}
void printGrid(int a [SIDELENGTH][SIDELENGTH]){
for (int i = 0; i < SIDELENGTH; i++){
for (int j = 0; j < SIDELENGTH; j++){
cout << a[i][j] << " ";
}
cout << endl;
}
cout << endl;
}

void makeGrid(double prop){
for (int i = 0; i < SIDELENGTH; i++){
for (int j = 0; j < SIDELENGTH; j++){
if (rand() / double(RAND_MAX) < prop)
grid[i][j] = 1;
}
}
}
bool solvePath(int x,int y, bool up){//boolean up is if it's up to down or not if not then it's left to right
//  printGrid(grid);
if (!up){
if (y == SIDELENGTH-1 && grid[x][y] != 0)
return true;
}
if (up){
if (x == SIDELENGTH-1 && grid[x][y] != 0)
return true;
}
if (grid[x][y] == 0 )//ayy c++ doesn't have array index out of bounds lol
return false;

grid[x][y] ++;// increment because we already touched this square
if (x > 0){
if (grid[x-1][y] < grid[x][y] && solvePath(x-1,y,up) )
return true;
}
if (x < SIDELENGTH-1){
if (grid[x+1][y] < grid[x][y] && solvePath(x+1,y,up) )
return true;
}
if (y > 0){
if (grid[x][y-1] < grid[x][y] && solvePath(x,y-1,up))
return true;
}
if (y < SIDELENGTH-1){
if (grid[x][y+1] < grid[x][y] && solvePath(x,y+1,up))
return true;
}
return false;

}

bool solve(double startP, double endP, double inc, int trials){

double numPaths=0, p=startP;
bool found;
for (int z = 0; z <(int)((endP-startP)/inc); z++){
numPaths = 0;
p+= inc;
for (int j = 0; j < trials; j++){
//    printGrid(grid);
fill(grid,grid + SIDELENGTH*SIDELENGTH,0);//reset to 0 grid
//  printGrid(grid);

makeGrid(p);
copyGrid(true);
//  printGrid(grid);
for (int i = 0; i < SIDELENGTH; i++){
found = solvePath(i,0,false);
if (found){
numPaths ++;
break;
}
}
//  printGrid(grid);
copyGrid(false);//undo increments
for(int i = 0; i < SIDELENGTH; i++){
found = solvePath(0,i,true);
if (found){
numPaths ++;
break;
}
}
}
/*  printGrid(grid);
if (found)
cout << "PATH!" << endl;
else
cout << "NOPATH" << endl;
*/
}
setprecision(10);
cout << numPaths << endl;
cout << trials << endl;
cout << numPaths/trials << endl;
cout << "Probability for getting a path with p = " << p << " is " << (double)numPaths/(double)trials << endl;
}

}
int main(){
srand(time(0));
double duration;
clock_t start;
start = clock();
solve(0.58,0.61,0.005,100);
duration = (clock()-start)/(double)CLOCKS_PER_SEC;
cout << "Total time elapsed: " << duration << " seconds " << endl;
return 0;
}

• Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. – Simon Forsberg Jan 16 '17 at 17:45

this little bit of code

if (!up){
if (y == SIDELENGTH-1 && grid[x][y] != 0)
return true;
}
if (up){
if (x == SIDELENGTH-1 && grid[x][y] != 0)
return true;
}
if (grid[x][y] == 0 )//ayy c++ doesn't have array index out of bounds lol
return false;


is not indented correctly, which makes it hard to read

it should look like this instead

if (!up){
if (y == SIDELENGTH-1 && grid[x][y] != 0)
return true;
}
if (up){
if (x == SIDELENGTH-1 && grid[x][y] != 0)
return true;
}
if (grid[x][y] == 0 )//ayy c++ doesn't have array index out of bounds lol
return false;


personally I think that I would create some variables to hold the boolean conditionals because I think that this piece of your code can be simplified.

bool notUpAndSideLengthEqualsY = !up &&  y == SIDELENGTH-1 && grid[x][y] != 0;
bool upAndSideLengthEqualsX = up && x == SIDELENGTH-1 && grid[x][y] != 0;

if (notUpAndSideLengthEqualsY || upAndSideLengthEqualsX)
return true;
else if (grid[x][y] == 0)
return false;


Actually, what I would do here is factor out grid[x][y] == 0 and check that first, because all your statements require grid[x][y] != 0 do it would look more like this instead

bool notUpAndSideLengthEqualsY = !up &&  y == SIDELENGTH-1;
bool upAndSideLengthEqualsX = up && x == SIDELENGTH-1;

if (grid[x][y] == 0)
{
return false;
}
else if (notUpAndSideLengthEqualsY || upAndSideLengthEqualsX)
{
return true;
}


There is no need to Check this condition 3 times when once will suffice.

Another if statement chain I would simplify is this one

if (x > 0){
if (grid[x-1][y] < grid[x][y] && solvePath(x-1,y,up) )
return true;
}
if (x < SIDELENGTH-1){
if (grid[x+1][y] < grid[x][y] && solvePath(x+1,y,up) )
return true;
}
if (y > 0){
if (grid[x][y-1] < grid[x][y] && solvePath(x,y-1,up))
return true;
}
if (y < SIDELENGTH-1){
if (grid[x][y+1] < grid[x][y] && solvePath(x,y+1,up))
return true;
}


I would write these differently so that I didn't have to indent. these are all 3 condition if statements that you have made into nested if statements.

if (x > 0 && grid[x-1][y] < grid[x][y] && solvePath(x-1,y,up)) {
return true;
}
if (x < SIDELENGTH-1 && grid[x+1][y] < grid[x][y] && solvePath(x+1,y,up) ) {
return true;
}
if (y > 0 && grid[x][y-1] < grid[x][y] && solvePath(x,y-1,up)) {
return true;
}
if (y < SIDELENGTH-1 && grid[x][y+1] < grid[x][y] && solvePath(x,y+1,up)) {
return true;
}