Sunday, July 31, 2016

TCS Code Vita Season-5 Round-1 set-1 Program-5

Problem : Mate In One
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 line of text and using only the ASCII character set. A FEN record consists of 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. 
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 

Given a board position in FEN format, your task is to find out all move(s) that lead to a forced mate. White to play and win in 1 move. 


Input Format: 
1.    First line contains single FEN record, which corresponds to a particular board position
2.    Second line contains -1 which indicates the end of input


Output Format: 
1.    The output must be printed as follows 
a.     A string "Mating moves " followed by "[<move format>]"
b.    Where <move format> is move represented in format "[Piece][fromSquare]-[Piece][toSquare]"
c.     If a mating move involves a capture then represent it as "[Piece][fromSquare]-[Piece]x[toSquare]"
d.    If the Piece inflicting a mate is a pawn represent it only as [fromSquare]-[toSquare]
e.    If there is more than one mating move, then follow the rules given below 
                                      i.        Moves must be sorted alphabetically according to their ascii values
                                     ii.        Two moves must be separated by a comma followed by a white space characters
                                    iii.        Between the last move and terminating "]" character there should be no space or comma
2.    See Example section for better understanding of output format


Constraints:
1.    The board position will always be White to move and mate in 1
2.    Since we focus on only first part of the FEN, we are essentially ignoring possibility of Castling being a mating move. Hence our test cases don't contain FENs which give rise to such positions.
3.    There is no need to handle En Passant positions. There are no test cases involving En Passant moves.
4.    No need to implement pawn promotion rules. Our test cases do not contain positions which will lead to a pawn getting promoted and inflicting a mate.
5.    There are no test cases in which capture by a white pawn leads to a mate.


Sample Input and Output
SNo.
Input
Output
1

3k4/8/3p4/7B/3Q4/2R1R3/8/5K2
-1

Mating moves [Qd4-Qxd6]
2

8/R7/3k4/8/2Q1P1B1/8/8/2K1R3
-1

Mating moves [Qc4-Qc7, Qc4-Qd5, e4-e5]

Explanation: 

Board position for sample input 1: 

Description: https://www.tcscodevita.com/CodevitaV5/images/cv15ph2r1_R1P7_fig6.jpg 
                    Figure 6.
Board position for sample input 2: 

Description: https://www.tcscodevita.com/CodevitaV5/images/cv15ph2r1_R1P7_fig7.jpg 
                    Figure 7.

Contact Geek Placement Preparation

Name

Email *

Message *