Semantic Problem: Chess Check

[Script Coder]

I have written a solution to the problem http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110107&format=html . It runs and compiles correctly (syntax correct), but the judge says it gives the Wrong Answer. I know it is a lot to ask, but would someone mind looking my program over and seeing if they can spot the error?

#include <iostream>
using namespace std;

inline int raycast(char A[][8], int i, int j, int di, int dj) {
	do {
		i+=di;		//change i value by deltaI
		j+=dj;		//change j value by deltaJ
	} while(i+di>=0 && j+dj>=0 && i+di<8 && j+dj<8 && A[i][j]=='.'); //continue until we are off the board or encounter a non empty space
	if(A[i][j]=='q' || A[i][j]=='b' || A[i][j]=='r') return(0);		//these pieces can attack a White king
	if(A[i][j]=='Q' || A[i][j]=='B' || A[i][j]=='R') return(1);		//these pieces can attack a Black king
	return(2);		//Nothing of interest found
}

inline void game(int g, int k) {			//outputs who is in check
	cout<<"Game #"<<g<<": "<<(k==1 ? "black king is in check.\n" : "white king is in check.\n");
}

inline bool BQR(char A[][8], int k, int ki, int kj, int g) {
	int X[3]={-1, 0, 1};
	for(int i=0; i<3 ; ++i) {
		for(int j=0; j<3; ++j) {		//generates all directions from a piece
			if(raycast(A, ki, kj, X[i], X[j])==k) {		//checks if there is an attacking piece in direction (X[i], X[j])
				game(g, k);
				return(true);
			}
		}
	}
	return(false);
}

inline bool N(char G[][8], int k, int ki, int kj, int g) {
	int A[2]={-2,2}, B[2]={-1,1};
	char n=(k==0 ? 'n' : 'N');		//Are we looking for a black or white Knight
	for(int i=0; i<2; ++i) {
		for(int j=0; j<2; ++j) {		//Generates all knight configurations from a piece
			if(ki+A[i]>=0 && ki+A[i]<8 && kj+B[j]>=0 && kj+B[j]>=0 && (G[ki+A[i]][kj+B[j]]==n || G[ki+B[j]][kj+A[i]]==n)) {		//if knight of correct colour is found
				game(g, k);																										//king is in check
				return(true);
			}
		}
	}
	return(false);
}

inline bool P(char A[][8], int k, int ki, int kj, int g) {
	if(k==0 && (A[ki-1][kj-1]=='p' || A[ki-1][kj+1]=='p')) {		//checks if pawn is attacking white king
		game(g, k);
		return(true);
	}
	if(k==1 && (A[ki+1][kj-1]=='P' || A[ki+1][kj+1]=='P')) {		//checks if pawn is attacking black king
		game(g, k);
		return(true);
	}
	return(false);
}

int main() {
	char A[8][8];
	for(int g=1; ; ++g) {		//holds the game number
		int kings[2][2]={{-1,-1},{-1,-1}};								//stores the location of the kings  kings[0] is the white king's location
		for(int i=0; i<8; ++i) for(int j=0; j<8; ++j) {	//input board and locate kings
			cin>>A[i][j];
			if(A[i][j]=='K') {
				kings[0][0]=i;
				kings[0][1]=j;
			} else if(A[i][j]=='k') {
				kings[1][0]=i;
				kings[1][1]=j;
			}
		}
		if(kings[0][0]==-1) break;		//if there are no kings found then we are done
		
		bool flag=true;
		for(int k=0; k<2; ++k) {
			if(BQR(A, k, kings[k][0], kings[k][1], g)) {flag=false; break;}		//checks if king[k] is being ckeched by a Bishop, Queen or Rook
			if(N(A, k, kings[k][0], kings[k][1], g)) {flag=false; break;}		//checks if king[k] is being checked by a Knight
			if(P(A, k, kings[k][0], kings[k][1], g)){flag=false; break;}		//checks if king[k] is being checked by a Pawn
		}
		if(flag) cout<<"Game #"<<g<<":  no king is in check.\n";			//if no king is in check out put this
	}
}
			

