# C++. Modifying a particular program, loop

• C/++/#
Gold Member
Hello! As a new past time I wanted to learn some coding. A friend of mine wrote a program and explained it from A to Z to me, it took like 2 hours.
I wanted to play a bit with the program by modifying it.
Here's the code:
Code:
#include <stdlib.h>
#include <iostream>
#include <time.h>

using namespace std;

static const int M = 32;
static const int N = 54;
static const int TRIES = 1000000;

int tries() {

bool board[N + 2][M + 2] = {};

for (int placed = 0;;) {
// Pick an x,y position on the board...
int x = rand() % N + 1; // so the N is for the x-coordinate
int y = rand() % M + 1; // M for y
// Is there already a stone at this position?
if (board[x][y])
// Ignore it and go pick another position
continue;
if (board[x][y - 1] || board[x - 1][y] || board[x + 1][y] || board[x][y + 1])
// Return the number of stones that have been placed
return placed;
// Place a stone at this position
board[x][y] = true;
// Keep track of the number of stones that have been placed
placed++;
}
}

int main() {
srand(time(0));
int placed = 0;
for (int t = 0; t < TRIES; t++)
placed += tries();
float average = placed / (float)TRIES;
cout << "It took an average of " << average << " tries" << endl;
}
Basically what the program does is pick a random MxN matrix element, check whether that element was already picked, in case of yes, go back and repeat the process to pick a random matrix element. If the matrix element was not picked before, check out whether the adjacent entries were already picked. If not, repeat. If there's an adjacent entry stop and return "placed", which corresponds to the number of chosen matrix elements.
Repeat the process "TRIES" times. Finally, report the average "placed" value we get after "TRIES" tries.
For example if you pick N=M=8 then the program will tell you how many pieces a program that places chess pieces randomly over a chess board will have to put in average so that 2 pieces are adjacent. For N=M=19 you have the answer for the 19x19 goban (go board).
Now for fun I wanted to see whether the relation for a square board size (or square matrix in the program) would be linear with N (turns out that it is! Or almost...).
So I wanted to create a new loop in the program that would execute it for N=M=j where j goes from 2 to 100.
I have tried several things, all failed. Also the way N and M are defined, I am not sure I can change their values (they would change if I assignate their value to j).
The following code:
Code:
#include <stdlib.h>
#include <iostream>
#include <time.h>

using namespace std;

for (int j=2;j<101;j++)
static const int N = j;

static const int TRIES = 100000;

int tries() {

bool board[N + 2][N + 2] = {};

for (int placed = 0;;) {

int x = rand() % N + 1;
int y = rand() % N + 1;

if (board[x][y])

continue;
if (board[x][y - 1] || board[x - 1][y] || board[x + 1][y] || board[x][y + 1])

return placed;

board[x][y] = true;

placed++;
}
}

int main() {

srand(time(0));
int placed = 0;
for (int t = 0; t < TRIES; t++)
placed += tries();
float average = placed / (float)TRIES;
cout << "It took an average of " << average << " tries" << endl;

}
returns lots of errors during the compile:
Code:
PFadjacency.cpp:7:1: error: expected unqualified-id before ‘for’
for (int j=2;j<101;j++)
^
PFadjacency.cpp:7:14: error: ‘j’ does not name a type
for (int j=2;j<101;j++)
^
PFadjacency.cpp:7:20: error: ‘j’ does not name a type
for (int j=2;j<101;j++)
^
PFadjacency.cpp:14:16: error: ‘N’ was not declared in this scope
bool board[N + 2][N + 2] = {};
^
PFadjacency.cpp:21:13: error: ‘board’ was not declared in this scope
if (board[x][y])
^
PFadjacency.cpp:24:13: error: ‘board’ was not declared in this scope
if (board[x][y - 1] || board[x - 1][y] || board[x + 1][y] || board[x][y + 1])
^
PFadjacency.cpp:28:9: error: ‘board’ was not declared in this scope
board[x][y] = true;
^
Google told me that's because I defined a loop outside the main function.
So I tried to define the loop inside the main function. The problem is that it does not know what N stands for when I do so, because the function "tries()" is written before "main()"...

Here's another attempt. I first define N to be 1 before both functions are written. And then in main() I try the loop. And I get the error that N is "read only". Details:
Code:
#include <stdlib.h>
#include <iostream>
#include <time.h>

using namespace std;

static const int N = 1;

static const int TRIES = 100000;

int tries() {

bool board[N + 2][N + 2] = {};

for (int placed = 0;;) {

int x = rand() % N + 1;
int y = rand() % N + 1;

if (board[x][y])

continue;
if (board[x][y - 1] || board[x - 1][y] || board[x + 1][y] || board[x][y + 1])

return placed;

board[x][y] = true;

placed++;
}
}

int main() {

for (int j=2;j<101;j++) {
N=j;
srand(time(0));
int placed = 0;
for (int t = 0; t < TRIES; t++)
placed += tries();
float average = placed / (float)TRIES;
cout << "It took an average of " << average << " tries" << endl;
}
}
returns
Code:
PFadjacency.cpp: In function ‘int main()’:
N=j;
^

Also, I cannot seem to compile when I change "static const int N" for "int N", and I don't understand why. Here is what I got (from the very last code I posted here) when I try so:
Code:
PFadjacency.cpp: In function ‘int tries()’:
PFadjacency.cpp:14:33: error: variable-sized object ‘board’ may not be initialized
bool board[N + 2][N + 2] = {};
^

