Last Updated: 24 Dec, 2020
Constellation
Easy
Asked in company
Given a matrix ‘UNIVERSE’ with 3 rows and ‘N’ columns, with the characters { # , * , . } and these characters represent a cluster of stars and galaxies in space. Stars are represented by ‘*’ symbol. The ‘.’ symbol represents empty space.
We define a constellation as a 3x3 matrix which contains stars in the shape of vowels. A group of constellations is defined as a galaxy. Note that a galaxy may contain many stars but they will never be overlapping. Two galaxies are separated by a column of ‘#’.
Given the ‘UNIVERSE’ matrix, print a string which denotes all the vowels formed by stars and ‘#’ present in the matrix.
A looks like this :
. * .
* * *
* . *
E looks like this :
* * *
* * *
* * *
I looks like this :
* * *
. * .
* * *
O looks like this :
* * *
* . *
* * *
U looks like this :
* . *
* . *
* * *
Note :
It is guaranteed that no two constellations are overlapping.
Input format :
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of each test case contains a single integer ‘N’ denoting the number of columns in the matrix.
The next 3 lines of each test case denote the matrix of size 3 rows and ‘N’ columns which denotes the stars and the galaxies. Each line contains ‘N’ space separated characters from the set { ‘#’ , ’*’ , ’.’ }.
Output format :
For each test case, print a string which contains the shape of vowels and the hashes.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 50
3 <= N <= 10^5
Time Limit: 1 sec
Approaches
The key idea is to recursively check every 3x3 grid and see what vowel does it signify and it to the string. This can be easily done using a recursive function.
Here is the algorithm :
- We take a recursive function ‘generateConstellations()’ and take parameters, ‘CURIDX’, which denotes the current column we are at, a matrix ‘UNIVERSE’ to denote the stars and constellations.
- We define ‘MAT’ as submatrix of size 3x3 of the matrix ‘UNIVERSE’.
- We append the string ‘STR’ with the following conditions.
- If it is an ‘A’ the MAT[0][1], MAT[1][0], MAT[1][1], MAT[1][2], MAT[2][0] and MAT[2][2] will be stars.
- If it is an ‘E’ all elements of the matrix will be stars.
- If it is an ‘I’ all elements except MAT[1][0] and MAT[1][2] will be stars
- If it is an ‘O’ all elements except MAT[1][1] will be stars
- If it is an ‘U’ all elements except MAT[0][1] and MAT[1][1] will be stars.
- If it is a ‘#’ all 3 rows of that column will be ‘#” and we append ‘#’ to our string ‘STR’.
- Check every 3x3 matrix at a time and add the vowel formed to the resultant string ‘STR’.
- The base case will be once we have traversed the whole string i.e ‘CURIDX’ is greater than equal to N-2.
- Finally, when the whole matrix is traversed, return ‘STR’.
The key idea is to just check every 3x3 grid and see what vowel does it signify and it to the string. This can be easily done iterating through the matrix with the help of a loop.
Here is the algorithm :
- Take an index (say, ‘i’) and check if the 3x3 is any vowel.
- Let MAT[i][j] denote element in ‘i'th row and ‘j’th column in a 3x3 matrix.
- If it is an ‘A’ the MAT[0][1], MAT[1][0], MAT[1][1], MAT[1][2], MAT[2][0] and MAT[2][2] will be stars.
- If it is an ‘E’ all elements of the matrix will be stars.
- If it is an ‘I’ all elements except MAT[1][0] and MAT[1][2] will be stars
- If it is an ‘O’ all elements except MAT[1][1] will be stars
- If it is an ‘U’ all elements except MAT[0][1] and MAT[1][1] will be stars.
- If it is a ‘#’ all 3 rows of that column will be ‘#” and we append ‘#’ to our string ‘STR’.
- Check every 3x3 matrix at a time and add the vowel formed to the resultant string ‘STR’.
- Finally, when the whole matrix is traversed, return ‘STR’.