Programming Geek
Rated 4.1/5 based on 446 reviews

CodeVita 2016 Round 2 Question: Mate In Two

Problem : Mate In Two


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.



                    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

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 2 moves.


Input Format:
  1. First line contains single FEN record, which corresponds to a particular board position


Output Format:
  1. The output must be printed as follows
    1. A string in format by "< move format >-< move format >-< move format >", where first move is white move, second is black move and third is again a white move
    2. Where < move format > is move represented in format "fromSquaretoSquare"
  2. See Example section for better understanding of output format


Constraints:
  1. The board position will always be White to move and mate in 2
  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 is exactly one forced mating sequence in our test cases. So once a forced mating sequence is found, there is no need to process further.


Sample Input and Output

SNo.InputOutput
1
r1b2rk1/1p4pR/p2pppn1/6q1/3NP1P1/2N2P2/PPP4Q/1K5R

h7g7-g8g7-h2h7
2
5r1k/p4p1p/5P1N/1p1p4/2pP3P/8/PP4RK/8

g2g8-f8g8-h6f7


Explanation:

Board position for sample input 1: 


                    Figure 6.

Mate enforcing moves for input 1: 


                    Figure 7.

Board position for sample input 2:                           


                    Figure 8.
Mate enforcing moves for input 2: 


                    Figure 9.





CodeVita 2016 Round 2 Question: Decrypt the Crypt

Problem : Decrypt the Crypt


Statement

Walter uses multiple applications at his workplace. He was assigned a unique password of variable lengths for each application (maximum length being 10). The only common factor among them was that all the passwords were a combination of 10 distinct characters. Walter created an algorithm to encrypt these passwords and wrote the codes on his desk to avoid a situation in which he would not be able to recollect a password.

Given as an input, is an encoded password and a list of 10 unique characters. Write a program that obtains the password by reverting the algorithm used by Walter.

Algorithm used by Walter to encode his password is as follows:
  1. Walter observes all his passwords and lists down every distinct character. He assigns an index value to each character from 0 to 9. (Note: This list will be provided as an input to the program). This list MUST contain 10 DISTINCT characters.
  2. He then replaces every character in the password with the corresponding index value to convert the password to a 10 digit numeric value.
  3. The leftmost digit in this number sequence is noted; let's say 'A'. Now, starting from the leftmost position, every digit in the number is added to the digit on its right. The last digit in the sequence is added to 'A'.
  4. Step 3 provides new sequences of numbers. He then scans through each of the summations and if any of the summation results in a value greater than 9, it is subtracted by 10, and its position is noted (Say B).
  5. He then lists every digit from 0 to 9 separated by '|' character and prepends each digit with its position in the sequence as noted in 'B'. The resulting sequence after this step is saved (Say C).
  6. The encoded password would therefore be
    < value_of_C >||< contents_of_array_B  > < Value_of_A >

Decrypt the encrypted password that has been created by Walter using the above algorithm to compute the actual password! 

Print -1 if there is any error in the inputs. 

Input Format:
  1. First line contains the encoded password as it should be according to Walter's algorithm
  2. Second line contains 10 unique characters

Output Format:

Obtained password by reverting the algorithm. Print -1 if there is any error in the inputs.
Constraints: 
  1. Second line of input MUST contain 10 DISTINCT characters.
  2. Encoded password should be in format
    < value_of_C >|| < contents_of_array_B >

Sample Input and Output

SNo.InputOutput
1
0|1|2|43|14|5|6|7|308|29||0149
*Acf$Zd&T@ 

@@Z$$ 
2
0|1|2|43|14|5|6|7|308|29||0149
*Acf$Zd&T 

-1



Explanation of Test Case 1:

