HackerRank Emas Supercomputer Solution

by

Hello Programmers, In this post, you will know how to solve the HackerRank Emas Supercomputer Solution. This problem is a part of the HackerRank Algorithms Series.

HackerRank Emas Supercomputer Solution
HackerRank Emas Supercomputer Solution

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Hackerrank by yourself. If you find any difficulty after trying several times, then you can look for solutions.

HackerRank Emas Supercomputer Game Solution

Task

Ema built a quantum computer! Help her test its capabilities by solving the problem below.

Given a grid of size n x m, each cell in the grid is either good or bad.

A valid plus is defined here as the crossing of two segments (horizontal and vertical) of equal lengths. These lengths must be odd, and the middle cell of its horizontal segment must cross the middle cell of its vertical segment.

In the diagram below, the blue pluses are valid and the orange ones are not valid.

Find the two largest valid pluses that can be drawn on good cells in the grid, and return an integer denoting the maximum product of their areas. In the above diagrams, our largest pluses have areas of 5 and 9. The product of their areas is 5 x 9 = 45.

Note: The two pluses cannot overlap, and the product of their areas should be maximal.

Function Description

Complete the twoPluses function in the editor below. It should return an integer that represents the area of the two largest pluses.

twoPluses has the following parameter(s):

  • grid: an array of strings where each string represents a row and each character of the string represents a column of that row

Input Format

The first line contains two space-separated integers, n and m.
Each of the next n lines contains a string of m characters where each character is either G (good) or B (bad). These strings represent the rows of the grid. If the yth character in the xth line is G, then (x, y) is a good cell. Otherwise it’s a bad cell.

Constraints

  • 2 <= n <= 15
  • 2 <= m <= 15

Output Format

Find  pluses that can be drawn on  cells of the grid, and return an integer denoting the maximum product of their areas.

Sample Input 0

5 6
GGGGGG
GBBBGB
GGGGGG
GGBBGB
GGGGGG

Sample Output 0

5

Sample Input 1

6 6
BGBBGB
GGGGGG
BGBBGB
GGGGGG
BGBBGB
BGBBGB

Sample Output 1

25

Explanation

Here are two possible solutions for Sample 0 (left) and Sample 1 (right): 

Explanation Key:

  • Green: good cell
  • Red: bad cell
  • Blue: possible pluses.

For the explanation below, we will refer to a plus of length i as Pi.

Sample 0
There is enough good space to color one P3 plus and one P1 plus. Area(P3) = 5 units, and Area(P1) = 1 unit. The product of their areas is 5 x 1 = 5.

Sample 1
There is enough good space to color two P3 pluses. Area(P3) = 5 units. The product of the areas of our two P3 pluses is 5 x 5 = 25.

HackerRank Emas Supercomputer Solution

Emas Supercomputer Solution in C

 #include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
char grid[15][16], grid2[15][16];
int n, m;
void copygrid() {
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) grid2[i][j] = grid[i][j];
}
int main() {
    int area[] = {0, 1, 5, 9, 13, 17, 21, 25, 29, 33};
    int i, j, step, max = 0, temp;
    scanf("%d %d", &n, &m);
    for (i = 0; i < n; i++) {
        scanf("%s", grid[i]);
    }
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            if (grid[i][j] == 'G') {
                copygrid();
                step = 1;
                grid2[i][j] = 'B';
                while (1) {
                    if (i - step < 0 || i + step > n - 1 || j - step < 0 || j + step > m - 1) break;
                    if (grid2[i-step][j] == 'B' || grid2[i+step][j] == 'B' || grid2[i][j-step] == 'B' || grid2[i][j+step] == 'B') break;
                    grid2[i-step][j] = 'B';
                    grid2[i+step][j] = 'B';
                    grid2[i][j-step] = 'B';
                    grid2[i][j+step] = 'B';
                    step++;
                }
                temp = area[step];
                int k, l;
                for (k = 0; k < n; k++) {
                    for (l = 0; l < m; l++) {
                        if (grid2[k][l] == 'G') {
                            step = 1;
                            while (1) {
                                if (k - step < 0 || k + step > n - 1 || l - step < 0 || l + step > m - 1) break;
                                if (grid2[k-step][l] == 'B' || grid2[k+step][l] == 'B' || grid2[k][l-step] == 'B' || grid2[k][l+step] == 'B') break;
                                step++;
                            }
                            if (temp * area[step] > max) max = temp * area[step];
                        }
                    }
                }
            }
        }
    }
    printf("%d", max);
    return 0;
}

