Tuesday, July 26, 2016

TCS Mock Code vita-1(Season-5) program-5

Problem : FEN Processor

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 at
 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.
 
Description: https://www.tcscodevita.com/CodevitaV5/images/cv15R2_R1P2_fig1.png 
                    
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
 


Description: https://www.tcscodevita.com/CodevitaV5/images/cv15R2_R1P2_fig2.png 
                    
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
 
Description: https://www.tcscodevita.com/CodevitaV5/images/cv15R2_R1P2_fig3.png  Description: https://www.tcscodevita.com/CodevitaV5/images/cv15R2_R1P2_fig4.png  Description: https://www.tcscodevita.com/CodevitaV5/images/cv15R2_R1P2_fig5.png                     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 construct a move list in
 standard algebraic formatfrom these FENs. For e.g. the five FENs depicted above will show the following move list 
1) e4 e5
2) f4 exf4
 

You will also have to print the total (White + Black) number of captures that have happened in the game.
 

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 a 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

Output Format: 
1.      Each line of output should correspond to a tuple <Move number, White's move, Black's move>
2.      Move Number is the move number followed by ')'
3.      White's move is move played by white, denoted in Algebraic notation
4.      Black's move is move played by black, denoted in Algebraic notation
5.      All parts of the tuple should be printed using a single space character as delimiter
6.      A capture must be denoted by x. See example output how a move representing a capture is printed.
7.      Print the entire Move List represented by input FENs
8.      At the end of the Move List, the output must print Number of Captures : <n>, where n corresponds to total number of captures by White and Black together.
9.      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. 

Description: https://www.tcscodevita.com/CodevitaV5/images/cv15R2_R1P2_fig6.png 
                    
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.
Input
Output
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/4PP2/8/PPPP2PP/RNBQKBNR
rnbqkbnr/pppp1ppp/8/8/4Pp2/8/PPPP2PP/RNBQKBNR
-1

1) e4 e5
2) f4 exf4
Number of Captures : 1
2

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
-1

1) e4 e5
2) Nf3 Nf6
3) Nxe5 d6
4) Nf3
Number of Captures : 1