NOTE: - The following are the steps used to encrypt the password. Your task is to reverse the logic and decrypt the encrypted string provided as input, and get back the clear-text password.
  1. Consider input characters and its position

    Input character list:*Acf$Zd&T@
    Position:0 1 2 3 4 5 6 7 8 9

    (Note: The character list will not contain more than 10 characters and each character must be unique)
  2. Now replace the characters in the password with the position value of the respective character as defined in step 1, to convert the password into a numeric value.

    Password:@@Z$$
    Numeric value:9 9 5 4 4

    (Note: Remember leftmost value (Say A) = 9)
  3. Starting from the left most position, add each digit to the digit on its right. Add the last digit with the first digit in the sequence

    Numeric value of password
    Addition
    :
    :
    9 9 5  4  4  
     18 14  9 8 13

  4. For each addition result equal to or greater than 10, subtract it by 10 and note its position.

    Additive step output
    Selective subtraction
    Numeric value
    :
    :
    :
    18 14 13
    84983
    01  4

    (Note: Remember the selective subtraction step positions obtained (Say B) = 014)
  5. The password will follow the following format

    Format:0|1|2|3|4|5|6|7|8|9
  6. Now, each number in this format is pre-appended with the positions of the occurrence of the respective number in the output obtained in selective subtraction step of Step 4.

    Encrypted password:0|1|2|43|14|5|6|7|038|29

    (Note: Say C = 0|1|2|43|14|5|6|7|038|29)
  7. The final encrypted password will be of the following format to account for the calculations performed in generating the encrypted password

    Encrypted password (format):< C >||< B >< A >
    Encrypted password:0|1|2|43|14|5|6|7|308|29||0149

Explanation of Test Case 2:

Second line of input contains 9 characters only hence prints -1


CodeVita 2016 Round 2 Question: Crack the Password

Problem : Crack the Password


Statement

Atul does lots of online transactions and has accounts in multiple banks, but to remember his passwords he created his own encryption technique and wrote down the enciphered passwords in a notepad. But he finds it very time consuming to decipher those passwords so he has asked for your help to develop a program to do the task quickly.

The approach he takes to encipher is,
  1. First he writes down his password in a square matrix P of dimension N, sequentially from the first element (see example for better explanation). He chooses N such that N^2 is the least number above the length of the password. He then starts filling the matrix row-wise from top to bottom. If any matrix element remains blank, he fills all those blanks with the last element e.g. if the last element filled is z then he fills all other remaining elements in the matrix by z .
  2. Then he creates new matrix A of the same dimensions such that every A(i,j) = P(j,i). Next he assigns the value of the alphabet in the password to that corresponding element in the matrix. So 'a' is substituted by 1, 'b' by 2, so on. Alphabets are only lower case. Also passwords contain characters from a to z only.
  3. Then he finds another matrix B such that, the solution to the following equation gives a matrix with all the elements of principal diagonal as 1 and rest as 0, which is also called the eMat( encrypted matrix ) .

Your are provided with the eMat (encrypted matrix) or the matrix B, your task is to find all possible passwords and print them. 

Example:
Let the password be "passwords" as it has 9 characters , the most appropriate matrix will be a 3X3 matrix, hence the matrix will be 

After Step 1: 

 


After step 2: 

 


After step 3: 

The eMat for the given matrix will be 

-0.783783783780.189189189190.70270270270
-0.118503118500.079002079000.09563409563
0.87733887734-0.25155925156-0.72557172557


Input Format:
  1. First line contains integer N, which is the dimension of square matrix eMat
  2. Next N lines contain N space separated values (11-digit precision after decimal point) representing the eMat.


Output Format:


In a single line print the password, if multiple password values are possible print them separated by space, sorted by ascending order of their lengths.
Constraints:

  1. When eMat is converted to Matrix A, round off the numbers in the matrix A to its nearest integer value to recover the alphabets in the password


Sample Input and Output

SNo.InputOutput

1

3
-0.78378378378 0.18918918919 0.70270270270
-0.11850311850 0.07900207900 0.09563409563
0.87733887734 -0.25155925156 -0.72557172557 

passwords

2

2
0.06666666667 -0.06666666667
-0.00350877193 0.05614035088 

pas pass


CodeVita 2016 Round 2 Question: Verify JSON Object validity

Problem : Verify JSON Object validity


Statement

A JSON object is a key-value pair data structure that is enclosed within { }. A sample JSON object would look like
{
"key1":"value1",
"key2":"value2",
"key3": {
"key4":"value4",
"key5":"value5"}
"key6":"value6",
"key7":[
{
"key8":"value8"
}]
}

Given a JSON object, ignore the literal values of the object and check whether the distinguishing characters and notation of the object are valid to determine if the JSON object is valid or not.

Note:
  1. Key3 points to another JSON object (Concept of nesting of JSON objects).
  2. Key7 points to an array of JSON objects.
You may wish to refer site1 to get a more formal description of JSON grammar. site2,site3; are also good resources to understand JSON specifications. 

Input Format:
  1. First line contains a pattern of JSON without any literal

Output Format:

Print 1 if pattern is valid, -1 otherwise.
Constraints:
  1. A JSON object should start with '{' and ends with a '}'.
  2. The key and value should be separated by a ':'.
  3. A ',' suggests an additional JSON property.
  4. An array only consists of JSON objects. It cannot contain a "key":"value" pair by itself.