EDIT: I have tried to comment clearly, please ask if anything needs explaining.

[ne555]

You are accessing out of bounds in `P()'

Also, calling your `game()' function from the check tests is poor style.

in_check=-1;
for(int k=0; k<2; ++k)
   if( BQR(/**/) or N(/**/) or P(/**/) )
      in_check = k;
//now use `in_check' to output the result 

[MiiNiPaa]

I will look at it later, but for now I should say: do not use inline keyword if you don't sure what it is doing.
Here it is doing absolutely nothing.

[Script Coder]

You are accessing out of bounds in `P()'

I will fix that thank you.

Also, calling your `game()' function from the check tests is poor style.

I know, I put myself under time constraints so that was the solution that came to mind first.

I will look at it later, but for now I should say: do not use inline keyword if you don't sure what it is doing.
Here it is doing absolutely nothing.

I know exactly what it is doing, it is ensuring my program does not make costly function calls.

[MiiNiPaa]

Nope. Compiler is free to ignore inline keyword or its absence.
The only funnction gcc inlined when I compiled this is game() function.
When I deleted inline declarations and compiled on -O3, it inlined everything.
Note that inlining large functions can hamper code caching and slow down your program.

The only thing it really does everytime is prevent multiple definition error from linker.

An implementation is not required to perform this
inline substitution at the point of call;
standard 7.1.2.2

Some other info:
http://stackoverflow.com/questions/3212571/usefulness-of-the-inline-feature
http://stackoverflow.com/a/3366987

Basically: do not think that you are smarter than compiler.

Edit: Google code guide:

A decent rule of thumb is to not inline a function if it is more than 10 lines long. Beware of destructors, which are often longer than they appear because of implicit member- and base-destructor calls!

Another useful rule of thumb: it's typically not cost effective to inline functions with loops or switch statements (unless, in the common case, the loop or switch statement is never executed).

http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml#Inline_Functions

[Script Coder]

Interesting, thank you.
After making the relevant changes to my P() function (given below) the judge is still giving me a WA. Where is the problem?

inline bool P(char A[][8], int k, int ki, int kj, int g) {
	if(k==0 && ki-1>=0 && kj-1>=0 && kj-1<8 && (A[ki-1][kj-1]=='p' || A[ki-1][kj+1]=='p')) {		//checks if pawn is attacking white king
		game(g, k);
		return(true);
	}
	if(k==1 && ki+1<8 && kj-1>=0 && kj+1<8 && (A[ki+1][kj-1]=='P' || A[ki+1][kj+1]=='P')) {		//checks if pawn is attacking black king
		game(g, k);
		return(true);
	}
	return(false);
}

[MiiNiPaa]

It is hard do determine what is wrong withiut knowing where is it wrong.
For example in message : no king is in check. there is two spaces between ':' and 'n', where in other places there is one. If they just gets the string and compares it with reference one it could give "not equals to reference" answer.

I have tested your program and it looks like everything is working fine here.
Will post again if I will find something.

[ne555]

It's still out of bounds.
if(k==0 && ki-1>=0 && kj-1>=0 && kj-1<8 && (A[ki-1][kj-1]=='p' || A[ki-1][kj+1]=='p'))

I'll suggest you to use sentinels instead.

[Script Coder]

I'll suggest you to use sentinels instead.

Would you mind explaining what a sentinel is, please.

I have corrected the double space error, and the out of bounds error, and still the judge is giving me WA. I'll keep hunting and post again if I find anything.

EDIT:
Code:

#include <iostream>
using namespace std;

inline int raycast(char A[][8], int i, int j, int di, int dj) {
	do {
		i+=di;		//change i value by deltaI
		j+=dj;		//change j value by deltaJ
	} while(i+di>=0 && j+dj>=0 && i+di<8 && j+dj<8 && A[i][j]=='.'); //continue until we are off the board or encounter a non empty space
	if(A[i][j]=='q' || A[i][j]=='b' || A[i][j]=='r') return(0);		//these pieces can attack a White king
	if(A[i][j]=='Q' || A[i][j]=='B' || A[i][j]=='R') return(1);		//these pieces can attack a Black king
	return(2);		//Nothing of interest found
}

