In this post, we will solve Ema’s Supercomputer HackerRank Solution. This problem (Ema’s Supercomputer) is a part of HackerRank Problem Solving series.
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 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
GGGGGGSample Output 0
5Sample Input 1
6 6
BGBBGB
GGGGGG
BGBBGB
GGGGGG
BGBBGB
BGBBGBSample Output 1
25Explanation 1
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.
Solution – Ema’s Supercomputer – HackerRank Solution
C++
#include <vector>
#include <iostream>
#include <algorithm>
#include <utility>
struct Plus {
int center_row, center_col, stretch, area;
};
int main() {
int n,m;
std::cin >> n >> m;
std::vector< std::vector<bool> > grid(n, std::vector<bool>(m));
char tmp;
for (auto& row : grid) {
for (auto el : row) {
std::cin >> tmp;
el = tmp == 'G';
}
}
std::vector<Plus> valid_areas;
std::vector<int> arr;
int i,j,up,down,right,left, tmp_i,tmp_j, max_stretch;
for (i = 1; i < n-1; i++) {
for (j = 1; j < m-1; j++) {
if (!grid[i][j]) continue;
up = down = right = left = 0;
tmp_i = i-1;
while(tmp_i >= 0 && grid[tmp_i--][j])
up++;
tmp_i = i+1;
while(tmp_i < n && grid[tmp_i++][j])
down++;
tmp_j = j+1;
while(tmp_j < m && grid[i][tmp_j++])
right++;
tmp_j = j-1;
while(tmp_j >= 0 && grid[i][tmp_j--])
left++;
arr = {up,down,left,right};
for (max_stretch = *std::min_element(arr.begin(),arr.end()); max_stretch >= 0; max_stretch--) {
valid_areas.push_back({
i,j,max_stretch,max_stretch*4+1
});
}
}
}
auto comp = [](Plus l, Plus r){return l.area > r.area;};
std::sort(valid_areas.begin(),valid_areas.end(), comp);
Plus a,b;
int s = valid_areas.size();
std::vector<int> results;
for (i = 0; i < s; i++) {
a = valid_areas[i];
for (j = i+1; j < s; j++) {
b = valid_areas[j];
bool row, arow, col, acol;
row = b.center_row < a.center_row;
arow = b.center_row > a.center_row;
col = b.center_col < a.center_col;
acol = b.center_col > a.center_col;
if (row) {
if (col) {
if ((b.stretch + b.center_row >= a.center_row && a.center_col - a.stretch <= b.center_col)
|| (b.center_col + b.stretch >= a.center_col && a.center_row - a.stretch <= b.center_row)) {
continue;
} else {
results.push_back(a.area * b.area);
break;
}
} else if (acol) {
if ((b.stretch + b.center_row >= a.center_row && a.center_col + a.stretch >= b.center_col)
|| (b.center_col - b.stretch <= a.center_col && a.center_row - a.stretch <= b.center_row)) {
continue;
} else {
results.push_back(a.area * b.area);
break;
}
} else {
if (b.stretch + b.center_col >= a.center_col - a.stretch) {
continue;
} else {
results.push_back(a.area * b.area);
break;
}
}
} else if (arow) {
if (col) {
if ((b.center_row - b.stretch <= a.center_row && a.center_col - a.stretch <= b.center_col)
|| (b.center_col + b.stretch >= a.center_col && a.center_row + a.stretch >= b.center_row)) {
continue;
} else {
results.push_back(a.area * b.area);
break;
}
} else if (acol) {
if ((b.center_row - b.stretch <= a.center_row && a.center_col + a.stretch >= b.center_col)
|| (b.center_col - b.stretch <= a.center_col && a.center_row + a.stretch >= b.center_row)) {
continue;
} else {
results.push_back(a.area * b.area);
break;
}
} else {
if (b.center_col - b.stretch <= a.center_col + a.stretch) {
continue;
} else {
results.push_back(a.area * b.area);
break;
}
}
} else {
if (col) {
if (b.stretch + b.center_col < a.center_col - a.stretch) {
results.push_back(a.area * b.area);
break;
}
} else if (acol) {
if (b.center_col - b.stretch > a.center_col + a.stretch) {
results.push_back(a.area * b.area);
break;
}
} // else continue
}
}
}
std::cout << *std::max_element(results.begin(),results.end()) << std::endl;
return 0;
}
Python
def get_pluses(x, y, grid, width, height):
pluses = []
if grid[y][x]:
dist = 0
for i in range(0, max(width, height)):
if y-i < 0 or not grid[y-i][x]:
break
if y+i >= height or not grid[y+i][x]:
break
if x-i < 0 or not grid[y][x-i]:
break
if x+i >= width or not grid[y][x+i]:
break
pluses.append((x, y, dist, dist * 4 + 1))
dist += 1
return pluses
def line_intersect(l1, l2):
return l1[0] <= l2[2] and l1[2] >= l2[0] and l1[1] <= l2[3] and l1[3] >= l2[1]
def intersect(p1, p2):
if p1[0] == p2[0] and p1[1] == p2[1]:
return True
l1 = p1[0] - p1[2], p1[1], p1[0] + p1[2], p1[1]
l2 = p1[0], p1[1] - p1[2], p1[0], p1[1] + p1[2]
l3 = p2[0] - p2[2], p2[1], p2[0] + p2[2], p2[1]
l4 = p2[0], p2[1] - p2[2], p2[0], p2[1] + p2[2]
return line_intersect(l1, l3) or line_intersect(l1, l4) or line_intersect(l2, l3) or line_intersect(l2, l4)
if __name__ == '__main__':
n, m = map(int, input().strip().split(' '))
grid = []
for i in range(n):
grid.append([True if x == 'G' else False for x in input().strip()])
pluses = []
for y in range(n):
for x in range(m):
pluses += get_pluses(x, y, grid, m, n)
if len(pluses) <= 1:
print(0)
else:
best = 0
for i in range(len(pluses)-1):
for j in range(i+1, len(pluses)):
if not intersect(pluses[i], pluses[j]):
best = max(best, pluses[i][3] * pluses[j][3])
print(best)
Java
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Solution {
static class ValidPlus{
public int area;
public int length;
public ArrayList<Cell> cells = new ArrayList<>();
public ValidPlus() {
area = 1;
length = 1;
}
public ValidPlus(ValidPlus anotherValidPlus) {
this.area = anotherValidPlus.area;
this.length = anotherValidPlus.length;
this.cells = new ArrayList<Cell>(anotherValidPlus.cells);
}
public void addCell(Cell cell) {
cells.add(cell);
}
}
static class Cell {
public int row;
public int column;
public Cell(int row, int column) {
super();
this.row = row;
this.column = column;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + column;
result = prime * result + row;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Cell other = (Cell) obj;
if (column != other.column)
return false;
if (row != other.row)
return false;
return true;
}
}
public static void main(String[] args) throws CloneNotSupportedException {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
ArrayList<ValidPlus> validPluses = new ArrayList<>();
char[][] map = new char[n][m];
for (int i = 0; i < n; i++) {
String line = sc.next();
for (int j = 0; j < m; j++) {
map[i][j] = line.charAt(j);
}
}
sc.close();
// We save all the valid pluses
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
char currentCell = map[i][j];
if (currentCell == 'G') {
boolean thereIsGoodCell = true;
// Everytime we find a good cell, we create a valid plus
// with length 1
ValidPlus validPlus = new ValidPlus();
int length = 1;
validPlus.addCell(new Cell(i, j));
validPluses.add(validPlus);
while (thereIsGoodCell) {
// We check if it's possible to extend the valid plus in
// all the four directions
if ((i - length >= 0 && map[i - length][j] == 'G')
&& (i + length < n && map[i + length][j] == 'G')
&& (j - length >= 0 && map[i][j - length] == 'G')
&& (j + length < m && map[i][j + length] == 'G')) {
// If it's possible, we create a new valid plus
ValidPlus newValidPlus = new ValidPlus(validPlus);
newValidPlus.addCell(new Cell(i - length, j));
newValidPlus.addCell(new Cell(i + length, j));
newValidPlus.addCell(new Cell(i, j - length));
newValidPlus.addCell(new Cell(i, j + length));
length++;
newValidPlus.area = 1 + (4 * (length - 1));
newValidPlus.length = length;
validPluses.add(newValidPlus);
validPlus = new ValidPlus(newValidPlus);
} else {
thereIsGoodCell = false;
}
}
}
}
}
int maxArea = 0;
// We compare all the valid pluses
for (int i = 0; i < validPluses.size(); i++) {
ValidPlus currentValidPlus = validPluses.get(i);
for (int j = i + 1; j < validPluses.size(); j++) {
ValidPlus otherValidPlus = validPluses.get(j);
int currentArea = currentValidPlus.area * otherValidPlus.area;
if (currentArea > maxArea) {
// If we have found a new max area, we have to check that
// the valid pluses don't overlap.
// To do this, we get the cells occupied by the two valid
// pluses
ArrayList<Cell> currentCells = currentValidPlus.cells;
ArrayList<Cell> otherCells = otherValidPlus.cells;
List<Cell> commonCells = new ArrayList<Cell>(currentCells);
commonCells.retainAll(otherCells);
// If the valid pluses don't have common cells, it's OK
if (commonCells.size() == 0) {
maxArea = currentArea;
}
}
}
}
System.out.println(maxArea);
}
}
Note: This problem (Ema’s Supercomputer) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.