TCS CodeVita 9 ( Zone 1) 2020 | Constellation
Three characters {#, *, . } represents a constellation of stars and galaxies in space. Each galaxy is demarcated by # characters. There can be one or many stars in a given galaxy. Stars can only be in the shape of vowels {A, E, I, O, U}. A collection of * in the shape of the vowels is a star. A star is contained in a 3×3 block. Stars cannot be overlapping. The dot (.) character denotes empty space.
Given a matrix mat[][] of dimensions 3×N consisting of {#, *, .} character, the task is to find the galaxy and stars within them.
Examples:
Input: N = 18, mat[][] = {{* . * # * * * # * * * # * * * . * .}, {* . * # * . * # . * . # * * * * * *}, {* * * # * * * # * * * # * * * * . *}}
Output: U#O#I#EA
Explanation:
It can be seen that the stars make the image of the alphabets U, O, I, E and A respectively.Input: N = 12, mat[][] = {{* . * # . * * * # . * .}, {* . * # . . * . # * * *}, {* * * # . * * * # * . *}}
Output: U#I#A
Explanation:
It can be seen that the stars make the image of the alphabet U, I and A.
Approach: The idea is to traverse the matrix column-wise using the variable i from the range [0, N – 1] and check if the given arrangement of {#, *, . } forms a galaxy, an empty space, or a vowel. There arise the following cases:
- When all ‘#’ is encountered in the given column: In this case, print ‘#’ and continue traversing the matrix.
- When all ‘.’ is encountered in the given column: In this case, skip the current column and continue traversing the matrix.
- For all other cases check if the given arrangement of {#, *, .} forms a vowel, then print the vowel and update the column index i to (i + 3).
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to print the vowels(stars) // in order of their occurrence within // the given galaxy void printGalaxy( vector<vector< char > > mat, int n) { // Iterate the matrix column-wise for ( int i = 0; i < n; i++) { // If all '#' is encountered // in the given column, print '#' if (mat[0][i] == '#' && mat[1][i] == '#' && mat[2][i] == '#' ) { cout << '#' ; } // If all '.' is encountered in // the given column, skip the // current column else if (mat[0][i] == '.' && mat[1][i] == '.' && mat[2][i] == '.' ) { } // If above cases fail else { char a, b, c, a1, b1; char c1, a2, b2, c2; int x1 = i; a = mat[0][x1]; b = mat[0][x1 + 1]; c = mat[0][x1 + 2]; a1 = mat[1][x1]; b1 = mat[1][x1 + 1]; c1 = mat[1][x1 + 2]; a2 = mat[2][x1]; b2 = mat[2][x1 + 1]; c2 = mat[2][x1 + 2]; // Check if the arrangement // of '.' and '*' forms // character 'A' if (a == '.' && b == '*' && c == '.' && a1 == '*' && b1 == '*' && c1 == '*' && a2 == '*' && b2 == '.' && c2 == '*' ) { // If true, print A cout << "A" ; // Increment column number i = i + 2; } // Check if the arrangement // of '.' and '*' forms // character 'E' if (a == '*' && b == '*' && c == '*' && a1 == '*' && b1 == '*' && c1 == '*' && a2 == '*' && b2 == '*' && c2 == '*' ) { // If true, print E cout << "E" ; // Increment column number i = i + 2; } // Check if the arrangement // of '.' and '*' forms // character 'I' if (a == '*' && b == '*' && c == '*' && a1 == '.' && b1 == '*' && c1 == '.' && a2 == '*' && b2 == '*' && c2 == '*' ) { // If true, print I cout << "I" ; // Increment column number i = i + 2; } // Check if the arrangement // of '.' and '*' forms // character 'O' if (a == '*' && b == '*' && c == '*' && a1 == '*' && b1 == '.' && c1 == '*' && a2 == '*' && b2 == '*' && c2 == '*' ) { // If true, print O cout << "O" ; // Increment column number i = i + 2; } // Check if the arrangement // of '.' and '*' forms // character 'U' if (a == '*' && b == '.' && c == '*' && a1 == '*' && b1 == '.' && c1 == '*' && a2 == '*' && b2 == '*' && c2 == '*' ) { // If True, print U cout << "U" ; // Increment column number i = i + 2; } } } } // Driver Code int main() { // Given n, number of columns int N = 18; // Given matrix vector<vector< char > > mat = { { '*' , '.' , '*' , '#' , '*' , '*' , '*' , '#' , '*' , '*' , '*' , '#' , '*' , '*' , '*' , '.' , '*' , '.' }, { '*' , '.' , '*' , '#' , '*' , '.' , '*' , '#' , '.' , '*' , '.' , '#' , '*' , '*' , '*' , '*' , '*' , '*' }, { '*' , '*' , '*' , '#' , '*' , '*' , '*' , '#' , '*' , '*' , '*' , '#' , '*' , '*' , '*' , '*' , '.' , '*' } }; // Function Call printGalaxy(mat, N); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG { // Function to print the vowels(stars) // in order of their occurrence within // the given galaxy static void printGalaxy( char mat[][], int n) { // Iterate the matrix column-wise for ( int i = 0 ; i < n; i++) { // If all '#' is encountered // in the given column, print '#' if (mat[ 0 ][i] == '#' && mat[ 1 ][i] == '#' && mat[ 2 ][i] == '#' ) { System.out.print( '#' ); } // If all '.' is encountered in // the given column, skip the // current column else if (mat[ 0 ][i] == '.' && mat[ 1 ][i] == '.' && mat[ 2 ][i] == '.' ) { } // If above cases fail else { char a, b, c, a1, b1; char c1, a2, b2, c2; int x1 = i; a = mat[ 0 ][x1]; b = mat[ 0 ][x1 + 1 ]; c = mat[ 0 ][x1 + 2 ]; a1 = mat[ 1 ][x1]; b1 = mat[ 1 ][x1 + 1 ]; c1 = mat[ 1 ][x1 + 2 ]; a2 = mat[ 2 ][x1]; b2 = mat[ 2 ][x1 + 1 ]; c2 = mat[ 2 ][x1 + 2 ]; // Check if the arrangement // of '.' and '*' forms // character 'A' if (a == '.' && b == '*' && c == '.' && a1 == '*' && b1 == '*' && c1 == '*' && a2 == '*' && b2 == '.' && c2 == '*' ) { // If true, print A System.out.print( "A" ); // Increment column number i = i + 2 ; } // Check if the arrangement // of '.' and '*' forms // character 'E' if (a == '*' && b == '*' && c == '*' && a1 == '*' && b1 == '*' && c1 == '*' && a2 == '*' && b2 == '*' && c2 == '*' ) { // If true, print E System.out.print( "E" ); // Increment column number i = i + 2 ; } // Check if the arrangement // of '.' and '*' forms // character 'I' if (a == '*' && b == '*' && c == '*' && a1 == '.' && b1 == '*' && c1 == '.' && a2 == '*' && b2 == '*' && c2 == '*' ) { // If true, print I System.out.print( "I" ); // Increment column number i = i + 2 ; } // Check if the arrangement // of '.' and '*' forms // character 'O' if (a == '*' && b == '*' && c == '*' && a1 == '*' && b1 == '.' && c1 == '*' && a2 == '*' && b2 == '*' && c2 == '*' ) { // If true, print O System.out.print( "O" ); // Increment column number i = i + 2 ; } // Check if the arrangement // of '.' and '*' forms // character 'U' if (a == '*' && b == '.' && c == '*' && a1 == '*' && b1 == '.' && c1 == '*' && a2 == '*' && b2 == '*' && c2 == '*' ) { // If True, print U System.out.print( "U" ); // Increment column number i = i + 2 ; } } } } // Driver Code public static void main(String[] args) { // Given n, number of columns int N = 18 ; // Given matrix char mat[][] = { { '*' , '.' , '*' , '#' , '*' , '*' , '*' , '#' , '*' , '*' , '*' , '#' , '*' , '*' , '*' , '.' , '*' , '.' }, { '*' , '.' , '*' , '#' , '*' , '.' , '*' , '#' , '.' , '*' , '.' , '#' , '*' , '*' , '*' , '*' , '*' , '*' }, { '*' , '*' , '*' , '#' , '*' , '*' , '*' , '#' , '*' , '*' , '*' , '#' , '*' , '*' , '*' , '*' , '.' , '*' } }; // Function Call printGalaxy(mat, N); } } // This code is contributed by Potta Lokesh |
Python3
# Python program for the above approach # Function to print vowels(stars) # in order of their occurrence within # the given galaxy def printGalaxy(mat, n): # Iterate the matrix column-wise for i in range (n - 2 ): # If all '#' is encountered # in the given column, pr'#' if (mat[ 0 ][i] = = '#' and mat[ 1 ][i] = = '#' and mat[ 2 ][i] = = '#' ): print ( '#' ,end = ""); # If all '.' is encountered in # the given column, skip the # current column elif (mat[ 0 ][i] = = '.' and mat[ 1 ][i] = = '.' and mat[ 2 ][i] = = '.' ): p = 0 ; # If above cases fail else : x1 = i; a = mat[ 0 ][x1]; b = mat[ 0 ][x1 + 1 ]; c = mat[ 0 ][x1 + 2 ]; a1 = mat[ 1 ][x1]; b1 = mat[ 1 ][x1 + 1 ]; c1 = mat[ 1 ][x1 + 2 ]; a2 = mat[ 2 ][x1]; b2 = mat[ 2 ][x1 + 1 ]; c2 = mat[ 2 ][x1 + 2 ]; # Check if the arrangement # of '.' and '*' forms # character 'A' if (a = = '.' and b = = '*' and c = = '.' and a1 = = '*' and b1 = = '*' and c1 = = '*' and a2 = = '*' and b2 = = '.' and c2 = = '*' ): # If True, prA print ( "A" ,end = ""); # Increment column number i = i + 2 ; # Check if the arrangement # of '.' and '*' forms # character 'E' if (a = = '*' and b = = '*' and c = = '*' and a1 = = '*' and b1 = = '*' and c1 = = '*' and a2 = = '*' and b2 = = '*' and c2 = = '*' ): # If True, prE print ( "E" ,end = ""); # Increment column number i = i + 2 ; # Check if the arrangement # of '.' and '*' forms # character 'I' if (a = = '*' and b = = '*' and c = = '*' and a1 = = '.' and b1 = = '*' and c1 = = '.' and a2 = = '*' and b2 = = '*' and c2 = = '*' ): # If True, prI print ( "I" ,end = ""); # Increment column number i = i + 2 ; # Check if the arrangement # of '.' and '*' forms # character 'O' if (a = = '*' and b = = '*' and c = = '*' and a1 = = '*' and b1 = = '.' and c1 = = '*' and a2 = = '*' and b2 = = '*' and c2 = = '*' ): # If True, prO print ( "O" ,end = ""); # Increment column number i = i + 2 ; # Check if the arrangement # of '.' and '*' forms # character 'U' if (a = = '*' and b = = '.' and c = = '*' and a1 = = '*' and b1 = = '.' and c1 = = '*' and a2 = = '*' and b2 = = '*' and c2 = = '*' ): # If True, prU print ( "U" ,end = ""); # Increment column number i = i + 2 ; # Driver Code if __name__ = = '__main__' : # Given n, number of columns N = 18 ; # Given matrix mat = [[ '*' , '.' , '*' , '#' , '*' , '*' , '*' , '#' , '*' , '*' , '*' , '#' , '*' , '*' , '*' , '.' , '*' , '.' ] , [ '*' , '.' , '*' , '#' , '*' , '.' , '*' , '#' , '.' , '*' , '.' , '#' , '*' , '*' , '*' , '*' , '*' , '*' ], [ '*' , '*' , '*' , '#' , '*' , '*' , '*' , '#' , '*' , '*' , '*' , '#' , '*' , '*' , '*' , '*' , '.' , '*' ] ]; # Function Call printGalaxy(mat, N); # This code is contributed by umadevi9616 |
C#
// C# program for the above approach using System; public class GFG { // Function to print the vowels(stars) // in order of their occurrence within // the given galaxy static void printGalaxy( char [,]mat, int n) { // Iterate the matrix column-wise for ( int i = 0; i < n; i++) { // If all '#' is encountered // in the given column, print '#' if (mat[0,i] == '#' && mat[1,i] == '#' && mat[2,i] == '#' ) { Console.Write( '#' ); } // If all '.' is encountered in // the given column, skip the // current column else if (mat[0,i] == '.' && mat[1,i] == '.' && mat[2,i] == '.' ) { } // If above cases fail else { char a, b, c, a1, b1; char c1, a2, b2, c2; int x1 = i; a = mat[0,x1]; b = mat[0,x1 + 1]; c = mat[0,x1 + 2]; a1 = mat[1,x1]; b1 = mat[1,x1 + 1]; c1 = mat[1,x1 + 2]; a2 = mat[2,x1]; b2 = mat[2,x1 + 1]; c2 = mat[2,x1 + 2]; // Check if the arrangement // of '.' and '*' forms // character 'A' if (a == '.' && b == '*' && c == '.' && a1 == '*' && b1 == '*' && c1 == '*' && a2 == '*' && b2 == '.' && c2 == '*' ) { // If true, print A Console.Write( "A" ); // Increment column number i = i + 2; } // Check if the arrangement // of '.' and '*' forms // character 'E' if (a == '*' && b == '*' && c == '*' && a1 == '*' && b1 == '*' && c1 == '*' && a2 == '*' && b2 == '*' && c2 == '*' ) { // If true, print E Console.Write( "E" ); // Increment column number i = i + 2; } // Check if the arrangement // of '.' and '*' forms // character 'I' if (a == '*' && b == '*' && c == '*' && a1 == '.' && b1 == '*' && c1 == '.' && a2 == '*' && b2 == '*' && c2 == '*' ) { // If true, print I Console.Write( "I" ); // Increment column number i = i + 2; } // Check if the arrangement // of '.' and '*' forms // character 'O' if (a == '*' && b == '*' && c == '*' && a1 == '*' && b1 == '.' && c1 == '*' && a2 == '*' && b2 == '*' && c2 == '*' ) { // If true, print O Console.Write( "O" ); // Increment column number i = i + 2; } // Check if the arrangement // of '.' and '*' forms // character 'U' if (a == '*' && b == '.' && c == '*' && a1 == '*' && b1 == '.' && c1 == '*' && a2 == '*' && b2 == '*' && c2 == '*' ) { // If True, print U Console.Write( "U" ); // Increment column number i = i + 2; } } } } // Driver Code public static void Main(String[] args) { // Given n, number of columns int N = 18; // Given matrix char [,]mat = { { '*' , '.' , '*' , '#' , '*' , '*' , '*' , '#' , '*' , '*' , '*' , '#' , '*' , '*' , '*' , '.' , '*' , '.' }, { '*' , '.' , '*' , '#' , '*' , '.' , '*' , '#' , '.' , '*' , '.' , '#' , '*' , '*' , '*' , '*' , '*' , '*' }, { '*' , '*' , '*' , '#' , '*' , '*' , '*' , '#' , '*' , '*' , '*' , '#' , '*' , '*' , '*' , '*' , '.' , '*' } }; // Function Call printGalaxy(mat, N); } } // This code is contributed by Amit Katiyar |
Javascript
<script> // Javascript program for the above approach // Function to print the vowels(stars) // in order of their occurrence within // the given galaxy function printGalaxy(mat, n) { // Iterate the matrix column-wise for (let i = 0; i < n; i++) { // If all '#' is encountered // in the given column, print '#' if (mat[0][i] == '#' && mat[1][i] == '#' && mat[2][i] == '#' ) { document.write( '#' ); } // If all '.' is encountered in // the given column, skip the // current column else if (mat[0][i] == '.' && mat[1][i] == '.' && mat[2][i] == '.' ) { } // If above cases fail else { let a, b, c, a1, b1; let c1, a2, b2, c2; let x1 = i; a = mat[0][x1]; b = mat[0][x1 + 1]; c = mat[0][x1 + 2]; a1 = mat[1][x1]; b1 = mat[1][x1 + 1]; c1 = mat[1][x1 + 2]; a2 = mat[2][x1]; b2 = mat[2][x1 + 1]; c2 = mat[2][x1 + 2]; // Check if the arrangement // of '.' and '*' forms // character 'A' if (a == '.' && b == '*' && c == '.' && a1 == '*' && b1 == '*' && c1 == '*' && a2 == '*' && b2 == '.' && c2 == '*' ) { // If true, print A document.write( "A" ); // Increment column number i = i + 2; } // Check if the arrangement // of '.' and '*' forms // character 'E' if (a == '*' && b == '*' && c == '*' && a1 == '*' && b1 == '*' && c1 == '*' && a2 == '*' && b2 == '*' && c2 == '*' ) { // If true, print E document.write( "E" ); // Increment column number i = i + 2; } // Check if the arrangement // of '.' and '*' forms // character 'I' if (a == '*' && b == '*' && c == '*' && a1 == '.' && b1 == '*' && c1 == '.' && a2 == '*' && b2 == '*' && c2 == '*' ) { // If true, print I document.write( "I" ); // Increment column number i = i + 2; } // Check if the arrangement // of '.' and '*' forms // character 'O' if (a == '*' && b == '*' && c == '*' && a1 == '*' && b1 == '.' && c1 == '*' && a2 == '*' && b2 == '*' && c2 == '*' ) { // If true, print O document.write( "O" ); // Increment column number i = i + 2; } // Check if the arrangement // of '.' and '*' forms // character 'U' if (a == '*' && b == '.' && c == '*' && a1 == '*' && b1 == '.' && c1 == '*' && a2 == '*' && b2 == '*' && c2 == '*' ) { // If True, print U document.write( "U" ); // Increment column number i = i + 2; } } } } // Driver Code // Given n, number of columns let N = 18; // Given matrix let mat = [ [ '*' , '.' , '*' , '#' , '*' , '*' , '*' , '#' , '*' , '*' , '*' , '#' , '*' , '*' , '*' , '.' , '*' , '.' ], [ '*' , '.' , '*' , '#' , '*' , '.' , '*' , '#' , '.' , '*' , '.' , '#' , '*' , '*' , '*' , '*' , '*' , '*' ], [ '*' , '*' , '*' , '#' , '*' , '*' , '*' , '#' , '*' , '*' , '*' , '#' , '*' , '*' , '*' , '*' , '.' , '*' ] ]; // Function Call printGalaxy(mat, N); // This code is contributed by gfgking. </script> |
U#O#I#EA
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us