zen_meditation_zen - 2020-03-29

5:52 AM

Good morning

I hope everything is going well with you there amidst this crisis of Covid19

@Aconcagua I see, so:

vector<vector<int>> matrix(n*n, vector<int>(m*m));

the chess board one is another matrix?

like this:

int x_move[9] = { 0, 2, 1, -1, -2, -2, -1, 1, 2 };
int y_move[9] = { 0, 1, 2, 2, 1, -1, -2, -2, -1 };
vector<vector<int>> chessmatrix(n, vector<int>(m));
for (size_t k = 0; k <= 8; k++) {
		int next_i = x1 + x_move[k];
		int next_j = y1 + y_move[k];
		if (isInside(next_i, next_j, n, m))
			chessmatrix[next_i][next_j] = 1;

	}

(x1, y1) is the starting position

Papa

8:04 AM

Ok, so:

we get n and m, so I would decide the adjacency matrix based on n?

something like

 vector<vector<int>> matrix(n*n, vector<int>(n*n));

?

and the chessboard matrix would simply be:

x1--; y1--; x2--; y2--;
int x_move[9] = { 0, 2, 1, -1, -2, -2, -1, 1, 2 };
int y_move[9] = { 0, 1, 2, 2, 1, -1, -2, -2, -1 };
vector<vector<int>> chessmatrix(n, vector<int>(m));
for (size_t k = 0; k <= 8; k++) {
		int next_i = x1 + x_move[k];
		int next_j = y1 + y_move[k];
		if (isInside(next_i, next_j, n, m))
			chessmatrix[next_i][next_j] = 1;

	}

Aconcagua

9:58 AM

Adjacency matrix is a square matrix always...

mn x mn

Papa

I don't know what is happening to me these days, please just overlook these blind mistakes

 vector<vector<int>> matrix(n*m, vector<int>(n*m));

so this is our adjacency matrix

for Adj matrix, the vertices are the indices

and the values 1 if they exist are the connected edges

now the connected edges according to knight valid moves, how would they get represented?

Also, we get a coordinate as a starting position, how would it possible to apply the exact previous path problem?

Aconcagua

10:21 AM

Well, you need a way to map the 2-D coordinates of the board into the 1-D coordinates of the adjacency matrix...

Papa

exactly

because it's the only way

Aconcagua

I proposed something alike to be able to use a 1D vector to represent a 2D matrix earlier. Then for efficiency reasons, but now we can re-use exactly that for adjacency matrix...

Papa

I remember when

though we haven't implemented it then

though this is the way

16

Q: Convert a 2D array index into a 1D index

I have two arrays for a chess variant I am coding in java...I have a console version so far which represents the board as a 1D array (size is 32) but I am working on making a GUI for it and I want it to appear as a 4x8 grid, so I have a 2-dimensional array of JPanels... Question is, is there any...

Ah, I remember, you proposed the way too

So, now, we would convert the coordinates or the matrix itself?

this would do it

for (q = 0; q < n; q++) {
    for (t = 0; t < m; t++) {
        b[q * m + t] = a[q][t];
    }
}

Aconcagua

10:45 AM

Something like that, yes...

Or, as you head before:

int next_i = x1 + x_move[k];
int next_j = y1 + y_move[k];
chessMatrix[i*m+j][next_i*m+next_j] = 1;

Papa

But

I still haven't cleared one thing, how does the chessboard matrix look like?

Aconcagua

And as you see, now you get a reference of current field (i, j) to it's possibly reachable fields (next_i, next_j)....

Well, you won't materialise the chess board itself.

Just the adjacency matrix for that one.

The adjaceny matrix would look like:

       (0, 0) (0, 1) (0, 2) ... (0, 7) (1, 0), ... (7, 7)
(0, 0)
(0, 1)
...
(0, 7)
(1, 0)
...
(7, 7)

for a classic 8x8 chess board.

Solely that you cannot use the 2D coordinates as index directly, you need to re-map

You want to know if you can reach e. g. (6, 7) from (1, 0), which would be true for a bishop or the queen...

Bb1-h7

Papa

interesting

please what did you mean by chessMatrix?

is the adj matrix?

