Can't find the overflow

[tiedye1]

Hi, I've been working on this algorithm, and It works perfectly for small data sets
but when I try a larger set the pc (and thus the pp) variable is overflowing, but
they're longs so I don't know whats causing it.

Here's the relevant code.

c++:

int bp = 0; // Previous bit count         long pp = 0; // Previous path         int cnt = 0; // Path count         // Temp Vars         long pc = 0; // Current path         int bc = 0; // Current bit count         int r = 0;         int c = 0;         while(true)         {                 if (pp != 0)                 {                         while(pp >> (bp-1) != 1) // This loop gets stuck because pp is negative, and the bits that are checked are zero                         {                                 --bp;                         }                 }                 if (cnt == 664)                 {                         cout << cnt << "\n";                 }                 pc = pp; // Current path                 pc &= ~(1 << (bp-1));                 bc = 0; // Current bit count                 r = 0;                 c = 0;                 for (unsigned int i = 0; i < input[0]-1 + input[1]-1; ++i)                 {                         if (r == input[0] - 1 ? false : grd[r+1][c] == 0)                         {                                 if (c == input[1] -1 ? false : grd[r][c+1] == 0)                                 {                                         ++bc;                                         if (bc == bp)                                         {                                                 ++r;                                         }else if (bc < bp)                                         {                                                 if (((pp >> (bc-1)) & 1) == 1)                                                 {                                                         ++c;                                                 }else                                                 {                                                         ++r;                                                 }                                         }else                                         {                                                 ++c;                                                 pc |= 1 << (bc-1);                                         }                                 }else                                 {                                         ++r;                                 }                         }else                         {                                 ++c;                         }                 }                 bp = bc;                 pp = pc;                 ++cnt;                 if (cnt % 100 == 0) cout << cnt << "\n";                 if (pp == 0) break;         }

Thanks for any help!

[Insectoid]

It would help if you told us what the algorithm is designed to do, and if you would use descriptive variable names. It's hard to read this code if I constantly have to look up what some variable is supposed to be. Also some comments would be nice.

[Zren]

What's considered a "small" and large dataset?

[tiedye1]

Sorry for the confusion, the purpose of the algorithm is to find all the possible paths through a grid to the opposite corner by moving only right and down.

The input is formatted like this in a file:
5 4
3
2 3
2 4
3 5

Where the first two numbers represent the number of rows and columns in the grid,
the second the number of impassible grid locations (X) and the remaining X lines the
coordinates of those impassible tiles.

c++:

