HackerRank Ema’s Supercomputer Solution
In this post, we will solve HackerRank Ema’s Supercomputer Problem Solution.
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.
Output Format
Find 2 pluses that can be drawn on good 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 P₁.
Sample 0
There is enough good space to color one P3 plus and one P₁ plus. Area(P3) = 5 units, and Area(P₁) = 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.
Ema’s Supercomputer C Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main()
{
int n, m;
scanf("%d %d \n", &n, &m);
char map[n][m+1];
int i, j;
for(i=0; i<n; i++){
for(j=0; j<=m; j++)
scanf("%c", &map[i][j]);
}
int count[225] = {0}; // store 'valid pluse' count
int post[225] = {0}; // store 'valid pluse' center postion
int num = 0; // count 'valid pluse' number
for(i=0; i<n; i++){
for(j=0; j<m; j++){
if(map[i][j] == 'G'){
int count_num = 1;
int x = 0;
for(x=1; x<8; x++){
if(i-x < 0 || map[i-x][j] != 'G') break;
if(i+x >= n || map[i+x][j] != 'G') break;
if(j-x < 0 || map[i][j-x] != 'G') break;
if(j+x >= m || map[i][j+x] != 'G') break;
count_num += 4; // calculate 'valid pluse' count
count[num] = count_num; // store 'valid pluse' count
// count_num = 5, 9, 13, 17 ...
post[num++] = (i) * n + (j);
// store 'valid pluse' center postion
}
}
}
}
int max = 1; // store answer --> max
count[num] = 1; // add 1 in the tail
for(i=0; i<=num-1; i++){
for(j=i+1; j<=num; j++){
if(count[i] * count[j] > max){
int compare_1[count[i]];
// store 'valid pluse' 1 all postion
int compare_2[count[j]];
// store 'valid pluse' 2 all postion
int x = 1, nx = 1;
compare_1[0] = post[i];
while(nx < count[i]){
compare_1[nx++] = post[i] - (n * x);
compare_1[nx++] = post[i] + (n * x);
compare_1[nx++] = post[i] - x;
compare_1[nx++] = post[i] + x;
x++;
} // calculate 'valid pluse' 1 "all" postion
// and store in compare_1 array
int y = 1, ny = 1;
compare_2[0] = post[j];
while(ny < count[j]){
compare_2[ny++] = post[j] - (n * y);
compare_2[ny++] = post[j] + (n * y);
compare_2[ny++] = post[j] - y;
compare_2[ny++] = post[j] + y;
y++;
} // calculate 'valid pluse' 2 "all" postion
// and store in compare_2 array
int flag = 1; // calculate the repeat place
for(int ni=0; ni<count[i]; ni++){
for(int nj=0; nj<count[j]; nj++){
if(compare_1[ni] == compare_2[nj]){
flag = 0;
ni = count[i], nj = count[j];
// jump out of the loop
}
}
}
if(flag == 1) max = count[i] * count[j]; // no repeat place
}
}
}
printf("%d",max); // print ans
return 0;
}Ema’s Supercomputer C++ Solution
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
bool intersects(const int x1, const int y1, const int s1,
const int x2, const int y2, const int s2) {
const int d = abs(x1 - x2) + abs(y1 - y2);
if (x1 == x2 || y1 == y2) {
return d <= s1 + s2;
}
if (abs(y2 - y1) <= s1 && abs(x1 - x2) <= s2) {
return true;
}
if (abs(y2 - y1) <= s2 && abs(x1 - x2) <= s1) {
return true;
}
return false;
}
int main() {
int n, m;
cin >> n >> m;
vector<string> good(n);
for (int i = 0; i < n; ++i) {
cin >> good[i];
}
vector<vector<int>> max_size(n, vector<int>(m, -1));
for (int x1 = 0; x1 < n; ++x1) {
for (int y1 = 0; y1 < m; ++y1) {
if (good[x1][y1] != 'G') {
continue;
}
max_size[x1][y1] = 0;
const int upper = min(min(x1, y1), min(n - x1 - 1, m - y1 - 1));
for (int size = 1; size <= upper; ++size) {
if (good[x1 - size][y1] != 'G' || good[x1 + size][y1] != 'G' ||
good[x1][y1 - size] != 'G' || good[x1][y1 + size] != 'G') {
break;
}
max_size[x1][y1] = size;
}
}
}
int answer = 0;
for (int x1 = 0; x1 < n; ++x1) {
for (int y1 = 0; y1 < m; ++y1) {
for (int x2 = 0; x2 < n; ++x2) {
for (int y2 = 0; y2 < m; ++y2) {
if (x1 == x2 && y1 == y2) {
continue;
}
if (good[x1][y1] != 'G' || good[x2][y2] != 'G') {
continue;
}
answer = max(answer, 1);
for (int s1 = 0; s1 <= max_size[x1][y1]; ++s1) {
for (int s2 = 0; s2 <= max_size[x2][y2]; ++s2) {
if (!intersects(x1, y1, s1, x2, y2, s2)) {
answer = max(answer, (4 * s1 + 1) * (4 * s2 + 1));
}
}
}
}
}
}
}
cout << answer << "\n";
return 0;
}Ema’s Supercomputer C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
class Solution {
public class Celda
{
public int fila;
public int col;
public Celda() { }
public Celda(int fila, int col)
{
this.fila = fila;
this.col = col;
}
public override bool Equals(object obj)
{
//return base.Equals(obj);
if (this.fila == ((Celda)obj).fila && this.col == ((Celda)obj).col)
{
return true;
}
return false;
}
public override int GetHashCode()
{
return base.GetHashCode();
}
}
static int buscarMaxProd(string[] s)
{
List<List<Celda>> cruces = new List<List<Celda>>();
//bool[,] marcas = new bool[s.Length, s[0].Length];
for (int i = 0; i < s.Length; i++)
{
for (int j = 0; j < s[i].Length; j++)
{
int fila_actual = i, col_actual = j;
int arriba = i, abajo = i, izquierda = j, derecha = j;
if (s[i][j] == 'G')
{
List<Celda> cruz = new List<Celda>();
cruz.Add(new Celda(i, j));
cruces.Add(cruz);
while (arriba - 1 >= 0 && abajo + 1 < s.Length
&& izquierda - 1 >= 0 && derecha + 1 < s[i].Length
&& s[arriba - 1][j] == 'G' && s[abajo + 1][j] == 'G'
&& s[i][izquierda - 1] == 'G' && s[i][derecha + 1] == 'G')
{
cruz.Add(new Celda(arriba - 1, j));
cruz.Add(new Celda(abajo + 1, j));
cruz.Add(new Celda(i, izquierda - 1));
cruz.Add(new Celda(i, derecha + 1));
List<Celda> aux = new List<Celda>(cruz);
cruces.Add(aux);
arriba--;
abajo++;
izquierda--;
derecha++;
}
// cruces.Add(cruz);
}
}
}
//foreach (List<Celda> lista in cruces)
//{
// //if (lista.Count == 9)
// {
// foreach (Celda unaCelda in lista)
// {
// Console.Write("(" + unaCelda.fila + " " + unaCelda.col + ") ");
// }
// Console.WriteLine();
// }
//}
int max_len = 1;
int max_prod = 1;
for (int i = 0; i < cruces.Count; i++)
{
for (int j = i+1; j < cruces.Count; j++)
{
List<Celda> a = cruces[i];
//me fijo si hay algun elemento en comun
List<Celda> b = cruces[j];
int k = 0;
for (k = 0; k < b.Count; k++)
{
if (a.Contains(b[k]))
{
break;
}
}
if (k == b.Count)
{
max_prod = Math.Max(max_prod, a.Count * b.Count);
// Console.Write(max_prod + " ");
}
max_len = Math.Max(max_len, a.Count);
}
}
if (cruces.Count == 1)
{
max_prod = cruces[0].Count;
}
if (max_prod == 1)
{
return max_len;
}
// Console.ReadLine();
return max_prod;
}
static void Main(string[] args)
{
//string[] s =
//{
// "GGGGGGGG",
// "GBGBGGBG",
// "GBGBGGBG",
// "GGGGGGGG",
// "GBGBGGBG",
// "GGGGGGGG",
// "GBGBGGBG",
// "GGGGGGGG"
//};//81
//string[] s =
//{
// "BBBBBGGBGG",
// "GGGGGGGGGG",
// "GGGGGGGGGG",
// "BBBBBGGBGG",
// "BBBBBGGBGG",
// "GGGGGGGGGG",
// "BBBBBGGBGG",
// "GGGGGGGGGG",
// "BBBBBGGBGG",
// "GGGGGGGGGG"
//}; //85
//string[] s =
//{
// "GGGGGGGGGGGG",
// "GBGGBBBBBBBG",
// "GBGGBBBBBBBG",
// "GGGGGGGGGGGG",
// "GGGGGGGGGGGG",
// "GGGGGGGGGGGG",
// "GGGGGGGGGGGG",
// "GBGGBBBBBBBG",
// "GBGGBBBBBBBG",
// "GBGGBBBBBBBG",
// "GGGGGGGGGGGG",
// "GBGGBBBBBBBG"
//}; //81
//string[] s =
//{
// "BBBBGBBBBB",
// "BBBBGBBBBB",
// "BBGGGGGBBB",
// "BBBBGBBBBB",
// "BBBBGBBBBB",
// "BBBBBBBBBB",
//};
//string[] s =
//{
// "GGGGGGGGGG",
// "GGGGGGGGGG",
// "GGGGGGGGGG",
// "GGGGGGGGGG",
// "GGGGGGGGGG",
// "GGGGGGGGGG",
//};
string[] input = Console.ReadLine().Split(' ');
int n = int.Parse(input[0]);
int m = int.Parse(input[1]);
string[] s = new string[n];
for (int i = 0; i < n; i++)
{
s[i] = Console.ReadLine();
}
int max = 0;
max = buscarMaxProd(s);
Console.WriteLine(max);
// Console.ReadLine();
}
}Ema’s Supercomputer Java Solution
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class Result {
/*
* Complete the 'twoPluses' function below.
*
* The function is expected to return an INTEGER.
* The function accepts STRING_ARRAY grid as parameter.
*/
public static class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public static class Line {
Point s;
Point e;
boolean isH;
public Line(Point s, Point e) {
if (s.y == e.y) {
isH = true;
if (s.x <= e.x) {
this.s = s;
this.e = e;
}
else {
this.s = e;
this.e = s;
}
}
else {
isH = false;
if (s.y <= e.y) {
this.s = s;
this.e = e;
}
else {
this.s = e;
this.e = s;
}
}
}
boolean intersects(Line line) {
if (isH && line.isH && s.y == line.s.y) {
return s.x <= line.s.x && e.x >= line.s.x
|| s.x <= line.e.x && e.x >= line.e.x;
}
else if (isH && !line.isH) {
return !(line.e.y < s.y || line.s.y > s.y) && s.x <= line.s.x && e.x >= line.s.x;
}
else if (!isH && !line.isH && s.x == line.s.x) {
return s.y <= line.s.y && e.y >= line.s.y
|| s.y <= line.e.y && e.y >= line.e.y;
}
else if (!isH && line.isH) {
return !(e.y < line.s.y || s.y > line.s.y) && line.s.x <= s.x && line.e.x >= s.x;
}
else {
return false;
}
}
}
public static class Cross {
Point m;
int l;
boolean overlaps (Cross c) {
Line lx1 = new Line(new Point(m.x - l, m.y), new Point(m.x + l, m.y));
Line ly1 = new Line(new Point(m.x, m.y - l), new Point(m.x, m.y + l));
Line lx2 = new Line(new Point(c.m.x - c.l, c.m.y), new Point(c.m.x + c.l, c.m.y));
Line ly2 = new Line(new Point(c.m.x, c.m.y - c.l), new Point(c.m.x, c.m.y + c.l));
return lx1.intersects(lx2)
|| lx1.intersects(ly2)
|| ly1.intersects(lx2)
|| ly1.intersects(ly2);
}
}
public static int twoPluses(List<String> grid) {
List<Cross> crosses = getValidCrosses(grid);
int result = 0;
for (int i = 0; i < crosses.size(); i++) {
Cross c1 = crosses.get(i);
for (int j = i + 1; j < crosses.size(); j++) {
Cross c2 = crosses.get(j);
if (!c1.overlaps(c2)) {
if (result < (c1.l*4 + 1) * (c2.l * 4 + 1)){
result = (c1.l*4 + 1) * (c2.l * 4 + 1);
}
}
}
}
return result;
}
public static List<Cross> getValidCrosses(List<String> grid) {
int width = grid.size();
int height = grid.get(0).length();
List<Cross> crosses = new ArrayList<>();
for (int i = 0; i < width; i++) {
for (int j = 0; j < height; j++) {
char c = grid.get(i).charAt(j);
if (c == 'G') {
int l = 0;
while (true) {
Cross newCross = new Cross();
newCross.m = new Point(i,j);
newCross.l = l;
crosses.add(newCross);
if (i - l - 1 < 0
|| i + l + 1 >= width
|| j - l - 1 < 0
|| j + l + 1 >= height
|| grid.get(i-l - 1).charAt(j) == 'B'
|| grid.get(i+l + 1).charAt(j) == 'B'
|| grid.get(i).charAt(j - l - 1) == 'B'
|| grid.get(i).charAt(j + l + 1) == 'B') {
break;
}
else {
l++;
}
}
}
}
}
return crosses;
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
int n = Integer.parseInt(firstMultipleInput[0]);
int m = Integer.parseInt(firstMultipleInput[1]);
List<String> grid = IntStream.range(0, n).mapToObj(i -> {
try {
return bufferedReader.readLine();
} catch (IOException ex) {
throw new RuntimeException(ex);
}
})
.collect(toList());
int result = Result.twoPluses(grid);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedReader.close();
bufferedWriter.close();
}
}Ema’s Supercomputer JavaScript Solution
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', _ => {
inputString = inputString.replace(/\s*$/, '')
.split('\n')
.map(str => str.replace(/\s*$/, ''));
main();
});
function readLine() {
return inputString[currentLine++];
}
// Complete the twoPluses function below.
function twoPluses(grid) {
let pluses = [];
for(let i = 1; i < grid.length - 1; i++) {
for(let j = 1; j < grid[i].length - 1; j++) {
if(grid[i][j] == "G") { // && grid[i+1][j] == "G" && grid[i-1][j] == "G"
// Left
let left = 0;
let k = j - 1;
while(k >= 0) {
if(grid[i][k] == "G") {
left++;
}else {
break;
}
k--;
}
// Right
let right = 0;
k = j + 1;
while(k < grid[i].length) {
if(grid[i][k] == "G") {
right++;
}else {
break;
}
k++;
}
// Up
let up = 0;
k = i - 1;
while(k >= 0) {
if(grid[k][j] == "G") {
up++;
}else {
break;
}
k--;
}
// Down
let down = 0;
k = i + 1;
while(k < grid.length) {
if(grid[k][j] == "G") {
down++;
}else {
break;
}
k++;
}
let plusLength = Math.min(left, right, up, down);
while(plusLength >= 0) {
let result = plusLength * 4 + 1;
pluses.push({
leftMost: j - plusLength,
rightMost: j + plusLength,
topMost: i - plusLength,
bottomMost: i + plusLength,
plusLength,
i,
j,
result
});
plusLength--;
}
}
}
}
console.log(pluses);
let max = 0;
for(let i = 0; i < pluses.length; i++) {
for(let j = i+1; j < pluses.length; j++) {
let ijResult = pluses[i].result * pluses[j].result;
if(!overlap(pluses[i], pluses[j]) && ijResult > max) {
max = ijResult;
}
}
}
return max;
}
function overlap(a, b) {
if(a.i == b.i && a.j == b.j) return true;
let aIndexes = getAllIndexes(a);
let bIndexes = getAllIndexes(b);
for(let i = 0; i < aIndexes.length; i++) {
if(bIndexes.indexOf(aIndexes[i]) !== -1) {
return true;
}
}
return false;
}
function getAllIndexes(a) {
let arr = [];
arr.push(a.i + "," + a.j);
for(let i = a.leftMost; i <= a.rightMost; i++) {
if(i == a.j) {
continue;
}
arr.push(a.i + "," + i);
}
for(let i = a.topMost; i <= a.bottomMost; i++) {
if(i == a.i) {
continue;
}
arr.push(i + "," + a.j);
}
return arr;
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const nm = readLine().split(' ');
const n = parseInt(nm[0], 10);
const m = parseInt(nm[1], 10);
let grid = [];
for (let i = 0; i < n; i++) {
const gridItem = readLine();
grid.push(gridItem);
}
let result = twoPluses(grid);
ws.write(result + "\n");
ws.end();
}Ema’s Supercomputer Python Solution
h,w=input().strip().split()
h,w=[int(h),int(w)]
grid=[]
area=1
lst=[]
for i in range(h):
tmp=input().strip()
grid.append(list(tmp))
co=0
for u in range(h):
co+=grid[u].count("G")
if co<2:
print(0)
exit()
for i in range (h):
for j in range(w):
if grid[i][j]=="G":
hu=hd=i
wl=wr=j
finding=True
clst=[(i,j)]
lst.append([(i,j)])
while(finding):
hu-=1
hd+=1
wl-=1
wr+=1
up="B" if hu==-1 else grid[hu][j]
down="B" if hd==h else grid[hd][j]
left="B" if wl==-1 else grid[i][wl]
right="B" if wr==w else grid[i][wr]
if up==down==left==right=="G":
clst.append( (hu,j) )
clst.append( (hd,j) )
clst.append( (i,wl) )
clst.append( (i,wr) )
clst2=[itm for itm in clst]
lst=lst+[clst2]
else:
finding=False
l=len(lst)
mxa=1
area=0
for p in range(l):
for q in range(p,l):
if not any(x in lst[p] for x in lst[q]) :
a=len(lst[p])
b=len(lst[q])
a=1 if a==2 else a
b=1 if b==2 else b
mxa= a*b
area=max(area,mxa)
print(area)Other Solutions
