The Encryption Problem

The encryption scheme that is as follows:

He forms an X-cipher using ‘n’ no. of rows, where he starts writing the characters of his message from the top left corner of the X and goes diagonally downwards till he reaches the last row. Then continues from the bottom left of the X and goes diagonally upwards while skipping the cell which has been used already, till he reaches the top row. He then continues writing by forming another X whose top left corner is same as the top right corner of the previous X. Also, the bottom left corner of this X is same as the bottom right corner of the previous one. He also doesn’t omit any space while encrypting his message. In this way he keeps on encrypting his message by forming a series of joint Xs. For example: “CHOOSE BATTING FIRST” is encrypted as “CAFHBT IOTR OGISESNT” when no. of rows used is 5 using the following scheme:

After filling the matrix this way, print the non-empty cells row-wise.

“CHOOSE BATTING FIRST” is encrypted as “CBGTH AN SEOITRFSOTI” when no. of rows is 4 using the following scheme:

After filling the matrix this way, print the non-empty cells row-wise.

Input Format:

First line contains a single integer n representing the no. of encrypted sentences. This is followed by 2n lines where 2 lines are for one encrypted sentence. The first of these 2 lines will contain a single integer (pi) which denotes the no. of rows used to encrypt the message and the second line contains the encrypted message (si).

Output Format:

The output should contain n lines with the ith line showing the ith decrypted message.

Sample Input:

2

5

CAFHBT IOTR OGISESNT

4

CBGTH AN SEOITRFSOTI

Sample Output:

CHOOSE BATTING FIRST

CHOOSE BATTING FIRST

using System; using System.Collections.Generic; using System.Text; using System.Linq; namespace ConsoleApplication2 { class Program { static void Main(string[] args) { string originalMessage = "CHOOSE BATTING FIRST"; originalMessage = "BIT Mesra --> ORACLE --> MICROSOFT --> AMAZON"; int numberOfRows = 4; char[,] xcipher = new char[numberOfRows, DetermineNumberOfColumns(numberOfRows, originalMessage.Length)]; string encryptedMessage = Encrypt(xcipher, originalMessage); Console.WriteLine(encryptedMessage); xcipher = new char[numberOfRows, DetermineNumberOfColumns(numberOfRows, encryptedMessage.Length)]; Console.WriteLine(Decrypt(FillMatrix(MarkValidCells(xcipher, encryptedMessage.Length), encryptedMessage), encryptedMessage.Length)); } public static string Encrypt(char[,] xcipher, string originalMessage) { int row = 0, col = 0, direction = 0;//0 for main diagonal; 1 for off diagonal for (int i = 0; i < originalMessage.Length; i++) { if (direction == 0) { xcipher[row, col] = originalMessage[i]; row++; col++; if (row == xcipher.GetLength(0)) { direction = 1; row--; col = col - xcipher.GetLength(0); } } else { while (row >= 0) { if (xcipher[row, col] != '') { row--; col++; } else { break; } } if (row >= 0) { xcipher[row, col] = originalMessage[i]; row--; col++; } if (row < 0) { direction = 0; row = row + 2; } } } string encryptedMessage = ""; int count = 0; for (row = 0; row < xcipher.GetLength(0); row++) { for (col = 0; col < xcipher.GetLength(1); col++) { if (xcipher[row, col] != '') { encryptedMessage = encryptedMessage + xcipher[row, col]; count++; if (count == originalMessage.Length) { col = xcipher.GetLength(1); row = xcipher.GetLength(0); } } } } return encryptedMessage; } public static string Decrypt(char[,] xcipher, int strLength) { string decryptedMessage = ""; int row = 0, col = 0, direction = 0;//0 for main diagonal; 1 for off diagonal for (int i = 0; i < strLength; i++) { if (direction == 0) { decryptedMessage = decryptedMessage + xcipher[row, col]; xcipher[row, col] = ''; row++; col++; if (row == xcipher.GetLength(0)) { direction = 1; row--; col = col - xcipher.GetLength(0); } } else { while (row >= 0) { if (xcipher[row, col].Equals('')) { row--; col++; } else { break; } } if (row >= 0) { decryptedMessage = decryptedMessage + xcipher[row, col]; xcipher[row, col] = ''; row--; col++; } if (row < 0) { direction = 0; row = row + 2; } } } return decryptedMessage; } public static char[,] FillMatrix(char[,] xcipher, string encryptedMessage) { int count = 0; for (int row = 0; row < xcipher.GetLength(0); row++) { for (int col = 0; col < xcipher.GetLength(1); col++) { if (xcipher[row, col] == 'Y') { xcipher[row, col] = encryptedMessage[count]; count++; if (count == encryptedMessage.Length) { col = xcipher.GetLength(1); row = xcipher.GetLength(0); } } } } return xcipher; } public static char[,] MarkValidCells(char[,] xcipher, int strLength) { int row = 0, col = 0, direction = 0;//0 for main diagonal; 1 for off diagonal for (int i = 0; i < strLength; i++) { if (direction == 0) { xcipher[row, col] = 'Y'; row++; col++; if (row == xcipher.GetLength(0)) { direction = 1; row--; col = col - xcipher.GetLength(0); } } else { while (row >= 0) { if (xcipher[row, col] == 'Y') { row--; col++; } else { break; } } if (row >= 0) { xcipher[row, col] = 'Y'; row--; col++; } if(row < 0) { direction = 0; row = row + 2; } } } return xcipher; } public static int DetermineNumberOfColumns(int numberOfRows, int stringLength) { int numberOfColumns = 0; int tempColumnCount = 0; int flag = 0; bool firstX = true; for (int i = 0; i < stringLength; i++) { if (flag == 0) //main diagonal { tempColumnCount++; if (firstX) { if (tempColumnCount == numberOfRows) //switch for off diagonal { numberOfColumns = numberOfColumns + tempColumnCount; tempColumnCount = 0; flag = 1; } } else { if (tempColumnCount == numberOfRows - 1) //switch for off diagonal { numberOfColumns = numberOfColumns + tempColumnCount; tempColumnCount = 0; flag = 1; } } } else //off diagonal { flag++; if (firstX) { if (numberOfRows % 2 != 0) //Odd number of rows, element overlap { if (flag == numberOfRows) { flag = 0; firstX = false; } } else //Even number of rows, no overlap { if (flag == numberOfRows + 1) { flag = 0; firstX = false; } } } else { if (numberOfRows % 2 != 0) //Odd number of rows, element overlap { if (flag == numberOfRows - 1) { flag = 0; } } else //Even number of rows, no overlap { if (flag == numberOfRows) { flag = 0; } } } } } return (numberOfColumns + tempColumnCount); } } } Output: Br EMO>OIsa>OL ISF- ZNeT- CR>-OC-TAAM -A-R M BIT Mesra --> ORACLE --> MICROSOFT --> AMAZON Press any key to continue . . .