Discussion on Ema's Supercomputer Challenge

Sort by

recency

|

325 Discussions

|

3 days ago+ 0 comments

Respectfully, this problem is not "medium", it's freaking hard! (ಥ﹏ಥ)

Heres is my c++ solutions, hope is helps someone.

struct Plus {
    int area;
    vector<pair<int,int>> cells;
};

vector<Plus> allPlussesAt(int y, int x, const vector<string>& grid) {
    vector<Plus> result;
    if (grid[y][x] != 'G') return result;

    int arm = 0;
    int rows = grid.size(), cols = grid[0].size();

    while (y-arm >= 0 && y+arm < rows &&
           x-arm >= 0 && x+arm < cols &&
           grid[y-arm][x] == 'G' &&
           grid[y+arm][x] == 'G' &&
           grid[y][x-arm] == 'G' &&
           grid[y][x+arm] == 'G') {
        
        vector<pair<int,int>> cells;
        cells.push_back({y,x});
        for (int k=1; k<=arm; k++) {
            cells.push_back({y-k,x});
            cells.push_back({y+k,x});
            cells.push_back({y,x-k});
            cells.push_back({y,x+k});
        }
        
        result.push_back({1 + 4*arm, cells});
        arm++;
    }

    return result;
}

vector<Plus> allPlusses(const vector<string>& grid) {
    vector<Plus> plusses;
    for (int y=0; y<grid.size(); y++) {
        for (int x=0; x<grid[0].size(); x++) {
            auto p = allPlussesAt(y, x, grid);
            plusses.insert(plusses.end(), p.begin(), p.end());
        }
    }
    return plusses;
}

bool overlap(const Plus& a, const Plus& b) {
    for (auto &cellA : a.cells) {
        for (auto &cellB : b.cells) {
            if (cellA == cellB) return true;
        }
    }
    return false;
}

int maxPlusAreaAt(int y, int x, const vector<string>& grid) {
    if (grid[y][x] != 'G') return 0;

    int arm = 0;
    int rows = grid.size(), cols = grid[0].size();

    while (y-arm >= 0 && y+arm < rows &&
           x-arm >= 0 && x+arm < cols &&
           grid[y-arm][x] == 'G' &&
           grid[y+arm][x] == 'G' &&
           grid[y][x-arm] == 'G' &&
           grid[y][x+arm] == 'G') {
        arm++;
    }
    arm--; 
    
    return 1 + 4*arm;
}

int twoPluses(vector<string> grid) {
    vector<Plus> plusses = allPlusses(grid);

    int best = 0;
    for (int i=0; i<plusses.size(); i++) {
        for (int j=i+1; j<plusses.size(); j++) {
            if (!overlap(plusses[i], plusses[j])) {
                best = max(best, plusses[i].area * plusses[j].area);
            }
        }
    }

    return best;
}

2 weeks ago+ 0 comments

