HackerRank Ema’s Supercomputer problem solution

In this 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 nxm, 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.

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.

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

HackerRank Ema’s Supercomputer problem solution in Python programming.

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)

Ema’s supercomputer problem solution in Java Programming.

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Solution {
    static int w, h;
    static char[][] g;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        h = in.nextInt();
        w = in.nextInt();
        g = new char[h][w];
        in.nextLine();
        for (int i = 0; i < h; i++) {
            g[i] = in.nextLine().toCharArray();
        }

        int max = 0;

        for (int len1 = Math.max(w, h); len1 > 0; len1--) {
            List<Cross> firstCrosses = findCrosses(len1);
            System.err.println(firstCrosses.size() + " cross of " + len1);

            for (Cross firstCross : firstCrosses) {
                markCross(firstCross);
                for (int len2 = len1; len2 > 0 && areaFromLen(len1) * areaFromLen(len2) > max; len2--) {
                    for (int x = 0 + len2 / 2; x < w - len2 / 2; x++) {
                        for (int y = 0 + len2 / 2; y < h - len2 / 2; y++) {
                            if (legalCross(x, y, len2)) max = Math.max(max, areaFromLen(len1) * areaFromLen(len2));
                        }
                    }
                }
                unmarkCross(firstCross);
            }
        }

        System.out.println(max);
    }

    static void markCross(Cross c) {
        for (int i = c.x - c.l / 2; i <= c.x + c.l / 2; i++) {
            g[c.y][i] = 'B';
        }
        for (int i = c.y - c.l / 2; i <= c.y + c.l / 2; i++) {
            g[i][c.x] = 'B';
        }
    }

    static void unmarkCross(Cross c) {
        for (int i = c.x - c.l / 2; i <= c.x + c.l / 2; i++) {
            g[c.y][i] = 'G';
        }
        for (int i = c.y - c.l / 2; i <= c.y + c.l / 2; i++) {
            g[i][c.x] = 'G';
        }
    }

    static int areaFromLen(int l) {
        return l + (l - 1);
    }

    static List<Cross> findCrosses(int l) {
        List<Cross> crosses = new ArrayList<>();

        for (int x = 0 + l / 2; x < w - l / 2; x++) {
            for (int y = 0 + l / 2; y < h - l / 2; y++) {
                if (legalCross(x, y, l)) crosses.add(new Cross(x, y, l));
            }
        }

        return crosses;
    }

    static boolean legalCross(int x, int y, int l) {
        for (int i = x - l / 2; i <= x + l / 2; i++) {
            if (g[y][i] != 'G') return false;
        }
        for (int i = y - l / 2; i <= y + l / 2; i++) {
            if (g[i][x] != 'G') return false;
        }
        return true;
    }

    static class Cross {
        int x, y, l;

        public Cross(int x, int y, int l) {
            this.x = x;
            this.y = y;
            this.l = l;
        }
    }

}

Problem solution in C++ programming.

#include <bits/stdc++.h>
#define MAX(a,b) (a>b?a:b)
#define MIN(a,b) (a<b?a:b)
#define UP upper_bound
#define LB lower_bound
#define LL long long 
#define Pi 3.14159265358
#define si size()
#define en end()
#define be begin()
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ii set<int>::iterator
#define Tree int ind, int L, int R
#define Left 2*ind,L,(L+R)/2
#define Right 2*ind+1,(L+R)/2+1,R
using namespace std;
bool f[20][20];
string s[20];
int n, m, k, i, j, res, x;
bool check(int i, int j, int x)
{
     int I=i;	
     while(s[I][j]=='G' && I<=n && !f[I][j])
	   I++;	
	 if(I-i<x)return false;
	 I=i+x/2;
	 int J=i;
	 while(s[I][J]=='G' && J<=m && !f[I][J])
	   J++;
	 if(J-j<(x+1)/2)return false;
	 J=i;
	 while(s[I][J]=='G' && J>=1 && !f[I][J])
	   J--;
	 if(j-J<(x+1)/2)return false;
	 return true;
			   	 	  	 
}
int main(){
	   cin>>n>>m;
	   for(i=1;i<=n;i++)
	    {
	     cin>>s[i];
		 s[i]=' '+s[i];	
		}
	   for(x=1;x<=n;x+=2)
	     for(i=1;i<=n;i++)
		   for(j=1;j<=n;j++)
		     if(s[i][j]=='G' && check(i,j,x))	
		      {	
               for(int l=i;l<i+x;l++)f[l][j]=1;
			   for(int l=j;l<j+(x+1)/2;l++)f[i+x/2][l]=1;
			   for(int l=j;l>j-(x+1)/2;l--)f[i+x/2][l]=1;
			   for(int X=1;X<=n;X+=2)
			     for(int I=1;I<=n;I++)
			       for(int J=1;J<=n;J++)
				     if(s[I][J]=='G' && check(I,J,X))
				       res=max(res,(2*x-1)*(2*X-1));	
               for(int l=i;l<i+x;l++)f[l][j]=0;
			   for(int l=j;l<j+(x+1)/2;l++)f[i+x/2][l]=0;
			   for(int l=j;l>j-(x+1)/2;l--)f[i+x/2][l]=0;	       
			  }
	   cout<<res;		  
       }

