Sunday, July 31, 2016

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

3D Maze problem

Suppose, an ant is trapped in a maze, with only one way in and one way out.

The maze is a cubic-lattice like structure of dimension NxNxN (Length=Breadth=Height=N). The way in is the left-bottom most point, and the way out is the right top-most point (along the principal diagonal). The below picture shows the maze for N=2. 



        
Figure 1. 
Assuming the ant only moves right, forward or upwards along the grids of the maze, calculate the total number of ways in which the ant can escape. Mathematically right, forward and upwards are defined at positive changes in co-ordinates on x, y and z axes respectively. 

Example:
For, N=1, the grid structure and solution is shown below: 




        
Figure 2. 


Thus, for N=1, we have a net of 6 ways. 


Input Format:

Single integer N 
Output Format:

Output also consists of a single number corresponding to the number of ways the ant can escape the maze.
Constraints:
  • 0<N<=8

Example
Example Number
Sample Input
Sample Output
1
1

6
2
2

90













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

Problem : Pivot Table
According to Wikipedia, a Pivot Table is a useful summarization tool in data processing. Your task is to implement a Pivot tableaccording to given requirements

Requirements
1.    Must work against a data table of arbitrary sizes
2.    Data types to be supported are String and Numbers
3.    Must support the following aggregation functions - Sum, Count, Average, Invert (transpose)
4.    Must take inputs on which column to use as a Pivot and which column to use an aggregation function on
5.    The aggregated Pivot table must be sorted in ascending order
a.     For string data type, sorting function must sort rows, alphabetically
b.    For numeric data type, sorting function must sort rows from smallest to largest

We explain the aggregation functions using example for better understanding of the specifications Lets' say, the data is as follows 

A
B
C
D
Match1
Sachin
2
12.678
Match4
Rahul
23
14
Match5
Sonal
13
35.333
Match6
Rajiv
6
56.33
Match2
Manish
87
37
Match6
Nakul
34
45
Match2
Mukul
48
12.87
Match7
Srinath
24
29.625
Match1
Dora
83
51.667
Match8
James
79
59
Match4
Munna
45
53.333
Match6
Sachin
53
52.5
Match3
Sonal
21
58.93
Match2
Rajiv
69
61.5
Match7
Nakul
36
63.75
Match9
Mukul
96
56.222
Match5
Dora
43
51.714
Match3
Munna
80
49.417


Sum Function 

  • Can only be applied to Numeric columns i.e. C and D in this case
  • Let's say we are grouping on column B and applying Sum function on column C then, the output will look as follows :

    Dora 126
    James 79
    Manish 87
    Mukul 144
    Munna 125
    Nakul 70
    Rahul 23
    Rajiv 75
    Sachin 55
    Sonal 34
    Srinath 24


Count Function 

  • Let's say we are grouping on column A and applying Count function on column A then, the output will look as follows :

    Match1 2
    Match2 3
    Match3 2
    Match4 2
    Match5 2
    Match6 3
    Match7 2
    Match8 1
    Match9 1


Average Function 

  • Can only be applied to Numeric columns i.e. C and D in this case
  • Let's say we are grouping on column B and applying Average function on column D then, the output will look as follows :

    Dora 52
    James 59
    Manish 37
    Mukul 35
    Munna 52
    Nakul 55
    Rahul 14
    Rajiv 59
    Sachin 33
    Sonal 48
    Srinath 30


Invert Function 

  • Let's say we are grouping on column B and applying Invert function on column D then, the output will look as follows :

    Dora 51.667 # # # 51.714 # # # #
    James # # # # # # # 59 #
    Manish # 37 # # # # # # #
    Mukul # 12.87 # # # # # # 56.222
    Munna # # 49.417 53.333 # # # # #
    Nakul # # # # # 45 63.75 # #
    Rahul # # # 14 # # # # #
    Rajiv # 61.5 # # # 56.33 # # #
    Sachin 12.678 # # # # 52.5 # # #
    Sonal # # 58.93 # 35.333 # # # #
    Srinath # # # # # # 29.625 # #

The first column of output is column B in ascending order. The column A in the data table becomes column headers in the output (which is not printed in output). The non-hash values are values of column D for a combination of column A and column B in the original data table. Column A and column B combination in test cases for Invert function are unique. '#' character is a place holder for null values. 

Now that the workings of the four functions have been explained, let us understand the input and output specifications.


Input Format:

First line of input contains total number of test cases, denoted by N
Each test case comprises of 5 parts-
  • First line of a test case contains a function name (Sum , Average, Invert and Count)
  • Second line contains the column no. on which grouping will be applied.(Column index starts from 1)
  • Third line contains the column no. on which the aggregation function will be applied
  • Next variable number of lines contain the actual data delimited by space
  • A test case is terminated by -1


Output Format:

For each test case print the output of the appropriate function as explained above.
  • Perform rounding up when printing output for Sum and Average functions.
  • Do not perform rounding when printing output for Invert function.


Sample Input and Output
SNo.
Input
Output
1

4
Sum
2
3
idx 49.865 30.071 blkqt
ywhw 17.909 96.138 nqng
odb 69.900 34.593 hcf
-1