int n, m, x1, y1, x2, y2;
	int x_move[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
	int y_move[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
	cin >> n >> m >> x1 >> y1 >> x2 >> y2;
	vector<vector<int>> matrix(n*m, vector<int>(n*m));
	for (size_t i = 0; i < n*m; i++) {
		for (size_t j = 0; j < n*m; j++) {
			for (size_t k = 0; k < 8; k++) {
				int next_i = i + x_move[k];
				int next_j = j + y_move[k];
				if (isInside(next_i, next_j, n, m))
					matrix[i*m + j][next_i*m + next_j] = 1;
			}

		}
	}

you mean this in some way?

but

 matrix[i*m + j][next_i*m + next_j] = 1;

instead of m we do n*m?

Aconcagua

12:03 PM

I assumed you named your adjacency matrix 'chessMatrix'. Not your intention?

What's the distance of two items in the same column, but neighbouring row?

Size of a column, isn't it?

So to get y-th column in x-th row, you need to calculate x*sizeof(column) + y...

Papa

12:29 PM

@Aconcagua right, it was

@Aconcagua I see, so the above is correct then?

int n, m, x1, y1, x2, y2;
	int x_move[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
	int y_move[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
	cin >> n >> m >> x1 >> y1 >> x2 >> y2;
        x1--; y1--; x2--; y2--;
	vector<vector<int>> matrix(n*m, vector<int>(n*m));
	for (size_t i = 0; i < n*m; i++) {
		for (size_t j = 0; j < n*m; j++) {
			for (size_t k = 0; k < 8; k++) {
				int next_i = x1 + x_move[k];
				int next_j = y1 + y_move[k];
				if (isInside(next_i, next_j, n, m))
					matrix[i*m + j][next_i*m + next_j] = 1;

this instead

if (isInside(next_i, next_j, n, m))

shoud be

if (isInside(i*m + j, next_i*m + next_j, n, m))

it doesn't seem correct the implementation

@Aconcagua this is our target right?

or would something like this be simpler:

for (q = 0; q < n; q++) {
    for (t = 0; t < m; t++) {
        b[q * m + t] = a[q][t];
    }
}

Aconcagua

12:58 PM

Looked good until you tried to correct yourself.

isInside refers to the actual chessboard, not the adjacency matrix.

So isInside(next_i, next_j, n, m) was fine!

This variant actually is stricter!

Assume 8x8 chessboard, and you consider field (3, 7).

Then (1,8), (2,9), (4,9), (5,8) all are outside of the chess board. But if you apply the formula to the adjacency matrix, you'll discover that all of these would be inside. (4, 9), for instance, would identify the same field as (5,1), though!

Papa

exactly right

I get it now

but this won't output the matrix

int n, m, x1, y1, x2, y2;
	int x_move[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
	int y_move[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
	cin >> n >> m >> x1 >> y1 >> x2 >> y2;
    x1--; y1--; x2--; y2--;
	vector<vector<int>> matrix(n*m, vector<int>(n*m));
	for (size_t i = 0; i < n*m; i++) {
		for (size_t j = 0; j < n*m; j++) {
			for (size_t k = 0; k < 8; k++) {
				int next_i = x1 + x_move[k];
				int next_j = y1 + y_move[k];
				if (isInside(next_i, next_j, n, m))
				    matrix[i*m + j][next_i*m + next_j] = 1;

given:

5 5
3 3
5 1

for (size_t i = 0; i < n*m; i++) {
		for (size_t j = 0; j < m*n; j++)
			cout << matrix[i][j] << " ";
		cout << endl;
	}

Aconcagua

1:29 PM

Why would you want to output the matrix?

Papa

just to check it

actually it doesn't output anything

Papa

2:23 PM

I think the problem is with this one:

or the indices I should say rather

  matrix[i*m + j][next_i*m + next_j] = 1;

shouldn't it be

 matrix[next_i*m + next_i][next_j*m + next_j] = 1;

?

this is the matrix we want I assume

0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

and we forgot the original placement of the knight

so we would add:

int x_move[9] = { 0, 2, 1, -1, -2, -2, -1, 1, 2 };
int y_move[9] = { 0, 1, 2, 2, 1, -1, -2, -2, -1 };

so this the adjacency matrix of the chessboard representation

0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Aconcagua

5:05 PM

> shouldn't it be
matrix[next_i*m + next_i][next_j*m + next_j] = 1;

What's the meaning of that???

You want to add an edge for chessboard position (i, j) to (next_i, next_j).

matrix[(i, j)][(next_i, next_j)] = 1

Just as you'd add in a normal matrix an edge from node v1 to node v2 as

matrix[v1][v2] = 1;

> and we forgot the original placement of the knight
[...]

Well, no.

Original placement is position (i, j). You want to have edges from this position to all others that can be reached.

Adding 0, 0 to the offsets array would add an edge from (i, j) to itself.

Papa

I see

Aconcagua

That might be meaningful for a chess AI, to represent the option of leaving the knight at the place it is right now (and move another piece instead). But that's not meaningful for our specific problem.

Papa

I see

interesting notes

though, the above code doesn't print anything

when doing debugging,the problem stems from matrix assignment line

Aconcagua

OK, you know now the code location where to fail. So you seem to access the matrix out of bounds. Have you checked values of i, j next_i and next_j?

You know, it's nice to know where your programme crashes. More interesting, though, is to know why it crashes there...

Papa

I didn't

@Aconcagua right

Papa

5:28 PM

this one i*m + j

gets out of range

so we need an isInside for that too

Aconcagua

5:38 PM

If i and j are in range of board, i*m + j cannot be out of range for matrix...

Papa

6:01 PM

well

I did this

simply

for (size_t i = 0; i < n*m; i++) {
		for (size_t j = 0; j < n*m; j++) {
			for (size_t k = 0; k < 8; k++) {
				int next_i = x1 + x_move[k];
				int next_j = y1 + y_move[k];
				if (isInside(next_i, next_j, n, m)) {
				    cout << i*m + j << " " << next_i*m + next_j << endl;
				    //matrix[i*m + j][next_i*m + next_j] = 1;
				}
			}

		}
	}

for this i*m + j I got up to 144

this is for

5 5
3 3
5 1

Aconcagua

6:37 PM

Wait, i and j must be in range [0, n) and [0, m) respectively!!!

They are coordinates of the chess board, not the adjacency matrix!

You need to get a clear image: When do you iterate over chess board, when over matrix!

Alternatively:

You can do it the other way round as well:

Iterate over the adjacency matrix and calculate board coordinates from indices:

for(size_t i = 0; i < n * m; ++i)
{
    // board row : i / m;
    // board column: i % m;
    // ..
}

(note: no double loop any more!)

Papa

@Aconcagua what do you mean, we don't have the board matrix to iterate over

Papa

7:45 PM

Ok, I see

so you mean this right?

matrix[(i/m)  + (i % m)][next_i*m + next_j] = 1;

Papa

8:24 PM

can you please re explain this process a little bit more, I really want to know if I am having the right picture of not

Aconcagua

10:01 PM

We iterate over the fields of a board that actually never gets materialised.

Still that board is the basis of the entire problem...

So for (i : [0, n) { for(j : [0: m) { [...] } } is fine.

If you really iterate over [0, n*m) in a single loop, then correct accessing would be:

matrix[(i/m) * m + (i % m)][n_i*m + n_j]

i/m * m + i % m by definition is equivalent to simply i, though...

Aconcagua

10:19 PM

By the way:

((i / m) + x) *m + (i % m + y) == i / m * m + i % m + x*m + y == i + x*m + y

You actually don't need a 2D-array then for your k-loop, you can have that as a 1D array as well:

-2 * m +/- 1, -1 * m +/- 2, 1*m +/- 2, 2*m +/- 1

The isInside check still must consider the actual field borders!

Oh... Maybe this helps to understand better:

for(i : [0, n))
    for(j : [0, m))

for(i : [0, n*m))

You have two different ways to address one and the same chess board...

Notice how fields get their addresses in real chess?

a8, b8, c8, ... h8
a7, b7, c7, ... h7
...
a1, b1, c1, ... h1

With the double loop, you iterate with inner loop over the letters a-h, with outer loop over the numbers 1-8.

a1 = (0, 0), b1 = (0, 1), ...

With the single loop, you give each field its own address:

a1 = 0, b1 = 1, b2 = 2, ... h1 = 7, a2 = 8, b2 = 9, ... h2 = 15, a3 = 16, ... h8 = 63

and you iterate over these.

Still you iterate over the non-materialised board.

Just noticing: You can use the chess board coordinates as indices: You need a four-dimensional matrix then, though:

bool matrix[n][m][n][m];

Transcript for

$Mathematics$ zen_meditation_zen