We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Implementation
  4. Ema's Supercomputer
  5. Discussions

Ema's Supercomputer

Sort by

recency

|

321 Discussions

|

  • CS_2212256_T
     + 0 comments
    #!/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()

  • ds1b_1641540100
     + 0 comments
    #!/bin/python3

import math
import os
import random
import re
import sys

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

def twoPluses(grid):
    # Write your code here
    n, m = len(grid), len(grid[0])
    up = [[0]*m for _ in range(n)]
    down = [[0]*m for _ in range(n)]
    left = [[0]*m for _ in range(n)]
    right = [[0]*m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if grid[i][j] == 'G':
                up[i][j] = 1 + (up[i-1][j] if i > 0 else 0)
                left[i][j] = 1 + (left[i][j-1] if j > 0 else 0)
    for i in reversed(range(n)):
        for j in reversed(range(m)):
            if grid[i][j] == 'G':
                down[i][j] = 1 + (down[i+1][j] if i < n-1 else 0)
                right[i][j] = 1 + (right[i][j+1] if j < m-1 else 0)

    pluses = []
    for i in range(n):
        for j in range(m):
            if grid[i][j] == 'G':
                arm_len = min(up[i][j], down[i][j], left[i][j], right[i][j]) - 1
                for length in range(arm_len + 1):
                    pluses.append((i, j, length, 4*length + 1))  # (row, col, arm, area)    
    def cells_of_plus(r, c, arm):
        cells = {(r, c)}
        for k in range(1, arm+1):
            cells.add((r+k, c))
            cells.add((r-k, c))
            cells.add((r, c+k))
            cells.add((r, c-k))
        return cells

    max_product = 0
    for i in range(len(pluses)):
        r1, c1, arm1, area1 = pluses[i]
        cells1 = cells_of_plus(r1, c1, arm1)
        for j in range(i+1, len(pluses)):
            r2, c2, arm2, area2 = pluses[j]
            cells2 = cells_of_plus(r2, c2, arm2)
            if cells1.isdisjoint(cells2):
                product = area1 * area2
                if product > max_product:
                    max_product = product
    return max_product


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

    first_multiple_input = input().rstrip().split()

    n = int(first_multiple_input[0])

    m = int(first_multiple_input[1])

    grid = []

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

    result = twoPluses(grid)

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

    fptr.close()

  • ds1b_1641540100
     + 0 comments

    Ema's Supercomputer solution in Python

    #!/bin/python3

import math
import os
import random
import re
import sys
import copy

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

class ValidPlus:
    def __init__(self):
        self.area = 1
        self.length = 1
        self.cells = []

    def addCell(self, cell):
        self.cells.append(cell)

class Cell:

    def __init__(self, row, column):
        self.row = row
        self.column = column

    def __str__(self):
        return str(self.row) + str(self.column)

    def __hash__(self):
        return hash(str(self))

    def __eq__(self, other):
        return self.row == other.row and self.column == other.column

    def __gt__(self, other):
        return self.row > other.row and self.column > other.column

    def __lt__(self, other):
        return self.row < other.row and self.column < other.column


if __name__ == '__main__':
    n, m = input().strip().split(' ')
    n, m = [int(n), int(m)]
    grid = []
    grid_i = 0
    for grid_i in range(n):
        grid_t = str(input().strip())
        grid.append(grid_t)
    validPluses = []
    for i in range(n):
        for j in range(m):
            current_cell = grid[i][j]
            if current_cell == 'G':
                there_is_a_good_cell = True
                validPlus = ValidPlus()
                length = 1
                validPlus.addCell(Cell(i,j))
                validPluses.append(validPlus)
                while there_is_a_good_cell:
                    if (i - length >= 0 and grid[i - length][j] == 'G') and (i + length < n and grid[i + length][j] == 'G') and (j - length >= 0 and grid[i][j - length] == 'G') and (j + length < m and grid[i][j + length] == 'G'):
                        new_valid_plus = copy.deepcopy(validPlus)
                        new_valid_plus.addCell(Cell(i - length, j))
                        new_valid_plus.addCell(Cell(i + length, j))
                        new_valid_plus.addCell(Cell(i, j - length))
                        new_valid_plus.addCell(Cell(i, j + length))
                        length += 1
                        new_valid_plus.area = 1 + (4 * (length - 1))
                        new_valid_plus.length = length
                        validPluses.append(new_valid_plus)
                        validPlus = copy.deepcopy(new_valid_plus)
                    else:
                        there_is_a_good_cell = False
    max_area = 0
    for i in range(len(validPluses)):
        current_valid_plus = validPluses[i]
        for j in range(i + 1, len(validPluses)):
            other_valid_plus = validPluses[j]
            current_area = current_valid_plus.area * other_valid_plus.area
            if current_area > max_area:
                current_cells = current_valid_plus.cells
                other_cells = other_valid_plus.cells
                common_cells = set(current_cells) - (set(current_cells) - set(other_cells))
                if len(common_cells) == 0:
                    max_area = current_area
    print(max_area)

  • yashdeora98294
     + 0 comments

    Here is problem solution in python java c++ c and Javascript - https://programmingoneonone.com/hackerrank-emas-supercomputer-problem-solution.html

  • kusakus
     + 0 comments

    /* Helper functions. */ public static String point(int x, int y) { return String.format("%d,%d", x, y); } public static String point(int[] p) { return String.format("%d,%d", p[0], p[1]); } public static int[] add(int[] a, int[] b) { return new int[]{a[0] + b[0], a[1] + b[1]}; }

    /*
 * Returns a list of sets where each set 
 * contains cell positions that make up a valid plus.
 * Starting at center x, y expand outwards as much as possible.
 * We save each plus we find in order to compare all possible pluses.
*/
public static List<Set<String>> allPluses(int x, int y, List<String> grid, Set<String> bad)
{
    List<Set<String>> allCombos = new ArrayList<>();

    int N = grid.size();
    int M = grid.get(0).length();
    int[][] directions = {
        {-1, 0}, //up
        {1, 0}, //down
        {0, -1}, //left
        {0, 1} //right
    };

    int[] up = new int[]{x, y};
    int[] down = new int[]{x, y};
    int[] left = new int[]{x, y};
    int[] right = new int[]{x, y};

    Set<String> cells = new HashSet<>();
    while(up[0] >= 0 && down[0] < N && left[1] >= 0 && right[1] < M)
    {
        if(bad.contains(point(up)) || bad.contains(point(left)) || bad.contains(point(right)) ||
                bad.contains(point(down)))
        {
            break;
        }

        Set<String> curr = new HashSet<>(cells);
        curr.add(point(up));
        curr.add(point(down));
        curr.add(point(left));
        curr.add(point(right));
        allCombos.add(curr);
        cells.addAll(curr);

        up = add(up, directions[0]);
        down = add(down, directions[1]);
        left = add(left, directions[2]);
        right = add(right, directions[3]);
    }
    return allCombos;
}

public static int twoPluses(List<String> grid) {
// Write your code here
final int N = grid.size();
final int M = grid.get(0).length();

//create set of all positions that are bad cells.
Set<String> badCells = new HashSet<>();
for(int x = 0; x < N; x++)
    for(int y = 0; y < M; y++)
        if(grid.get(x).charAt(y) != 'G')
            badCells.add(point(x,y));

//find every possible plus you can make for a cell.
Map<String, List<Set<String>>> pluses = new HashMap<>();
for(int x = 0; x < N; x++)
    for(int y = 0; y < M; y++)
        pluses.put(point(x,y), allPluses(x, y, grid, badCells));

/*
 * for every 2 cells compare each possible plus combination
 * keep the max.
*/
int maxArea = 0;
for(String cell_one : pluses.keySet())
    for(String cell_two : pluses.keySet())
        if(!cell_one.equals(cell_two))
            for(Set<String> c1_plus : pluses.get(cell_one))
                for(Set<String> c2_plus : pluses.get(cell_two))
                    if(Collections.disjoint(c1_plus, c2_plus))
                        maxArea = Math.max(maxArea, c1_plus.size() * c2_plus.size());

return maxArea;
}