Count
3
2
79.424 bwipx eqmz 15.800
61.570 uhaci fifo 36.933
9.881 alt cjven 63.373
31.110 mpcq pdg 9.170
-1

Average
3
2
76.114 69.394 nuvr 1.992
80.233 5.676 kxf 2.783
1.940 85.761 zlnv 5.537
74.016 79.417 atp 89.162
-1
Invert
2
3
cky foq 57.193 80.148
mkf kjqs 15.449 43.623
ohu turnf 95.211 57.271
-1 

17.909 97
49.865 31
69.9 35

cjven 1
eqmz 1
fifo 1
pdg 1

atp 80
kxf 6
nuvr 70
zlnv 86

foq 57.193 # #
kjqs # 15.449 #
turnf # # 95.211 


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

Problem : Clockwise Bricks Breaker

Clockwise Bricks Breaker is a game where there is a ball which is used to break the block of bricks. Brick's Blocks are always in a form of a square matrix( e.g 2X2, 4X4). The ball has some characteristics like for breaking each brick from the block. It consumes 1 unit of energy and the whole setup is in a manner that the ball will break bricks always - in clock wise direction, in a ring fashion and start from top-left. Take an example of 4X4 brick block. 

        
Figure 1.



        
Figure 2. 




        
Figure 3. 
The numbers on the bricks are nothing but points gained by breaking that brick which is assigned row wise starting from 1 to NxN. The game gets over when energy of ball exhausts and once ball initiated with some energy it will only stop when all its energy exhaust. 

Your Task is to calculate total points (points of a block should be the positional value of that block as mentioned in the picture: You have to add points of all the broken bricks) gained by a player, where the energy of ball and size of block will be given. 


Input Format:

First line of input should be the number of test cases T

Next T lines contain two variables N and E delimited by a whitespace where, 
  • N =size of square block (i.e. block will be of NXN bricks)
  • E =Energy of ball



Output Format:

Output will be T lines containing the integer which is total number points gained by that energy. 
OR

Print "Invalid Input" if constraint fails 
Constraints:
  • 0< T<=10
  • 0< N <=200
  • 0<= E <=N*N 


Example
Example Number
Sample Input
Sample Output
Explaination
1
2
4 5
1 50

36
Invalid Input
For first test case as with Energy 5, the ball will break 5 bricks having points 1,4,16,13,2

So 1+4+16+13+2=36.
Second test case is Invalid Input because constraint E<=N*N not satisfied.
2
2
5 0
9 -3

0
Invalid Input
For first test case it is 0 as energy is zero.

For second test case it is Invalid Input because constraint E >= 0 not satisfied.


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

Problem : Even Sum
A number is even if it is divisible by 2, but in this case a number is even if the active bits (1s in its binary representation) of a given number are 2. So your task is to find the sum of first N even numbers. 
Input Format:

First line of the input contains an integer T denoting the number of test cases.

Each of the next T lines contains a single integer N. 
Output Format:

For each test case, print a single integer denoting sum of first N even numbers mod 1000000007. 
Constraints:
1.    0 < N <=10^5
Example:
Example Number
Sample Input
Sample Output
1

1
2

2

2
15
25

315
666







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

Problem : Knight Moves

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. 

                    
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 w
















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 b
















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 w
           4. rnbqkbnr/pppp1ppp/8/4p3/4PP2/8/PPPP2PP/RNBQKBNR b
           5. rnbqkbnr/pppp1ppp/8/8/4Pp2/8/PPPP2PP/RNBQKBNR w 

Wikipedia describes first field of FEN format as follows 

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. 

The second field denotes whose move it is now. "w" depicts that it is White's turn to play and "b" indicates that it is Black's turn to play 

CodeVita Problem Statement 

Given a board position in FEN format, your task is to find out all the move(s) that Knight(s) of the playing side can make. 


Input Format: 
1.    First line contains single FEN record, which corresponds to a particular board position and also indicates whose turn it is.


Output Format: 
1.    The output must be printed as follows
1.    All legal moves that Knight can make must be in the format "[<Move Format>]"
2.    Where <Move Format> is move represented in format "[fromSquare][toSquare]"
2.    See Example section for better understanding of output format
3.    Follow Output printing specification to print the output in required format


Sample Input and Output
SNo.
Input
Board Depiction
Output
1

3k4/8/8/8/8/1K4R1/5R2/7N w


[]
2

3k4/8/8/8/8/6b1/5r2/K6N w


[h1g3, h1f2]
3

2k1b3/6n1/n7/5R2/8/8/8/4K3 b


[g7e6, g7f5, g7h5, a6b8, a6c7, a6c5, a6b4]

Print Specification: 
  1. Should start with "[" and end with "]"
  2. If more than one move is possible, moves should be separated by a comma followed by whitespace
  3. Moves of a single bishop should be printed in Move Format. Scan the board from 8th rank to 1st rank from a-file to h-file. Whichever square gets hit first, that move should be printed first.
  4. If more than one bishop exists for side to move, then start scanning for bishop from 8th rank to 1st rank, left to right i.e. from a-file to h-file. Whichever bishop appears first, print all moves for that bishop first.
  5. Verify your understanding of how printing should happen against examples shown above