Problem solution in C programming.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int N;
int M;

char grid[16][16];


void markPlus(int i, int j, int l, char c)
{
    int k;
    grid[i][j] = c;
    for (k = 1; k <= l; ++k) {
        grid[i+k][j] = c;
        grid[i-k][j] = c;
        grid[i][j+k] = c;
        grid[i][j-k] = c;
    }
}


int checkPlus(int i, int j, int l)
{
    int res = 1;
    int k;
    do {
        if (grid[i][j] != 'G') {
            res = 0;
            break;
        }

        for (k = 1; k <= l; ++k) {
            if (grid[i+k][j] != 'G') {
                res = 0;
                break;
            }
            if (grid[i-k][j] != 'G') {
                res = 0;
                break;
            }
            if (grid[i][j+k] != 'G') {
                res = 0;
                break;
            }
            if (grid[i][j-k] != 'G') {
                res = 0;
                break;
            }
        }
    } while (0);
    return res;
}


int findPlus(int l)
{
    int i;
    int j;

    for (i = l; i < N - l; ++i) {
        for (j = l; j < M - l; ++j) {
            if (checkPlus(i, j, l)) {
                return 1;
            }
        }
    }
    return 0;
}


int main()
{
    int i;
    int j;
    int k;
    int m;
    int res = 0;
    int p1;
    int p2;
    int biggest;

    scanf("%d %d", &N, &M);
    for (i = 0; i < N; ++i) {
        scanf("%s", grid[i]);
    }

    biggest = N;
    if (M < biggest) {
        biggest = M;
    }
    biggest /= 2;

    for (i = 0; i <= biggest; ++i) {
        p1 = 1 + 4 * i;
        for (j = i; j < N-i; ++j) {
            for (k = i; k < M-i; ++k) {
                if (checkPlus(j, k, i)) {
                    markPlus(j, k, i, 'B');
                    for (m = 0; m <= biggest; ++m) {
                        p2 = 1 + 4 * m;
                        if (findPlus(m)) {
                            if (p1 * p2 > res) {
                                res = p1 * p2;
                            }
                        }
                    }
                    markPlus(j, k, i, 'G');
                }
            }
        }
    }

    printf("%dn", res);

    return 0;
}

Problem solution in JavaScript programming.

function processData(input) {
    var lines = input.split('n');
    var n = parseInt(lines[0].split(' ')[0]);
    var m = parseInt(lines[0].split(' ')[1]);
    
    var board = lines.slice(1).map(function(line) { return line.split('').map(function (gb) { return gb === 'G'; } )});
    
    // return the lengths of plusses centered at i, j that fit
    var lengthsThatFit = function(brd, row, col) {
        if (!brd[row][col]) return [];
        var result = [1];
        
        var bordermax = Math.min(row, col);
        bordermax = Math.min(bordermax, n - row - 1);
        bordermax = Math.min(bordermax, m - col - 1);
        
        for (var l = 1; l <= bordermax; l++) {
            if (brd[row - l][col] && brd[row + l][col] && brd[row][col - l] && brd[row][col + l]) {
                result.push(2*l + 1);
            } else {
                return result;
            }
        }
        return result;
    };
    var makeWorkboard = function(brd, workbrd, row, col, size) {
        for (var i = 0; i < n; i++) {
            for (var j = 0; j < m; j++) {
                workbrd[i][j] = brd[i][j];
            }
        }
        workbrd[row][col] = false;
        for (var l = 1; l <= (size - 1) / 2; l++) {
            workbrd[row + l][col] = workbrd[row-l][col] = workbrd[row][col+l] = workbrd[row][col-l] = false;
        }
    };
    var workboard = new Array(n);
    for (var i = 0; i < n; i++) workboard[i] = new Array(m);
    
    var maxProduct = 1;
    
    var productOfLengths = function(length1, length2) {
        return (2*length1 - 1)*(2*length2 - 1);
    };
    
    for (var i = 0; i < n; i++) {
        for (var j = 0; j < m; j++) {
            var lengths = lengthsThatFit(board, i, j);
            for (var k = 0; k < lengths.length; k++) {
                makeWorkboard(board, workboard, i, j, lengths[k]);
                for (var p = 0; p < n; p++) {
                    for (var q = 0; q < m; q++) {
                        var otherLengths = lengthsThatFit(workboard, p, q);
                        if (otherLengths.length > 0) {
                            var maxLength = otherLengths[otherLengths.length - 1];
                            maxProduct = Math.max(maxProduct, productOfLengths(lengths[k], maxLength));
                        }
                    }
                }
            }
        }
    }
    console.log(maxProduct);
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});