Programming Geek
Rated 4.1/5 based on 446 reviews

TCS CodeVita 2015 Round 2 : Find Captures

Problem : Find Captures
Background

A Chess board position is accurately captured by Forsyth-Edwards notation and is abbreviated as FEN. A FEN "record" defines a particular game position, all in one text line and using only the ASCII character set. A FEN record contains six fields. A complete description of the FEN format to represent Chess positions can be found here

For the purpose of this problem only consider first of the six fields of FEN. Before we describe the problem, let us look at how FEN maps to a board position. The following 5 images show board positions and its corresponding FEN representation.

                    Figure 1.




This board position depicts initial position before any side has made a move. In FEN format this board position is represented as


rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR
















Let's say, White plays e4. Then the board position looks like shown below 


                    Figure 2.




This board position depicts the Chess board after White has played e4. In FEN format this board position is represented as


rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR
















Similarly, 3 more half-moves are depicted in following diagrams 

                         Figure 3.                                                  Figure 4.                                                      Figure 5.


The FENs corresponding to Figure 3, 4 and 5 are represented as 

           3. rnbqkbnr/pppp1ppp/8/4p3/4P3/8/PPPP1PPP/RNBQKBNR
           4. rnbqkbnr/pppp1ppp/8/4p3/4PP2/8/PPPP2PP/RNBQKBNR
           5. rnbqkbnr/pppp1ppp/8/8/4Pp2/8/PPPP2PP/RNBQKBNR 

Wikipedia describes first field of FEN format as follows 

Piece placement (from white's perspective). Each rank is described, starting with rank 8 and ending with rank 1; within each rank, the contents of each square are described from file "a" through file "h". Following the Standard Algebraic Notation (SAN), each piece is identified by a single letter taken from the standard English names (pawn = "P", knight = "N", bishop = "B", rook = "R", queen = "Q" and king = "K").[1] White pieces are designated using upper-case letters ("PNBRQK") while black pieces use lowercase ("pnbrqk"). Empty squares are noted using digits 1 through 8 (the number of empty squares), and "/" separates ranks 

Statement 

You will be given FENs of successive board positions. Your task is to find the number of captures in the game and then break it down into number of captures by White and Black respectively. You also have to print the move number and the move on which each side makes the capture. See example output to get better understanding. 

For e.g. the five FENs depicted above, corresponds to the following move list in the game. 

1) e4 e5
2) f4 exf4 

The output of processing these FENs will thus be 

Number of Captures in the game : 1
Captures By White : []
Captures By Black : [2) .. exf4] 

Sections below describe the Input and Output specifications followed by examples. Input has to be read from console and output has to be written back to console. 

Input Format:
  1. Each input will correspond to one game only i.e. all successive FEN inputs will represent successive board positions that are a part of the same game.
  2. Each input will begin with FEN corresponding to Initial Position in chess as depicted in Fig 1.
  3. One line will contain only one FEN record
  4. There can be arbitrary number of FEN records provided as input
  5. Input will be terminated by -1
  6. See example inputs for better understanding

Output Format:
  1. First line of the output must print Number of Captures in the game : , where n corresponds to total number of captures by White and Black together
  2. Next two lines should print captures by White and Black respectively, one on each line
  3. The format of printing these two lines is Captures By : [Move List] where colour will be {White | Black}
  4. Move List must be enclosed in square brackets.
    1. If there are no captures by a side, then Move List should be empty denoted by []
    2. If the Move List is non-empty, then print the formats for printing captures by White and Black are as follows
      • Capture by White should be tuples delimited by ',' where tuple comprises on , where move number should be suffixed by ')' e.g. [4) cxd5, 6) bxc3]
      • Capture by Black should be tuples delimited by ',' where tuple comprises on , where move number should be suffixed by ')' e.g. [4) .. Nxd5, 5) .. Nxc3]. The '.. ' represents a placeholder for White's move
      • In case, number of captures is exactly 1, print only respective tuples (without ',')
  5. See example outputs for better understanding

Constraints:
  1. A check in algebraic notation is depicted by '+' symbol. We don't expect checks to be detected. Hence the output should be printed without '+' symbol. Ditto for double checks.
  2. Similarly, a check mate is usually denoted by #. We don't expect check mate to be detected. Hence the output should be printed without '#' symbol.
  3. Similarly, castling is usually denoted by o-o (short castle) or o-o-o (long castle). We don't expect castling to be detected. Hence our test cases don't contain FENs which give rise to such positions.
  4. Algebraic notation provides a way to disambiguate a move. We don't expect disambiguation to be implemented. Hence we have ensured test cases don't have ambiguous move. The following diagram explains the ambiguity and the corresponding disambiguation method.

                        Figure 6.


    The next move by White in this position is Nd2. Now both Knights can move to d2 square. Hence this move is ambiguous until it is explicitly expressed which knight has moved to d2.


    The algebraic notation solves this problem by writing the move as
    Nbd2 - if knight on b-file has moved to d2 or
    Nfd2 - if knight on f-file has moved to d2

    Generating a move list which can disambiguate move based on FENs is not expected. Hence our test cases don't contain FENs which give rise to such positions.


















  5. There is no need to handle En Passant positions. There are no test cases involving En Passant moves.

Sample Input and Output