Emas Supercomputer Solution in Cpp

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
int main() {
	int N; int M;
	while(~scanf("%d%d", &N, &M)) {
		vector<string> a(N);
		rep(i, N) cin >> a[i];
		int ans = 0;
		rep(y0, N) rep(x0, M) rer(s0, 1, min({ y0 + 1, N - y0, x0 + 1, M - x0 })) {
			vector<vector<bool> > good(N, vector<bool>(M));
			rep(i, N) rep(j, M)
				good[i][j] = a[i][j] == 'G';
			bool ok = true;
			rer(d, -s0 + 1, s0 - 1) {
				ok &= good[y0 + d][x0];
				ok &= good[y0][x0 + d];
				good[y0 + d][x0] = good[y0][x0 + d] = false;
			}
			if(!ok) continue;
			rep(y1, N) rep(x1, M) {
				int maxs1 = min({ y1 + 1, N - y1, x1 + 1, M - x1 });
				int s1 = maxs1;
				rer(d, -maxs1 + 1, maxs1 - 1) {
					if(!good[y1 + d][x1] || !good[y1][x1 + d])
						amin(s1, abs(d) - 1);
				}
				if(s1 > 0)
					amax(ans, ((s0 - 1) * 4 + 1) * ((s1 - 1) * 4 + 1));
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

Emas Supercomputer Solution in Java

import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;
public class Solution {
	static boolean[][] good;
	public static void main(String[] args) throws IOException{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		 good = new boolean[n][m];
		for(int i = 0; i < n; i++) {
			String s = in.next();
			for(int j = 0; j < m; j++) {
				good[i][j] = s.charAt(j) == 'G';
			}
		}
		int s = 0;
		for(int a = 0; a < n; a++) {
			for(int b = 0; b < m; b++) {
				for(int c = 0; a - c >= 0 && a + c < n && b - c >= 0 && b + c < m; c++) {
					for(int x = 0; x < n; x++) {
						for(int y = 0; y < m; y++) {
							for(int z = 0; x - z >= 0 && x + z < n && y - z >= 0 && y + z < m; z++) {
								if(valid(a, b, c, x, y, z)) {
									s = Math.max(s, (4 * c + 1) * (4 * z + 1));
								}
							}
						}
					}
				}
			}
		}
		System.out.println(s);
	}
	public static boolean valid(int a, int b, int c, int x, int y, int z) {
		boolean[][] cp = new boolean[good.length][good[0].length];
		for(int i = 0; i < good.length; i++) {
			for(int j = 0 ; j < good[0].length; j++) {
				cp[i][j] = good[i][j];
			}
		}
		if(!cp[a][b]) {
			return false;
		}
		cp[a][b] = false;
		for(int i = 1; i <= c; i++) {
			if(!cp[a - i][b] || !cp[a][b - i] || !cp[a + i][b] || !cp[a][b + i]) {
				return false;
			}
			cp[a - i][b] = false;
			cp[a + i][b] = false;
			cp[a][b - i] = false;
			cp[a][b + i] = false;
		}
		if(!cp[x][y]) {
			return false;
		}
		cp[x][y] = false;
		for(int i = 1; i <= z; i++) {
			if(!cp[x - i][y] || !cp[x][y - i] || !cp[x + i][y] || !cp[x][y + i]) {
				return false;
			}
			cp[x - i][y] = false;
			cp[x + i][y] = false;
			cp[x][y - i] = false;
			cp[x][y + i] = false;
		}
		return true;
	}
}
Ezoicreport this ad

Emas Supercomputer Solution in Python

# Enter your code here. Read input from STDIN. Print output to STDOUT
from sys import exit
# read input
ns = map(int, raw_input().strip().split())
n = ns[0]
grid = []
for i in range(n):
    grid.append(raw_input())
# make sure there are at least 2 Gs, else output 0
num_gs = 0
for row in grid:
    num_gs += len(row) - len(row.replace("G", ""))
if num_gs < 2:
    print 0
    exit(0)
    
grid = [list(x) for x in grid]
# find pluses n stuff
def get_max_plus_radius(g, r, c):
    
    left_bound = c
    while left_bound >= 0 and g[r][left_bound] == 'G':
        left_bound -= 1
    right_bound = c
    while right_bound < len(g[r]) and g[r][right_bound] == 'G':
        right_bound += 1
    upper_bound = r
    while upper_bound >= 0 and g[upper_bound][c] == 'G':
        upper_bound -= 1
    lower_bound = r
    while lower_bound < len(g) and g[lower_bound][c] == 'G':
        lower_bound += 1
        
    bound = min(c - left_bound, right_bound - c, r - upper_bound, lower_bound - r)
    return bound
def get_area_with_radius(radius):
    return 1 + (radius - 1)*4
def get_max_plus_area_at(g, r, c):
        
    bound = get_max_plus_radius(g, r, c)
    if bound == 0:
        return 0
    return get_area_with_radius(bound)
    
def find_max_plus_area(g):
    max_plus_area = 0
    for row in range(len(g)):
        for col in range(len(g[row])):
            max_plus_area = max(max_plus_area, get_max_plus_area_at(g, row, col))
    return max_plus_area
def set_plus_val(g, r, c, rad, val):
    
    left_cursor = c
    right_cursor = c
    up_cursor = r
    down_cursor = r
    
    while rad > 0:
        g[r][left_cursor] = val
        g[r][right_cursor] = val
        g[up_cursor][c] = val
        g[down_cursor][c] = val
        
        left_cursor-=1
        right_cursor+=1
        up_cursor-=1
        down_cursor+=1
        
        rad -= 1
        
max_area_product = 0
for row in range(len(grid)):
    for col in range(len(grid[row])):
        # for each plus centered at this location
        cur_max_rad = get_max_plus_radius(grid, row, col)
        for cur_rad in range(1, cur_max_rad+1):
            area1 = get_area_with_radius(cur_rad)
            set_plus_val(grid, row, col, cur_rad, 'B')
            area2 = find_max_plus_area(grid)
            max_area_product = max(max_area_product, area1*area2)
            set_plus_val(grid, row, col, cur_rad, 'G')
            
print max_area_product

Emas Supercomputer Solution using JavaScript

function replaceChar(s, i, ch) {
    return s.substr(0, i) + ch + s.substr(i + ch.length);
}
function processData(input) {
    var lines = input.split("\n");
    var nm = lines[0].split(" "), n = 1*nm[0], m = 1*nm[1];
    var grid = lines.slice(1);
    
    function rank(grid, i, j) {
        for (var o = 1; o <= Math.min(i, j, n - 1 - i, m - 1 - j); o++)
            if (grid[i-o][j] === "B" ||
                grid[i+o][j] === "B" ||
                grid[i][j-o] === "B" ||
                grid[i][j+o] === "B")
                break;
        return o;
    }
    
    function area(r) { return 4 * (r-1) + 1; }
    
    var maxprod = 0;
    for (var i = 0; i < n; i++)
    for (var j = 0; j < m; j++)
        if (grid[i][j] === "G") {
            var r = rank(grid, i, j);
            var ngrid = grid.concat();
            ngrid[i] = replaceChar(ngrid[i], j, "B");
            for (var o = 1; o < r; o++) {
                ngrid[i-o] = replaceChar(ngrid[i-o], j, "B");
                ngrid[i+o] = replaceChar(ngrid[i+o], j, "B");
                ngrid[i] = replaceChar(ngrid[i], j-o, "B");
                ngrid[i] = replaceChar(ngrid[i], j+o, "B");
            }
            
            var r2 = 0;
            for (var k = 0; k < n; k++)
            for (var l = 0; l < m; l++)
                if (ngrid[k][l] === "G")
                    r2 = Math.max(r2, rank(ngrid, k, l));
            
            maxprod = Math.max(maxprod, area(r)*area(r2));
        }
    
    console.log(maxprod);
} 
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});
process.stdin.on("end", function () {
   processData(_input);
});

Emas Supercomputer Solution in Scala

object Solution {
    def main(args: Array[String]) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution
*/
        
            import scala.io.StdIn
    import scala.collection.mutable
    val lin = StdIn.readLine.split(' ').head.toInt
    val arr: Seq[Array[Char]] = Seq.fill(lin)(StdIn.readLine.toCharArray)
    type Plus = List[(Int, Int)]
    def createPossibles(lini: Int, coli: Int, step: Int): Option[Plus] = for {
      cent <- safeGet(lini, coli)
      left <- safeGet(lini - step, coli)
      up <- safeGet(lini, coli - step)
      right <- safeGet(lini + step, coli)
      down <- safeGet(lini, coli + step)
      inner <- if (step > 0) createPossibles(lini, coli, step - 1) else Some(Nil)
    } yield {
      (List(cent, left, up, right, down) ::: inner) .distinct
    }
    def safeGet(lini: Int, coli: Int): Option[(Int, Int)] = for {
      i <- arr.lift(lini)
      n <- i.lift(coli) if n == 'G'
    } yield (lini, coli)
    def findNext(step: Int): Seq[Plus] = for {
      (line, lini) <- arr.zipWithIndex
      (cole, coli) <- line.zipWithIndex
      plus <- createPossibles(lini, coli, step)
    } yield plus
    
    val allPluses = for (i <- 0 to lin) yield findNext(i)
    val withoutEMpty = allPluses.flatten.filter(_.nonEmpty)
    val startQu: mutable.Queue[Plus] = collection.mutable.Queue(withoutEMpty: _*)
    def compute(qu: mutable.Queue[Plus]): mutable.Queue[Int] = {
      val one = qu.dequeue()
      val answers: mutable.Queue[Int] = qu.collect {
        case two if (two intersect one).isEmpty => two.size * one.size
        case _ => 0
      }
      if (qu.nonEmpty) {
        compute(qu) ++ answers
      }
      else answers
    }
    val max = compute(startQu).sorted.last
    println(max)
    }
}

Emas Supercomputer Solution in Pascal

uses math;
var n,m,res,count:longint;
	a:array[0..55,0..55] of char;
	c:array[0..55,0..55] of longint;
Procedure ReadF;
var i,j:longint;
begin
readln(n,m);
for i:=1 to n do
	begin
	for j:=1 to m do read(a[i,j]);
	readln;
	end;
end;
Procedure Process;
var i,j,k,x,y,h:longint;
begin
count:=1;
for i:=1 to n do
	for j:=1 to m do
		for k:=1 to 20 do
			if (a[i-k+1,j]=a[i+k-1,j]) and (a[i+k-1,j]=a[i,j-k+1]) and (a[i+k-1,j]=a[i,j+k-1]) and (a[i+k-1,j]='G') then
				begin
				c[i-k+1,j]:=1;
				c[i+k-1,j]:=1;
				c[i,j+k-1]:=1;
				c[i,j-k+1]:=1;
				for x:=1 to n do
					for y:=1 to m do
						for h:=1 to 20 do
							if (a[x-h+1,y]=a[x+h-1,y]) and (a[x+h-1,y]=a[x,y-h+1]) and (a[x+h-1,y]=a[x,y+h-1]) and (a[x+h-1,y]='G')
							and (c[x-h+1,y]<count) and (c[x+h-1,y]<count) and (c[x,y+h-1]<count) and (c[x,y-h+1]<count) then
								res:=max(res,((k-1)*4+1)*((h-1)*4+1))
							else break;
				end
			else
				begin
				fillchar(c,sizeof(c),0);
				break;
				end;
write(res);
end;
begin
ReadF;
Process;
end.

Disclaimer: This problem (Emas Supercomputer) is generated by HackerRank but the Solution is Provided by BrokenProgrammers. This tutorial is only for Educational and Learning purposes.

Next: HackerRank Fair Rations Solution

Sharing Is Caring

Leave a Comment

Ezoicreport this ad