JANUARY 25, 2011
Chess 2 is the second of the three problems in the 2011 Facebook Hacker Cup elimination round 1B. I completely forgot about round 1A last Saturday and was unable to compete then. In this problem, you find yourself faced with a modified game of chess played on a 16×16 board and that contains some new and interesting pieces. What you have to do is, given a set of pieces on the board, determine how many pieces are en prise, that is, under threats from another piece. Here are some thoughts on it…
First though, here’s a copy of the problem description:
After decades of shadowy demonstrations and delays from the game’s maker, Chess 2 has finally been released. You waited in line all night to be one of the first to purchase an example of the hot sequel to the classic original, and now you are finally getting a chance to open up your new investment and take a look inside. What you find is slightly puzzling; in addition to the traditional pieces, the game has been expanded to contain a number of pieces that are not actually original.
The best-known piece that has been added to the game is the nightrider. The nightrider can make any number of knight moves in a single direction, i.e., its offset from its initial position will be 2*m in one dimension and m in the other for some nonzero integer m. Like other “sliding” pieces, if one of the knight moves would cause it to take another piece it is not able to traverse beyond that point
The archbishop is also part of Chess 2. The archbishop can simply make any move that a knight or bishop could legally make.
The strangest new piece is the kraken. The kraken can move to any square on the board, regardless of the position of any other pieces, including its own current position.
You don’t feel like reading the manual to learn about how the new pieces fit into the standard chess opening positions, so instead you place some of the pieces randomly on the board. The game you’ve decided to play is simply to count how many pieces on the board are currently being threatened. A piece is threatened if another piece is able to move into its cell and take it (note that if the kraken moves into its own cell it does not take itself).
Input
Your input file will consist of a single integer N followed by N test cases. Each case will consist of, all separated by whitespace, an integer P followed by the identities and positions of P Chess 2 pieces. Pieces are described by a single character C to denote their type (see specification below) followed by two integers R and F, the 1-based rank and file, respectively, of the piece.
You’ve decided to ignore the colors of the pieces in this game. The color of the pieces will not be reflected in the input and so cannot affect your output.
To make room for the new pieces, the Chess 2 board is a 16 by 16 grid. No specified pieces will fall outside the board, and no two pieces will occupy the same position.
The types of pieces will be specified as follows, and no entries not present in this table will appear on the board:
Piece – Abbreviation
King – K
Queen – Q
Rook – R
Bishop – B
Knight – N
Nightrider – S
Archbishop – A
Kraken – E
Output
Output a single integer, the number of threatened pieces on the board, for each test case separated by whitespace.
Constraints
N = 20
3 <= P <= 64 1 <= R, F <= 16 C will be one of K, Q, R, B, N, S, A or E Example input 5 4 Q 1 1 B 3 1 B 5 1 B 1 4 3 S 1 1 K 2 3 S 3 5 4 N 1 1 B 3 3 Q 5 5 N 4 1 5 R 2 2 N 1 2 N 2 1 N 16 2 N 2 16 6 Q 1 1 Q 2 3 Q 3 5 Q 4 2 Q 5 4 E 1 5 Example output 2 1 3 4 6
What I decided to do is create a game board and calculate how many pieces can attack a given square at any time, if the position where a piece is located can be attacked (that is, if the threat value is at least 1) then it is added to the threatened piece counter.
One of the tricky parts was determining when a piece would block a second piece. This is an issue with pieces that can move an unlimited amount of squares within the board in a direction, such as the Rook, Bishop or Nightrider. For this to work correctly, one needs to know where all the pieces in the board are located before calculating the attack values on the board.
Also, I decided to catch ArrayIndexOutOfBounds exceptions so that my code could be simplified. This way many of the “if” checks necessary to prevent that from happening did not have to be coded. Since it was a programming contest and time was important I believe it makes sense.
The code ran very fast, even with the “most difficult” test cases since the code is relatively efficient and the test cases were small. My solution was accepted by Facebook so the code is also correct.
Anyway, here’s the source code I made, feel free to chime in on the comments:
import java.util.LinkedList;
import java.util.Scanner;
/**
* @author Luis Edgardo Argote Bolio http://argote.mx/
* @see http://argote.mx/
*/
public class Main {
public static Scanner in = new Scanner(System.in);
private static int boardSize = 16;
private static Square[][] board = new Square[boardSize][boardSize];
/**
* @param args
*/
public static void main(String[] args) {
int cases = in.nextInt();
for (int caseNum = 0; caseNum < cases; caseNum++) {
for (int i = 0; i < boardSize; i++) {
for (int j = 0; j < boardSize; j++) {
board[i][j] = new Square();
}
}
LinkedList<Piece> pieces = new LinkedList<Piece>();
int pieceCount = in.nextInt();
for (int pieceNum = 0; pieceNum < pieceCount; pieceNum++) {
String type = in.next();
int rank = in.nextInt() - 1;
int file = in.nextInt() - 1;
pieces.add(new Piece(type.charAt(0), rank, file));
}
for (int pieceNum = 0; pieceNum < pieceCount; pieceNum++) {
placePiece(pieces.get(pieceNum));
}
for (int pieceNum = 0; pieceNum < pieceCount; pieceNum++) {
calculateAttacks(pieces.get(pieceNum));
}
int threatened = 0;
for (int pieceNum = 0; pieceNum < pieceCount; pieceNum++) {
if (isThreatenend(pieces.get(pieceNum))) {
threatened++;
}
}
printBoard();
System.out.println(threatened);
}
}
/**
* This is a fairly simple function that basically just prints out the board
* status for each square
*/
public static void printBoard() {
for (int i = 0; i < boardSize; i++) {
for (int j = 0; j < boardSize; j++) {
System.out.print(board[i][j].toString() + "t");
}
System.out.println();
}
}
/**
* This method determines if a piece is "en prise", that is, threatened by
* another piece
*
* @param piece
* The piece for which the threat will be analyzed
* @return true if the piece is threatened, false if it's not
*/
public static boolean isThreatenend(Piece piece) {
int rank = piece.getRank();
int file = piece.getFile();
return board[rank][file].getHazardCount() > 0 ? true : false;
}
/**
* This places a given piece in a location in the board, this is done before
* calculating the attacks so that blocking pieces are considered
*
* @param piece
* The piece that will be placed on the board
*/
public static void placePiece(Piece piece) {
char type = piece.getType();
int rank = piece.getRank();
int file = piece.getFile();
board[rank][file].setType(type);
// System.out.println("Placing a " + type + " at " + rank + "," + file);
}
/**
* This calculates the squares that can be attacked by a given piece
*
* @param piece
* The piece that the attack will be calculated for
*/
public static void calculateAttacks(Piece piece) {
char type = piece.getType();
int rank = piece.getRank();
int file = piece.getFile();
switch (type) {
// King
case 'K':
captureKing(rank, file);
break;
// Rook
case 'R':
captureRook(rank, file);
break;
// Bishop
case 'B':
captureBishop(rank, file);
break;
// Queen
case 'Q':
captureQueen(rank, file);
break;
// Knight
case 'N':
captureKnight(rank, file);
break;
// Archbishop
case 'A':
captureArchbishop(rank, file);
break;
// Nightrider
case 'S':
captureNightrider(rank, file);
break;
// Kraken
case 'E':
captureKraken(rank, file);
break;
}
}
/**
* This method calculates which positions can be captured by a King, since a
* King can attack any of the 8 adjacent squares at any given time, they are
* accessed directly.
*
* If the index is out of bounds, the exception is caught and ignored. This
* decision was made for simplicity's sake.
*
* @param rank
* the rank on which the piece is located
* @param file
* the file on which the piece is located
*/
public static void captureKing(int rank, int file) {
try { // Up and left movement
board[rank - 1][file - 1].incrementHazard();
} catch (ArrayIndexOutOfBoundsException e) {
}
try { // Up movement
board[rank - 1][file].incrementHazard();
} catch (ArrayIndexOutOfBoundsException e) {
}
try { // Up and right movement
board[rank - 1][file + 1].incrementHazard();
} catch (ArrayIndexOutOfBoundsException e) {
}
try { // Left movement
board[rank][file - 1].incrementHazard();
} catch (ArrayIndexOutOfBoundsException e) {
}
try { // Right movement
board[rank][file + 1].incrementHazard();
} catch (ArrayIndexOutOfBoundsException e) {
}
try { // Down and Left movement
board[rank + 1][file - 1].incrementHazard();
} catch (ArrayIndexOutOfBoundsException e) {
}
try { // Down movement
board[rank + 1][file].incrementHazard();
} catch (ArrayIndexOutOfBoundsException e) {
}
try { // Down and Right movement
board[rank + 1][file + 1].incrementHazard();
} catch (ArrayIndexOutOfBoundsException e) {
}
}
/**
* This method calculates which positions can be captured by a Rook, since a
* Rook can attack any number of squares up, down, left or right this moves
* in each of that direction from the position of the piece.
*
* In this case, if there is a piece between the squares where piece passes
* through and a square after that in the same direction, its movement is
* blocked
*
* If the index is out of bounds, the exception is caught and ignored. That
* shouldn't happen on this method though. This decision was made for
* simplicity's sake.
*
* @param rank
* the rank on which the piece is located
* @param file
* the file on which the piece is located
*/
public static void captureRook(int rank, int file) {
int tmpRank;
int tmpFile;
// Up movements
tmpRank = rank - 1;
while (tmpRank >= 0) {
try {
board[tmpRank][file].incrementHazard();
if (board[tmpRank][file].getType() != ' ') {
break;
}
} catch (ArrayIndexOutOfBoundsException e) {
}
tmpRank--;
}
// Down movements
tmpRank = rank + 1;
while (tmpRank <= boardSize) {
try {
board[tmpRank][file].incrementHazard();
if (board[tmpRank][file].getType() != ' ') {
break;
}
} catch (ArrayIndexOutOfBoundsException e) {
}
tmpRank++;
}
// Left movements
tmpFile = file - 1;
while (tmpFile >= 0) {
try {
board[rank][tmpFile].incrementHazard();
if (board[rank][tmpFile].getType() != ' ') {
break;
}
} catch (ArrayIndexOutOfBoundsException e) {
}
tmpFile--;
}
// Right movements
tmpFile = file + 1;
while (tmpFile <= boardSize) {
try {
board[rank][tmpFile].incrementHazard();
if (board[rank][tmpFile].getType() != ' ') {
break;
}
} catch (ArrayIndexOutOfBoundsException e) {
}
tmpFile++;
}
}
/**
* This method calculates which positions can be captured by a Bishop, since
* a Bishop can attack any number of squares up-left, up-right, down-left or
* down-right this moves in each of that direction from the position of the
* piece.
*
* In this case, if there is a piece between the squares where piece passes
* through and a square after that in the same direction, its movement is
* blocked
*
* If the index is out of bounds, the exception is caught and ignored. That
* shouldn't happen on this method though. This decision was made for
* simplicity's sake.
*
* @param rank
* the rank on which the piece is located
* @param file
* the file on which the piece is located
*/
public static void captureBishop(int rank, int file) {
int tmpRank;
int tmpFile;
// Up and left movements
tmpRank = rank - 1;
tmpFile = file - 1;
while (tmpRank >= 0 && tmpFile >= 0) {
try {
board[tmpRank][tmpFile].incrementHazard();
if (board[tmpRank][tmpFile].getType() != ' ') {
break;
}
} catch (ArrayIndexOutOfBoundsException e) {
}
tmpRank--;
tmpFile--;
}
// Up and right movements
tmpRank = rank - 1;
tmpFile = file + 1;
while (tmpRank >= 0 && tmpFile <= boardSize) {
try {
board[tmpRank][tmpFile].incrementHazard();
if (board[tmpRank][tmpFile].getType() != ' ') {
break;
}
} catch (ArrayIndexOutOfBoundsException e) {
}
tmpRank--;
tmpFile++;
}
// Down and left movements
tmpRank = rank + 1;
tmpFile = file - 1;
while (tmpRank <= boardSize && tmpFile >= 0) {
try {
board[tmpRank][tmpFile].incrementHazard();
if (board[tmpRank][tmpFile].getType() != ' ') {
break;
}
} catch (ArrayIndexOutOfBoundsException e) {
}
tmpRank++;
tmpFile--;
}
// Down and right movements
tmpRank = rank + 1;
tmpFile = file + 1;
while (tmpRank <= boardSize && tmpFile <= boardSize) {
try {
board[tmpRank][tmpFile].incrementHazard();
if (board[tmpRank][tmpFile].getType() != ' ') {
break;
}
} catch (ArrayIndexOutOfBoundsException e) {
}
tmpRank++;
tmpFile++;
}
}
/**
* This method calculates which positions can be captured by a Queen, since
* a Queen is basically the fusion between a Bishop and a Rook, it just
* calls both of those capture methods
*
* @param rank
* the rank on which the piece is located
* @param file
* the file on which the piece is located
*/
public static void captureQueen(int rank, int file) {
captureRook(rank, file);
captureBishop(rank, file);
}
/**
*
* If the index is out of bounds, the exception is caught and ignored. This
* decision was made for simplicity's sake.
*
* @param rank
* the rank on which the piece is located
* @param file
* the file on which the piece is located
*/
public static void captureKnight(int rank, int file) {
try {
board[rank - 2][file - 1].incrementHazard();
} catch (ArrayIndexOutOfBoundsException e) {
}
try {
board[rank - 1][file - 2].incrementHazard();
} catch (ArrayIndexOutOfBoundsException e) {
}
try {
board[rank + 1][file - 2].incrementHazard();
} catch (ArrayIndexOutOfBoundsException e) {
}
try {
board[rank + 2][file - 1].incrementHazard();
} catch (ArrayIndexOutOfBoundsException e) {
}
try {
board[rank - 2][file + 1].incrementHazard();
} catch (ArrayIndexOutOfBoundsException e) {
}
try {
board[rank - 1][file + 2].incrementHazard();
} catch (ArrayIndexOutOfBoundsException e) {
}
try {
board[rank + 2][file + 1].incrementHazard();
} catch (ArrayIndexOutOfBoundsException e) {
}
try {
board[rank + 1][file + 2].incrementHazard();
} catch (ArrayIndexOutOfBoundsException e) {
}
}
/**
* This method calculates which positions can be captured by an Archbishop,
* since an Archbishop is basically the fusion between a Bishop and a
* Knight, it just calls both of those capture methods
*
* @param rank
* the rank on which the piece is located
* @param file
* the file on which the piece is located
*/
public static void captureArchbishop(int rank, int file) {
captureBishop(rank, file);
captureKnight(rank, file);
}
/**
* This method calculates which positions can be captured by a Nightrider,
* since a Nightrider can attack any number of squares 1up-2left, 2up-1left,
* 2up-1right, 1up-2right, 1down-2right, 2down-1right, 2down-1left or
* 1down-2left this moves in each of that direction from the position of the
* piece.
*
* In this case, if there is a piece between the squares where piece passes
* through and a square after that in the same direction, its movement is
* blocked
*
* If the index is out of bounds, the exception is caught and ignored. That
* shouldn't happen on this method though. This decision was made for
* simplicity's sake.
*
* @param rank
* the rank on which the piece is located
* @param file
* the file on which the piece is located
*/
public static void captureNightrider(int rank, int file) {
int tmpRank;
int tmpFile;
// Up and left movements
tmpRank = rank - 2;
tmpFile = file - 1;
while (tmpRank >= 0 && tmpFile >= 0) {
try {
board[tmpRank][tmpFile].incrementHazard();
if (board[tmpRank][tmpFile].getType() != ' ') {
break;
}
} catch (ArrayIndexOutOfBoundsException e) {
}
tmpRank -= 2;
tmpFile--;
}
// Left and up movements
tmpRank = rank - 1;
tmpFile = file - 2;
while (tmpRank >= 0 && tmpFile >= 0) {
try {
board[tmpRank][tmpFile].incrementHazard();
if (board[tmpRank][tmpFile].getType() != ' ') {
break;
}
} catch (ArrayIndexOutOfBoundsException e) {
}
tmpRank--;
tmpFile -= 2;
}
// Up and right movements
tmpRank = rank - 2;
tmpFile = file + 1;
while (tmpRank >= 0 && tmpFile <= boardSize) {
try {
board[tmpRank][tmpFile].incrementHazard();
if (board[tmpRank][tmpFile].getType() != ' ') {
break;
}
} catch (ArrayIndexOutOfBoundsException e) {
}
tmpRank -= 2;
tmpFile++;
}
// Right and up movements
tmpRank = rank - 1;
tmpFile = file + 2;
while (tmpRank >= 0 && tmpFile <= boardSize) {
try {
board[tmpRank][tmpFile].incrementHazard();
if (board[tmpRank][tmpFile].getType() != ' ') {
break;
}
} catch (ArrayIndexOutOfBoundsException e) {
}
tmpRank--;
tmpFile += 2;
}
// Down and left movements
tmpRank = rank + 2;
tmpFile = file - 1;
while (tmpRank <= boardSize && tmpFile >= 0) {
try {
board[tmpRank][tmpFile].incrementHazard();
if (board[tmpRank][tmpFile].getType() != ' ') {
break;
}
} catch (ArrayIndexOutOfBoundsException e) {
}
tmpRank += 2;
tmpFile--;
}
// Left and down movements
tmpRank = rank + 1;
tmpFile = file - 2;
while (tmpRank <= boardSize && tmpFile >= 0) {
try {
board[tmpRank][tmpFile].incrementHazard();
if (board[tmpRank][tmpFile].getType() != ' ') {
break;
}
} catch (ArrayIndexOutOfBoundsException e) {
}
tmpRank++;
tmpFile -= 2;
}
// Down and right movements
tmpRank = rank + 2;
tmpFile = file + 1;
while (tmpRank <= boardSize && tmpFile <= boardSize) {
try {
board[tmpRank][tmpFile].incrementHazard();
if (board[tmpRank][tmpFile].getType() != ' ') {
break;
}
} catch (ArrayIndexOutOfBoundsException e) {
}
tmpRank += 2;
tmpFile++;
}
// Right and down movements
tmpRank = rank + 1;
tmpFile = file + 2;
while (tmpRank <= boardSize && tmpFile <= boardSize) {
try {
board[tmpRank][tmpFile].incrementHazard();
if (board[tmpRank][tmpFile].getType() != ' ') {
break;
}
} catch (ArrayIndexOutOfBoundsException e) {
}
tmpRank++;
tmpFile += 2;
}
}
/**
* This method calculates which positions can be captured by a Kraken, since
* it can capture any other square it iterates through all the squares in
* the board and marks them as attackable.
*
* If the index is out of bounds, the exception is caught and ignored. That
* shouldn't happen on this method though. This decision was made for
* simplicity's sake.
*
* @param rank
* the rank on which the piece is located
* @param file
* the file on which the piece is located
*/
public static void captureKraken(int rank, int file) {
for (int i = 0; i < boardSize; i++) {
for (int j = 0; j < boardSize; j++) {
if (i == rank && j == file) { // Skip the square it's at
continue;
}
try {
board[i][j].incrementHazard();
} catch (ArrayIndexOutOfBoundsException e) {
}
}
}
}
}
/**
* This class defines each square for the board, it keeps track of a threat
* counter and the type of piece on the square. It is very straightforward so
* the methods are not commented
*
* @author Luis Edgardo Argote Bolio
* @see http://argote.mx/
*/
class Square {
private int hazardCount;
private char type;
public Square() {
this.hazardCount = 0;
this.type = ' ';
}
public void incrementHazard() {
this.hazardCount++;
}
public int getHazardCount() {
return hazardCount;
}
public void setHazardCount(int hazardCount) {
this.hazardCount = hazardCount;
}
public char getType() {
return type;
}
public void setType(char type) {
this.type = type;
}
public String toString() {
return "(" + type + "," + hazardCount + ")";
}
}
/**
* This class defines a piece object, it keeps track of its location on the
* board (rank, file) and the type of piece it is. It is very straightforward so
* the methods are not commented
*
* @author Luis Edgardo Argote Bolio
* @see http://argote.mx/
*/
class Piece {
private char type;
private int rank;
private int file;
public Piece(char type, int rank, int file) {
this.type = type;
this.rank = rank;
this.file = file;
}
public char getType() {
return type;
}
public void setType(char type) {
this.type = type;
}
public int getRank() {
return rank;
}
public void setRank(int rank) {
this.rank = rank;
}
public int getFile() {
return file;
}
public void setFile(int file) {
this.file = file;
}
}