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

|

317 Discussions

|

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

  • patrickgao2020
     + 0 comments

    I finally got some code that worked! For my approach, I found every cell that was good. Then, I checked how far each arm could reach. The largest plus with the middle in that cell would then be the minimum size of arms. However, we also need to add all of the pluses that are smaller than that. Then, we can compare every plus with every other plus to see if they overlap. If they don't overlap, we record the product. Once we have all the products, we return the largest one.

    def twoPluses(grid):
    sizes = []
    middles = []
    products = []
    for row in range(len(grid)):
        for col in range(len(grid[0])):
            if grid[row][col] == "G":
                segments = []
                count = 0
                index = row
                while index >= 1 and grid[index - 1][col] == "G":
                    index -= 1
                    count += 1
                segments.append(count)
                count = 0
                index = row
                while index < len(grid) - 1 and grid[index + 1][col] == "G":
                    index += 1
                    count += 1
                segments.append(count)
                count = 0
                index = col
                while index >= 1 and grid[row][index - 1] == "G":
                    index -= 1
                    count += 1
                segments.append(count)
                count = 0
                index = col
                while index < len(grid[0]) - 1 and grid[row][index + 1] == "G":
                    index += 1
                    count += 1
                segments.append(count)
                for size in range(min(segments) + 1):
                    sizes.append(size)
                    middles.append((row, col))
    for p1 in range(len(middles)):
        for p2 in range(p1 + 1, len(middles)):
            plus1 = set()
            plus2 = set()
            row1 = middles[p1][0]
            col1 = middles[p1][1]
            row2 = middles[p2][0]
            col2 = middles[p2][1]
            for add in range(-sizes[p1], sizes[p1] + 1):
                plus1.add((row1 + add, col1))
                plus1.add((row1, col1 + add))
            for add in range(-sizes[p2], sizes[p2] + 1):
                plus2.add((row2 + add, col2))
                plus2.add((row2, col2 + add))
            product = (4 * sizes[p1] + 1) * (4 * sizes[p2] + 1)
            if plus1.isdisjoint(plus2):
                products.append(product)
    if products:
        return max(products)
    return 0

Join us

Create a HackerRank account

Be part of a 26 million-strong community of developers

Already have an account?Log in