MY SOLUTION IN PHP

  $totalrow = count($grid);
    
    $columnArr = array();
    $allIndex = array();

    for ($i=0; $i <$totalrow ; $i++) { 
         $arr = str_split($grid[$i]);
         $columnArr[]  = $arr;
    }
    $columnLength = count($columnArr[0]);


    for ($i=1; $i < $totalrow-1; $i++) { 

        for ($j=1; $j <$columnLength-1 ; $j++) { 
            $rowis = $i+1;
            $columnIs = $j+1;
            
            $down = $totalrow-$rowis;
            $up = $totalrow - ($down +1);
            $right = $columnLength - ($columnIs);
            $left = $columnLength - ($right+1);
            $min = min($down,$up,$right,$left);
            
            
            for ($k=$min; $k >0 ; $k--) { 
                
                 $totalValue = 0;
                 $flag = 0;
                 $indexArr = array();
                 $innerArr = array();
                 for ($l=0; $l <$k; $l++) { 
                     
                     
                      $val = $l+1;
                      $newupRow = $rowis -$val-1;
                      $newDownRow = $rowis+$val-1;
                     
                      $columnUpValue = $columnArr[$newupRow][$columnIs-1];
                     

                      $columnDownvalue = $columnArr[$newDownRow][$columnIs-1];
                     

                     
                      $colLeft = ($columnIs-1)-($l+1);
                       $columnLeftValue = $columnArr[$rowis-1][$colLeft];
                      

                       $colRight = ($columnIs-1)+($l+1);
                        $columnRightValue = $columnArr[$rowis-1][$colRight];
                     

                       if($columnUpValue === 'G' && $columnDownvalue === 'G' && $columnLeftValue === 'G' && $columnRightValue === 'G' && $columnArr[$i][$j] === 'G' && $l === 0 )
                        {
                            $flag = 1;
                            $totalValue+= 4;
                       
                         $innerArr[] =$newupRow.','.$columnIs-1;
                         $innerArr[] =$newDownRow.','.$columnIs-1;
                         $innerArr[] =($rowis-1).','.$colLeft;
                         $innerArr[] =($rowis-1).','.$colRight;
                         $innerArr[] =$i.','.$j;

                        }
                        else if($columnUpValue === 'G' && $columnDownvalue === 'G' && $columnLeftValue === 'G' && $columnRightValue === 'G'  && $columnArr[$i][$j] === 'G' && $flag === 1 )
                        {
                            $flag = 1;
                            $totalValue+= 4;
                        
                        $innerArr[] =$newupRow.','.$columnIs-1;
                         $innerArr[] =$newDownRow.','.$columnIs-1;
                         $innerArr[] =($rowis-1).','.$colLeft;
                         $innerArr[] =($rowis-1).','.$colRight;
                       
                       
                        }
                         else
                        {
                            break;
                        }

                       if(count($innerArr)>0)
                       {
                            $indexArr[] = $innerArr;

                       } 


                 }
                
                
                   if(count($indexArr)>0)
                       {
                            $allIndex[] = $indexArr;

                       } 
                  
                


            }
            
        }

        
    }


 
    

$result = array();
foreach ($allIndex as $outer) {
    foreach ($outer as $inner) {
        $result[] = $inner;
    }
}
    

    $unique = [];
foreach ($result as $sub) {
    $temp = $sub;
    sort($temp);                
    $key = json_encode($temp);  
    $unique[$key] = $sub;    
}


$result = array_values($unique);


$resultLen = count($result);

$ans = 0;
if ($resultLen == 1) {
    $ans = count($result[0]);
}
else
{
    $productArray = [];
for ($i=0; $i < $resultLen-1; $i++) { 
    
    $first = $result[$i];
    $firstLen = count($first);
    
     for ($j=$i+1; $j < $resultLen ; $j++) { 
        $second = $result[$j];
        $secondLen = count($second);

        $common = array_intersect($first, $second);

        if (!empty($common)) {
            $productArray[] = max($firstLen,$secondLen);
          
        } else {
            $secondLen = count($second);
            $productArray[] = $firstLen*$secondLen;
           
        }

     }
}

$ans = count($productArray) > 0 ? max($productArray) : 1;

}

return $ans;

3 weeks ago+ 0 comments

If you fail only a few cases, consider smaller size pluses with the same center, as they might not overlapse while the biggest one does. Also, you might be curious about how much pearls are worth when selecting decorative elements for your design.

4 weeks ago+ 0 comments

Since the input size is very small, we can use brute force approach:

TLDR:

for each G point, traverse in all four directions setp by step (ex: at step 2 you visit all the points which are at dist. 2 in all directions) till all the points in the step are valid G points and collect them at each step
sort them based on len in desc order, then check for all the combinations of such non overlapping plus points and find the max aread

CODE

