Amazon Interview Question
SDE1sCountry: United States
@Noobie: good tip. but wouldn't it be necessary to know the move history for applying en-passant here ? (at least the immediate last move)
I did not even know what is board[8][8]. Chess knowledge is pre-required for this solution.
and last I checked Chess was not part of computer science.
Yeah, right. Keep down voting. Chess will still not be part of Computer Science.
@VJ's code
2 possible inaccuracies:
1. forwardMove2 needs two conditions to be verified. Whether forwardMove == empty && forwardMove2 == empty.
Also, int forwardMove2 = isWhite? y+2:y-2; (instead of y++:y--)
2. Just checking isEmpty is not sufficient for DiagonalMoves. A diagonalMove for a white pawn is possible only if the position has a black piece. And likewise, a diagonalMove for a black pawn is possible only if the position has a white piece.
Haven't compiled the code. But, this should give a rough idea.
void possibleMoves( int board[8][8], x, y )
{
bool isWhite;
if( board[x][y] >= 1 && board[x][y] <= 9 )
isWhite = true;
else if( board[x][y] >= 11 && board[x][y] <= 19 )
isWhite = false;
if( isWhite && y == 1 )
{
if( board[x][y+1] == isEmpty() )
{
//cout << "Forward move : " << x << ", " << y+1 << endl;
if( board[x][y+2] == isEmpty() )
cout << "Forward move : " << x << ", " << y+2 << endl;
}
}
if( !isWhite && y == 6 )
{
if( board[x][y-1] == isEmpty() )
{
//cout << "Forward move : " << x << ", " << y-1 << endl;
if( board[x][y-2] == isEmpty() )
cout << "Forward move : " << x << ", " << y-2 << endl;
}
}
if( isWhite && y >= 1 && y <= 6 )
{
if( board[x][y+1] == isEmpty(x, y+1) )
cout << "Forward move : " << x << ", " << y+1 << endl;
if( x >= 1 && x <=6 )
{
if( board[x-1][y+1] == isOccupiedByBlack(x-1, y+1) )
cout << "Diagonal move : " << x-1 << ", " << y+1 << endl;
if( board[x+1][y+1] == isOccupiedByBlack(x+1, y+1) )
cout << "Diagonal move : " << x+1 << ", " << y+1 << endl;
}
else if( x == 0 )
{
if( board[x+1][y+1] == isOccupiedByBlack(x+1, y+1) )
cout << "Diagonal move : " << x+1 << ", " << y+1 << endl;
}
else if( x == 7 )
{
if( board[x-1][y+1] == isOccupiedByBlack(x-1, y+1) )
cout << "Diagonal move : " << x-1 << ", " << y+1 << endl;
}
}
if( !isWhite && y <= 6 && y >= 1 )
{
if( board[x][y-1] == isEmpty(x, y-1) )
cout << "Forward move : " << x << ", " << y-1 << endl;
if( x >= 1 && x <=6 )
{
if( board[x-1][y-1] == isOccupiedByWhite(x-1, y-1) )
cout << "Diagonal move : " << x-1 << ", " << y-1 << endl;
if( board[x+1][y-1] == isOccupiedByWhite(x+1, y-1) )
cout << "Diagonal move : " << x+1 << ", " << y-1 << endl;
}
else if( x == 0 )
{
if( board[x+1][y-1] == isOccupiedByWhite(x+1, y-1) )
cout< "Diagonal move: " << x+1 << ", " << y-1 << endl;
}
else if( x == 7 )
{
if ( board[x-1][y-1] == isOccupiedByWhite(x-1, y-1) )
cout << "Diagonal move: " << x-1 << ", " << y-1 << endl;
}
}
}
bool isLegal( int a, int b )
{
if( a < 0 || a > 7 || b < 0 || b > 7 )
return false;
}
bool isEmpty( int a, int b )
{
if( isLegal ( a, b ) )
if( (board[a][b] >= 1 && board[a][b] <= 9) || (board[a][b] >= 11 || board[a][b] <= 19) )
return false;
return true;
}
bool isOccupiedByBlack( int a, int b )
{
if( isLegal ( a, b ) )
if( board[a][b] >= 11 || board[a][b] <= 19 )
return true;
return false;
}
bool isOccupiedByWhite( int a, int b )
{
if( isLegal ( a, b ) )
if( board[a][b] >= 1 || board[a][b] <= 9 )
return true;
return false;
}
assuming we don't have the move history (for en-passant move), one of the solutions could be as follows:
void printPawnMoves(int[][] board, int x, int y) {
assert (isWithinBounds(x,y));
bool isWhite = false;
if (board[x][y] > 0 && board[x][y] < 10) { isWhite = true; }
else if (board[x][y] > 10 && board[x][y] < 20( { isWhite = false; }
else { assert(true); }
//each pawn can have a total of 4 possible moves
int forwardMove = isWhite ? y++:y--;
//forward moves
if (isWithinBounds(x,forwardMove)) {
if(isEmpty(board,x,forwardMove)) {
cout << "(" + x + "," + forwardMove + ")\n";
}
//check if in the starting grid position
if (y == (isWhite ? 1 : 6)) {
int forwardMove2 = isWhite ? y++:y--;
if(isEmpty(x,forwardMove2)) {
cout << "(" + x + "," + forwardMove2 + ")\n";
}
}
}
//diagonal moves
int diagLeftXMove = isWhite ? x++:x--;
int diagRightXMove = isWhite ? x--:x++;
if (isWithinBounds(diagLeftXMove,forwardMove) && !isEmpty(board,diagLeftXMove,forwardMove)) {
cout << "(" + diagLeftXMove + "," + forwardMove + ")\n";
}
if (isWithinBounds(diagRightXMove,forwardMove) && !isEmpty(board,diagRightXMove,forwardMove)) {
cout << "(" + diagRightXMove + "," + forwardMove + ")\n";
}
return;
}
bool isWithinBounds(int x, int y) {
return ((x < 0 || x > 7 || y < 0 || y > 7) ? true:false);
}
bool isEmpty(int[][] board,int x, int y) {
assert(isWithinBounds(x,y));
return ((board[x][y] < 0 || board[x][y] > 19 || board[x][y] == 10) ? true:false);
}
Really? Amazon is surely running short on engineers.
- Noobie March 27, 2013TIP: consider n-passant rule in this one!