SNo.InputOutput
1
rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR
rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR
rnbqkbnr/pppp1ppp/8/4p3/4P3/8/PPPP1PPP/RNBQKBNR
rnbqkbnr/pppp1ppp/8/4p3/4P3/5N2/PPPP1PPP/RNBQKB1R
r1bqkbnr/pppp1ppp/2n5/4p3/4P3/5N2/PPPP1PPP/RNBQKB1R
r1bqkbnr/pppp1ppp/2n5/4p3/2B1P3/5N2/PPPP1PPP/RNBQK2R
r1bqk1nr/pppp1ppp/2n5/2b1p3/2B1P3/5N2/PPPP1PPP/RNBQK2R
r1bqk1nr/pppp1ppp/2n5/2b1p3/1PB1P3/5N2/P1PP1PPP/RNBQK2R
r1bqk1nr/pppp1ppp/2n5/4p3/1bB1P3/5N2/P1PP1PPP/RNBQK2R
r1bqk1nr/pppp1ppp/2n5/4p3/1bB1P3/2P2N2/P2P1PPP/RNBQK2R
r1bqk1nr/pppp1ppp/2n5/b3p3/2B1P3/2P2N2/P2P1PPP/RNBQK2R
r1bqk1nr/pppp1ppp/2n5/b3p3/2BPP3/2P2N2/P4PPP/RNBQK2R
r1bqk1nr/pppp1ppp/2n5/b7/2BpP3/2P2N2/P4PPP/RNBQK2R
r1bqk1nr/pppp1ppp/2n5/b7/2BpP3/2P2N2/P4PPP/RNBQ1RK1
r1bqk1nr/pppp1ppp/2n5/b7/2B1P3/2Pp1N2/P4PPP/RNBQ1RK1
r1bqk1nr/pppp1ppp/2n5/b7/2B1P3/1QPp1N2/P4PPP/RNB2RK1
r1b1k1nr/pppp1ppp/2n2q2/b7/2B1P3/1QPp1N2/P4PPP/RNB2RK1
r1b1k1nr/pppp1ppp/2n2q2/b3P3/2B5/1QPp1N2/P4PPP/RNB2RK1
r1b1k1nr/pppp1ppp/2n3q1/b3P3/2B5/1QPp1N2/P4PPP/RNB2RK1
-1

Number of Captures in the game : 2
Captures By White : []
Captures By Black : [4) .. Bxb4, 6) .. exd4] 
2
rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR
rnbqkbnr/pppppppp/8/8/3P4/8/PPP1PPPP/RNBQKBNR
rnbqkb1r/pppppppp/5n2/8/3P4/8/PPP1PPPP/RNBQKBNR
rnbqkb1r/pppppppp/5n2/8/2PP4/8/PP2PPPP/RNBQKBNR
rnbqkb1r/pppppp1p/5np1/8/2PP4/8/PP2PPPP/RNBQKBNR
rnbqkb1r/pppppp1p/5np1/8/2PP4/2N5/PP2PPPP/R1BQKBNR
rnbqkb1r/ppp1pp1p/5np1/3p4/2PP4/2N5/PP2PPPP/R1BQKBNR
rnbqkb1r/ppp1pp1p/5np1/3P4/3P4/2N5/PP2PPPP/R1BQKBNR
rnbqkb1r/ppp1pp1p/6p1/3n4/3P4/2N5/PP2PPPP/R1BQKBNR
rnbqkb1r/ppp1pp1p/6p1/3n4/3PP3/2N5/PP3PPP/R1BQKBNR
rnbqkb1r/ppp1pp1p/6p1/8/3PP3/2n5/PP3PPP/R1BQKBNR
rnbqkb1r/ppp1pp1p/6p1/8/3PP3/2P5/P4PPP/R1BQKBNR
rnbqk2r/ppp1ppbp/6p1/8/3PP3/2P5/P4PPP/R1BQKBNR
rnbqk2r/ppp1ppbp/6p1/8/3PP3/2P2N2/P4PPP/R1BQKB1R
rnbqk2r/pp2ppbp/6p1/2p5/3PP3/2P2N2/P4PPP/R1BQKB1R
rnbqk2r/pp2ppbp/6p1/2p5/3PP3/2P2N2/P4PPP/1RBQKB1R
rnb1k2r/pp2ppbp/6p1/q1p5/3PP3/2P2N2/P4PPP/1RBQKB1R
-1

Number of Captures in the game : 4
Captures By White : [4) cxd5, 6) bxc3]
Captures By Black : [4) .. Nxd5, 5) .. Nxc3]
3
rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR
rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR
rnbqkbnr/pppp1ppp/8/4p3/4P3/8/PPPP1PPP/RNBQKBNR
rnbqkbnr/pppp1ppp/8/4p3/4P3/5N2/PPPP1PPP/RNBQKB1R
rnbqkb1r/pppp1ppp/5n2/4p3/4P3/5N2/PPPP1PPP/RNBQKB1R
rnbqkb1r/pppp1ppp/5n2/4N3/4P3/8/PPPP1PPP/RNBQKB1R
rnbqkb1r/ppp2ppp/3p1n2/4N3/4P3/8/PPPP1PPP/RNBQKB1R
rnbqkb1r/ppp2ppp/3p1n2/8/4P3/5N2/PPPP1PPP/RNBQKB1R
rnbqkb1r/ppp2ppp/3p4/8/4n3/5N2/PPPP1PPP/RNBQKB1R
-1

Number of Captures in the game : 2
Captures By White : [3) Nxe5]
Captures By Black : [4) .. Nxe4]
Note:

Please do not use package and namespace in your code. For object oriented languages your code should be written in one class.
Note:

Participants submitting solutions in C language should not use functions from / as these files do not exist in gcc
Note:

For C and C++, return type of main() function should be int.