def twoPluses(grid):
    # Write your code here
    n,m = len(grid), len(grid[0])
    g_points = []
    pluses = []
    
    for i in range(n):
        for j in range(m):
            if grid[i][j] == 'G': 
                g_points.append((i, j))
                pluses.append({(i, j)})
    
    def getPluses(i, j):
        cur_plus = {(i, j)}                
        for k in range(1, min(n-i, m-j, i+1, j+1)):
            points = ((i-k, j), (i+k, j), (i, j-k), (i, j+k))
            for x,y in points:
                if grid[x][y] != 'G': 
                    return
            cur_plus.update(points)
            pluses.append(cur_plus.copy())
    
    for i,j in g_points:
        getPluses(i, j)
                    
    pluses.sort(key=len, reverse=True) 
    
    def getRes(pluses):
        res = -1
        for i in range(len(pluses)):
            for j in range(i+1, len(pluses)):
                if len(pluses[i].intersection(pluses[j])) == 0:
                    res = max(res, len(pluses[i])*len(pluses[j]))
        return res
				`
    
    return getRes(pluses)

Initial thoughts:

Approach 1:

start at each G point
traverse in all four directions at once (mark G to say -1 to identify as visited, so that there won't be any intersection with others)
now we have lenghts of all such pluses
find the top two and do product. Either sort the lenghts array or use heap and maintain only top two

Flaws with this approach:

Future G point, might need the current one (as it can be in the plus path of future G) since we are marking as -1, this will be ignored and we might loose the longest plus

Approach 2:

Okay, so what if we try to find the pluses that can be formed from each G point? find the top two such set of points without any intersection

find all the G points
from each G point, traverse in all the directions, collect all the points
sort the collection of points based on length, find top two with zero intersection and do a product of it

Flaws:

x = max(side of plus you can reach in all 4 directions), area = 4*x +1 ex: x=2, area = 4*2+1 = 9 say pluses of x=2 & x=3 are next to each other with one overlapping G point, then maxArea = area(3)*1 (as there is no other plus points) = 13 but if we somehow make x=3 to take only two G's in all directions? then maxArea = area(x=2)*area(x=2) = 81

Approach 3:

So now instead of considering only the points in the max plus path of each g point, consider all the plus points for each length.

Ex: for x=3, we will have in total of 4 collections points while going thorugh the directions, i.e start from x = 0 --> x=1 --> x=2 --> x=3 for a given G point

Now for x=2 & x=3 points, we have 0,1,2 & 0,1,2,3 lengths of collection points for each G point. Now sort the collection of plus points, find max among all the given pairs (not just top two non intersection points, as 2x1 & 3x2 can have intersection, then top two aread will become 1x1 * 3x2, but max is 2x1 *2X2)

2 months ago+ 1 comment

#!/bin/python3

import math
import os
import random
import re
import sys
from itertools import combinations

# Complete the 'twoPluses' function below.
# The function is expected to return an INTEGER.
# The function accepts STRING_ARRAY grid as parameter.

def twoPluses(grid):
    h, w = len(grid), len(grid[0])
    pluses = []

    def is_good(r, c):
        return 0 <= r < h and 0 <= c < w and grid[r][c] == 'G'

    # Generate all valid pluses
    for r in range(h):
        for c in range(w):
            if not is_good(r, c):
                continue
            size = 0
            occupied = {(r, c)}
            pluses.append((1, occupied.copy()))  # Add single cell plus
            while True:
                size += 1
                cells = {(r+i, c) for i in range(-size, size+1)} | {(r, c+i) for i in range(-size, size+1)}
                if all(is_good(x, y) for x, y in cells):
                    pluses.append((len(cells), cells.copy()))
                else:
                    break

    # Try all combinations of 2 pluses and find max area product of non-overlapping ones
    max_product = 0
    for (area1, cells1), (area2, cells2) in combinations(pluses, 2):
        if cells1.isdisjoint(cells2):
            max_product = max(max_product, area1 * area2)

    return max_product if max_product else 1  # At least one plus is guaranteed

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    nm = input().split()
    n = int(nm[0])
    m = int(nm[1])

    grid = []
    for _ in range(n):
        grid_item = input()
        grid.append(grid_item)

    result = twoPluses(grid)

    fptr.write(str(result) + '\n')
    fptr.close()

Sort by

|

325 Discussions

|

Cookie support is required to access HackerRank