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

|

318 Discussions

|

  • 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;
}

  • yeungsze
     + 0 comments

    An alternative Python solution:

    def twoPluses(grid):
    n = len(grid)
    m = len(grid[0])
    # getting the list of coordinates of all good cells
    goodcells = [(r, c) for r in range(n) for c in range(m) if grid[r][c] == 'G']
    # initialize the list of crosses of single cells
    pluses = [{cell} for cell in goodcells]
    # finding the larger crosses
    for r, c in goodcells:
        if 0 < r < n and 0 < c < m:
            for i in range(1, min(r, c, n - r - 1, m - c - 1) + 1):
                four_cells = [(r + i, c), (r - i, c), (r, c - i), (r, c + i)]
                if all(cell in goodcells for cell in four_cells):
                    h_line = set((r, x) for x in range(c - i, c + i + 1))
                    v_line = set((y, c) for y in range(r - i, r + i + 1))
                    pluses.append(h_line | v_line)
                else:
                    break
    pluses = sorted(pluses, key = len, reverse = True)
    max_2 = 0
    while len(pluses) > 1:
        plus_a = pluses.pop(0)
        for plus_b in pluses:
            if plus_a.isdisjoint(plus_b):
                max_2 = max(max_2, len(plus_a) * len(plus_b))
                break
    return max_2

  • yeungsze
     + 1 comment

    My Python solution:

    def twoPluses(grid):
    # Write your code here
    n = len(grid)
    m = len(grid[0])
    pluses = []
    # finding all the possible crosses
    for r in range(n):
        for c in range(m):
            # setting the possible sizes for drawing crosses in each cell
            for i in range(min(r, c, n - r - 1, m - c - 1) + 1):
                # checking whether all cells for crosses are good
                if all(grid[j][c] == 'G' for j in range(r - i, r + i + 1)) \
                and all(grid[r][k] == 'G' for k in range(c - i, c + i + 1)):
                    # record all the coordinates of the valid cross
                    h_line = set((r, x) for x in range(c - i, c + i + 1))
                    v_line = set((y, c) for y in range(r - i, r + i + 1))
                    pluses.append(h_line | v_line)
    pluses = sorted(pluses, key = len, reverse = True)
    # finding the maximum product of 2 crosses
    max_2 = 0
    while len(pluses) > 1:
        plus_a = pluses.pop(0)
        for plus_b in pluses:
            # check whether the 2 crosses are not overlapped
            if plus_a.isdisjoint(plus_b):
                max_2 = max(max_2, len(plus_a) * len(plus_b))
    return max_2

  • tuan_lq121100
     + 0 comments

    After all, the best method is brute force. The idea is simple, you only need to travese the grid to find possible plus and then loop through these valid pluses to get the max product. Here is my js for the function. It might not be optimized, so feel free to upgrade it further.

    function isCellValid(grid, i, j) {
    if(!grid[i] || !grid[i][j]) return false;
    if(grid[i][j] === 'G') return true;
    else return false;
}
function isPlusOverlap(plus1, plus2) {
    const {i : i1, j : j1, count : count1} = plus1;
    const {i : i2, j : j2, count : count2} = plus2;
    let plusArr1 = [];
    let plusArr2 = [];
    for(let i=i1-count1+1;i<=i1+count1-1;i++){
        plusArr1.push({i, j:j1});
    }
    for(let j=j1-count1+1;j<=j1+count1;j++){
        plusArr1.push({i:i1, j});
    }
    for(let i=i2-count2+1;i<=i2+count2-1;i++){
        plusArr2.push({i, j:j2});
    }
    for(let j=j2-count2+1;j<=j2+count2-1;j++){
        plusArr2.push({i:i2, j});
    }
    const intersection = plusArr1.reduce((acc, value) => {
        let filteredArr = plusArr2.filter(obj => obj.i === value.i && obj.j === value.j)
        if (filteredArr.length > 0) {
            acc.push([...filteredArr]);
        }
        return acc;
    }, []);
    if(intersection.length > 0) return true;
    return false;
}

function twoPluses(grid) {
    // Write your code here
    let h = grid.length;
    let w = grid[0].length;
    let plusses = [];
    let output = 0;
    for(let i=1;i<h-1;i++){
        for(let j=1;j<w-1;j++){
            if(isCellValid(grid, i, j)){
                let count = 0;
                while(
                    isCellValid(grid, i-count,j) 
                    && isCellValid(grid, i+count, j)
                    && isCellValid(grid, i, j-count) 
                    && isCellValid(grid, i, j+count)
                    ){
                        count++;
                        plusses.push({
                            i, j, count
                        })
                    }

            }
        }
    }
    for(let k=0; k<plusses.length-1;k++) {
        let plus = plusses[k];
        let product = 0;
        for(let h=k+1; h<plusses.length; h++){
            let plus2 = plusses[h];
            if(!isPlusOverlap(plus, plus2)) {
                let tempProduct = (1+ 4*(plus.count-1)) * (1+ 4*(plus2.count-1));
                if(product < tempProduct) {
                    product = tempProduct;
                    console.log(plus, plus2, product);
                }
            }
        }
        if(output < product) output = product;
    }
    return output;
}