void prb5() {         vector<int> input = vector<int>(); // Stores input numbers from file         string line;         ifstream inFile;         inFile.open("s5.in");         char str[256];         while(!inFile.eof())         {                 inFile >> str;                 input.push_back(atoi(str));         }         inFile.close();         // The first two numbers rpresent the width and hieght of the grid, these next two loops initialize the grid         vector<vector<int>> grd = vector<vector<int>>(input[0]);         for (int i = 0; i < grd.size(); ++i)         {                 grd[i] = vector<int>(input[1]);         }         for (int i = 0; i < input[0]; ++i)         {                 for (int j = 0; j < input[1]; ++j)                 {                         grd[i][j] = 0;                 }         }         // The next number (input[2]) represents the number of coordinate remaining in the file         // The next loop then reads those coordinates and set the corrisponding spots in the grid to one         for (int i = 0; i < input[2]; ++i)         {                 grd[input[i*2+3]-1][input[i*2+4]-1] = 1;         }         // Now loop through every grid segment (starting at the bottom right) and if both the grid to the right and down is either the edge or non-zero, set itself to 2 (non-zero)         for (int i = input[0]-1; i >= 0; --i)         {                 for (int j = input[1]-1; j >= 0; --j)                 {                         if (grd[i][j] != 0) continue;                         if (i == input[0]-1 && j == input[1]-1) continue;                                                 if ((i+1 <= input[0]-1 ? grd[i+1][j] != 0 : true) && (j+1 <= input[1]-1 ? grd[i][j+1] != 0 : true) || (i-1 >= 0 ? grd[i-1][j] != 0 : true) && (j-1 >= 0 ? grd[i][j-1] != 0 : true))                         {                                 grd[i][j] = 2;                         }                 }         }         // Every turn represents a point in the path wher there are to possible paths (right or down), non optional turns are not recorded         long long int previousTurnCount = 0; // Previous bit count         long long int previousPath = 0; // Previous path         long long int totalPathCount = 0; // Path count         // Temp vars         long long int currentPath = 0; // Current path         long long int currentTurn = 0; // Current bit count         int row = 0;         int col = 0;         while(true)         {                 if (previousPath != 0LL)                 {                         while(previousPath >> (previousTurnCount-1LL) != 1LL)                         {                                 --previousTurnCount;                         }                 }                 currentPath = previousPath & ~(1LL << (previousTurnCount-1LL)); // Current path                 currentTurn = 0; // Current bit count                 row = 0;                 col = 0;                 for (unsigned int i = 0; i < input[0]-1 + input[1]-1; ++i) // We know how far we have to go (taxicab distance never changes for the same starting and ending points)                 {                         // Check to see if there is a choice in the next turn                         if (row == input[0] - 1 ? false : grd[row+1][col] == 0)                         {                                 if (col == input[1] -1 ? false : grd[row][col+1] == 0)                                 {                                         // If yes then:                                         ++currentTurn;                                         if (currentTurn == previousTurnCount) // If current turn is the last turn taken last time, go down (as last time we know we went right)                                         {                                                 ++row;                                         }else if (currentTurn < previousTurnCount) // If current turn is before the last turn taken last time, do what was done last time                                         {                                                 if (((previousPath >> (currentTurn-1LL)) & 1LL) == 1LL) // 1 = go right, 0 = go left                                                 {                                                         ++col;                                                 }else                                                 {                                                         ++row;                                                 }                                         }else // If current turn is after last turn taken last time, go right                                         {                                                 ++col;                                                 currentPath |= 1LL << (currentTurn-1LL);                                         }                                 }else // If no then go where possible                                 {                                         ++row;                                 }                         }else                         {                                 ++col;                         }                 }                 ++totalPathCount; // We made a new path, add one to the count                 if (currentPath == 0LL) break; // All turns are down, there are no more paths, exit the loop                 previousTurnCount = currentTurn;                 previousPath = currentPath;         }         cout << totalPathCount; }

[tiedye1]

Oh, and its works as is, but I don't know how many of those long long ints are necessary;

A large data set is say a 25 by 25 grid with 1000 or more impassible tiles.

[Zren]

So your treating the previousPath/currentPath variables as an array of directions, and since there's only two directions, you only need the single bit to represent the direction. You're overflowing since your trying to access an index larger than your "array". Which means you don't know the maximum path length required.

First let's figure out the length of your "arrays".

https://en.wikipedia.org/wiki/C_data_types
An int has 16 bits.
An long has 32 bits.
An long long has 64 bits.

Next, let's figure out the length we need. You seem to already know it.

code:

for (unsigned int i = 0; i < input[0]-1 + input[1]-1; ++i) // We know how far we have to go (taxicab distance never changes for the same starting and ending points)

A 25x25 grid would need an array length of COLUMNS + ROWS - 1 which is 49. A length of 49 will overflow the regular long data type, but not a long long.

Since your algorithms problem doesn't define the limits of the COLUMNS and ROWS input, you should use a data type that can support much more variable lengths, like an array of booleans where you define the size manually.

---

Tips for making your code more legible:

code:

if (((previousPath >> (currentTurn-1LL)) & 1LL) == 1LL) // 1 = go right, 0 = go left

Use constants, so you have more variable names and less magic numbers floating around.

code:

long long RIGHT = 1; long long previousDirection = (previousPath >> (currentTurn-1LL)) & 1LL; if (previousDirection == RIGHT) // 1 = go right, 0 = go left

---

code:

grd[input[i*2+3]-1][input[i*2+4]-1] = 1;

Parse your giant input array into variables.

code:

int x = input[i*2+3]; int y = input[i*2+4]; grd[x-1][y-1] = 1;