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

Sample Input 1

6 6
BGBBGB
GGGGGG
BGBBGB
GGGGGG
BGBBGB
BGBBGB

Sample Output 1

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.

HackerRank Ema's Supercomputer Problem Solution — HackerRank Ema’s Supercomputer Problem Solution

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)

HackerRank Ema’s Supercomputer Solution