Example 1:

Input
{:[{},{}]}

Output
1

Explanation
{
"Key": [{
"Key": "Value"
}, {
"Key": "Value"
}]
}
Pattern is following all constraints hence prints 1
Example 2:

Input
{:{[]},{}}

Output
-1

Explanation
Convert this pattern in a JSON Object

{
"Key": {
[
"Key": "Value"
]
},
{
"Key": "Value"
}
}

Constraint 4 "An array only consists of JSON objects. It cannot contain a "key":"value" pair by itself." not followed here, so it's a invalid pattern, hence prints -1




CodeVita 2016 Round 2 Question: The Mystery of Sky

Problem : The Mystery of Sky


Statement

Stark is a 10 year old kid and he loves stars. So, he decided every day he will capture a picture of a sky. After doing this for many days he found very interesting observations.

Every day the total number of stars in the sky is same as days completed for a calendar year. He noticed, on Saturday's and Sunday's that there are no stars in the sky. Stark's camera does not have wide angle capture feature so he could only capture maximum of 50 stars at a time. So, he assumed that there are only 50 stars in the sky that day. Also, the camera discharges every 4th day and he is not be able to click any picture that day. So let's say, if the first day of calendar (01/01/0001) starts on a Monday then on Thursday he can't click any pictures. Then resuming on Friday he can take pictures until Sunday, but can't take picture on Monday, followed by downtime on Friday, then Tuesday, then Saturday etc. When the camera discharges he considers 0 stars that day.

You are his programmer friend and want to help him. You need to write a code which will tell him on a particular date how many stars Stark's camera was able to click.

You can assume Stark has an ancient camera and your first input will be the day for date (01/01/0001) and then followed by any date on which Stark wants to find out the number of stars in the sky.
Input Format:

Every line of input will contain a Day at date 01/01/0001 in dd/mm/yyyy format followed by a Date in the same format (on which we have to count the stars)
Output Format:
For valid Input
Count of the number of stars in the sky on the given date

For Invalid Input
Print "Invalid Date" for invalid date

Print "Invalid Day" for invalid day


Sample Input and Output

SNo.InputOutputExplanation
1
Monday
30/02/1990

Invalid Date

2
Thursday

Invalid Day 

3
Wednesday
24/01/2056 

24

Its 24th day of the year and neither is Saturday/Sunday nor has the camera discharged on this day.

CodeVita 2016 Round 2 Question: Collecting Candies

Problem : Collecting Candies


Statement

Krishna loves candies a lot, so whenever he gets them, he stores them so that he can eat them later whenever he wants to.

He has recently received N boxes of candies each containing Ci candies where Ci represents the total number of candies in the ith box. Krishna wants to store them in a single box. The only constraint is that he can choose any two boxes and store their joint contents in an empty box only. Assume that there are infinite number of empty boxes available.

At a time he can pick up any two boxes for transferring and if both the boxes say contain X and Y number of candies respectively, then it takes him exactly X+Y seconds of time. As he is to eager to collect all of them he has approached you to tell him the minimum time in which all the candies can be collected.
Input Format:
  1. First line of input is number of test case T
  2. Each test case is comprised of two inputs
    1. First input of a test case is the number of boxes N
    2. Second input is N integers delimited by whitespace denoting number of candies in each box

Output Format:

Print minimum time required, in seconds, for each of the test case. Print each output on a new line.
Constraints:
  1. 1 ≤T≤10
  2. 1 ≤N≤ 10000
  3. 1 ≤ [Candies in each box] ≤ 100009

Sample Input and Output

SNo.InputOutputExplanation

1

1
4
1 2 3 4

19

4 boxes, each containing 1, 2, 3 and 4 candies respectively.
Adding 1 + 2 in a new box takes 3 seconds
Adding 3 + 3 in a new box takes 6 seconds
Adding 4 + 6 in a new box takes 10 seconds
Hence total time taken is 19 seconds. There could be other combinations also, but overall time does not go below 19 seconds.

2

1
5
1 2 3 4 5

33

5 boxes, each containing 1, 2, 3, 4 and 5 candies respectively.
Adding 1 + 2 in a new box takes 3 seconds
Adding 3 + 3 in a new box takes 6 seconds
Adding 4 + 5 in a new box takes 9 seconds
Adding 6 + 9 in a new box takes 15 seconds
Hence total time taken is 33 seconds. There could be other combinations also, but overall time does not go below 33 seconds.