inline void game(int g, int k) {			//outputs who is in check
	cout<<"Game #"<<g<<": "<<(k==1 ? "black king is in check.\n" : "white king is in check.\n");
}

inline bool BQR(char A[][8], int k, int ki, int kj, int g) {
	int X[3]={-1, 0, 1};
	for(int i=0; i<3 ; ++i) {
		for(int j=0; j<3; ++j) {		//generates all directions from a piece
			if(raycast(A, ki, kj, X[i], X[j])==k) {		//checks if there is an attacking piece in direction (X[i], X[j])
				game(g, k);
				return(true);
			}
		}
	}
	return(false);
}

inline bool N(char G[][8], int k, int ki, int kj, int g) {
	int A[2]={-2,2}, B[2]={-1,1};
	char n=(k==0 ? 'n' : 'N');		//Are we looking for a black or white Knight
	for(int i=0; i<2; ++i) {
		for(int j=0; j<2; ++j) {		//Generates all knight configurations from a piece
			if(ki+A[i]>=0 && ki+A[i]<8 && kj+B[j]>=0 && kj+B[j]<8 && (G[ki+A[i]][kj+B[j]]==n || G[ki+B[j]][kj+A[i]]==n)) {		//if knight of correct colour is found
				game(g, k);																										//king is in check
				return(true);
			}
		}
	}
	return(false);
}

inline bool P(char A[][8], int k, int ki, int kj, int g) {
	if(k==0 && ki-1>=0 && kj-1>=0 && kj+1<8 && (A[ki-1][kj-1]=='p' || A[ki-1][kj+1]=='p')) {		//checks if pawn is attacking white king
		game(g, k);
		return(true);
	}
	if(k==1 && ki+1<8 && kj-1>=0 && kj+1<8 && (A[ki+1][kj-1]=='P' || A[ki+1][kj+1]=='P')) {		//checks if pawn is attacking black king
		game(g, k);
		return(true);
	}
	return(false);
}

int main() {
	char A[8][8];
	for(int g=1; ; ++g) {		//holds the game number
		int kings[2][2]={{-1,-1},{-1,-1}};								//stores the location of the kings  kings[0] is the white king's location
		for(int i=0; i<8; ++i) for(int j=0; j<8; ++j) {	//input board and locate kings
			cin>>A[i][j];
			if(A[i][j]=='K') {
				kings[0][0]=i;
				kings[0][1]=j;
			} else if(A[i][j]=='k') {
				kings[1][0]=i;
				kings[1][1]=j;
			}
		}
		if(kings[0][0]==-1) break;		//if there are no kings found then we are done
		
		bool flag=true;
		for(int k=0; k<2; ++k) {
			if(BQR(A, k, kings[k][0], kings[k][1], g)) {flag=false; break;}		//checks if king[k] is being ckeched by a Bishop, Queen or Rook
			if(N(A, k, kings[k][0], kings[k][1], g)) {flag=false; break;}		//checks if king[k] is being checked by a Knight
			if(P(A, k, kings[k][0], kings[k][1], g)){flag=false; break;}		//checks if king[k] is being checked by a Pawn
		}
		if(flag) cout<<"Game #"<<g<<": no king is in check.\n";			//if no king is in check out put this
	}
	return(0);
}
			

[MiiNiPaa]

Damn. I checked pawn and knight functions but never tried to check BQR function, because I though it is trivial and nobody will make a mistake in it.
Long story short your program will think that white king in check in following cases:

K.b    K..
...    ...
...    ..r

(Every piece move as a queen for your algorithm)

[ne555]

The idea of sentinels is to make your matrix bigger and surround it with values that would not affect the computation.
They are just to `cath' out of bounds access in a defined way.
char board[12][12] = {};