Related Programming and Computer Science News on Phys.org
Borek
Mentor
You have to make the board dynamically allocated using a "new" operator. Pass the size of the board as a parameter to the tries(int n). Then put your loop loop in the main() and call tries(n).

D H
Staff Emeritus
Also, I cannot seem to compile when I change "static const int N" for "int N", and I don't understand why. Here is what I got (from the very last code I posted here) when I try so:
Code:
PFadjacency.cpp: In function ‘int tries()’:
PFadjacency.cpp:14:33: error: variable-sized object ‘board’ may not be initialized
bool board[N + 2][N + 2] = {};
^

Strictly speaking, bool board[N+2][N+2] is illegal in C++ unless N is a compile-time constant. For example, #define N 42 or static const int N = 42; make N a compile-time constant. You have made N vary in runtime, so you can't do this. Strictly speaking, that is.

In C, variable length arrays such as your board[N+2][N+2] have been perfectly okay since the 1999 version of the C standard, and even earlier as a non-standard extension. For some reason, the C++ standards committee thinks this idea is dumber than dumb and rejected it in the 2011 version of the C++ standard. On the other hand, programmers think this idea is very useful. Douglas Gregor, one of the clang/llvm developers said "Users really seem to want this feature. It's a fairly common extension, and when we tried to ban it out of principle (in Clang), our users reacted *very* strongly."

Variable length arrays are a non-standard extension of C++ in gcc, clang, llvm, and the Intel compilers. The one limitation: You can't use initializers on them. The solution is to do the initialization as a separate instruction. Here's one way to fix your problem:
Code:
    bool board[N + 2][N + 2];
std::memset (board, 0, (N+2)*(N+2)*sizeof(bool));
You'll have to add a #include <cstring> directive to your source file to make this work.

Now, for the rest of your code. Note how I used std::memset rather than the unqualified memset. You are using using namespace std; in your code. This is a widely perceived as a very, very bad practice. Getting into the habit of typing those extra five characters std:: will save your butt one day.

The same goes for using #include <cstdlib> instead of #include <stdlib.h>. You are trying to program in C++, so use the C++ headers rather than the C headers. The C++ headers put those standard library functions in the std namespace. The old-style C headers put the standard library functions in the global namespace.

Namespaces are your friend. They are fences between your code and other code, and as Robert Frost said, "Good fences make good neighbors." Keep those fences intact. Using the using directive and #including the old-style C headers tears down the fence between the names in the standard library names and the names in your code. An example: little things like double y0; can cause all kinds of trouble if you #include <math.h>. This is but one of many collisions you would never expect.

Here's what I would do with the start of your code:
Code:
#include <cstdlib>          // Instead of #include <stdlib.h>
#include <iostream>
#include <ctime>            // Instead of #include <time.h>

/* using namespace std; */  // NEVER DO THIS!
What this means is that you need to prefix calls to library functions such as rand with std::. Yes, it's five extra characters of typing. Code is written once, read many times. The reader of your code will appreciate those five extra characters. It tells the reader right off the bat that what you are calling is in the standard library. That's rather obvious for rand(). It's not so obvious other times.

The next item I'm going to address is your use of rand(). This is arguably one of the biggest mistakes in the C library. There are some implementations of rand() for which rand()%2 yields the rather non-random sequence 0,1,0,1,0,1,0,1,...

This is what the MacOS man page has to say about rand(): rand, rand_r, srand, sranddev -- bad random number generator. The Linux man page says However, on older rand() implementations, and on current implementations on different systems, the lower-order bits are much less random than the higher-order bits. Do not use this function in applications intended to be portable when good randomness is needed. (Use random(3) instead.). There are many, many pseudo random number generators that are vastly superior to rand(). No matter what system you use, DON'T USE RAND.

If you have access to C++11, that version of the standard has pretty much solved the random number generator problem, at least for those who dot nned a cryptographically secure random number generator. You don't. The reason rand() oftentimes is so very, very bad is a collision between between "standardese" (a technical language used by standards authors that superficially looks somewhat like English) and the way experts in the field of pseudo random number generator describe random number generators.

The authors of C++11 were faced with a dilemma: Write the standard per standard "standardese", in which case int rand() {return 42;} would pass muster, or tell compiler writers that they must implement a known set of pseudo random number generator algorithms. The authors of C++11 chose to violate the standards of how to write good standards in the case of random number generators. The result is that with C++11 you have your choice of good to very good PRNGs. Here's a C++11 version of the start of your function tries, modified to take the size of the board as an input:

Code:
typedef std::minstd_rand PRNG;    // Minimum standard random number generator,
// Numerical Recipes (1993)
// typedef std::ranlux24 PRNG;    // 24-bit RANLUX generator by
// Martin Lüscher and Fred James, 1994
// typedef std::ranlux48 PRNG;    // 48-bit RANLUX generator
// typedef std::mt19937 PRNG;     // 32-bit Mersenne Twister by
// Matsumoto and Nishimura, 1998
// typedef std::mt19937_64 PRNG;  // 64-bit Mersenne Twister
int tries(int N) {

bool board[N+2][N+2];
std::memset (board, 0, (N+2)*(N+2)*sizeof(bool));
static std::random_device rd;
static PRNG generator (rd());
std::uniform_int_distribution<> random_1_N(1, N);

for (int placed = 0;;) {

int x = random_1_N(generator);
int y = random_1_N(generator);
...
placed++;
}
}

jbunniii