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

|

316 Discussions

|

  • 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

  • lewigetu4
     + 0 comments

    It took me over a day figuring this out. I finally devised a working algorithm while I was thinking about it at work. These problems are all about solving the math (getting exactly how the algorithm works). Once I have the algorithm down, it took me just 1-2 hours for actual implementation. Trying to just code a solution to these problems without a working plan (which I tried initially) will be a disaster.

    My solution uses brute force. It essentially tries all possible permutations and pick the best one. My approach is to use the center to slowly expand out and check for 'G'. It'll be too much to explain everything but if you're interested, you can take a look at the code. Coded in python:

    import math
import os
import random
import re
import sys

def codify(n):
    my_str = str(n)
    if n<10:
        my_str = "0" + str(n)
        
    return my_str
		
def get_max_val(my_dict):
    k = ""
    v = -1
    my_max = -1
    for center, size in my_dict.items():
        if size>my_max:
            my_max=size
            k = center
            v = size
    
    return k, v

def get_list(center, size):
    my_list = [center]
    i = int(center[0: 2])
    j = int(center[2:])  
    length = int((size-1)/4)
    for n in range(1, length+1):
        my_list.append(codify(i+n)+codify(j))
    for n in range(1, length+1):
        my_list.append(codify(i-n)+codify(j))
    for n in range(1, length+1):
        my_list.append(codify(i)+codify(j+n))
    for n in range(1, length+1):
        my_list.append(codify(i)+codify(j-n))
        
    return my_list
		
def twoPluses(grid):
    limit = 1
    area_list = []
    while limit<16:
        row_len = len(grid)
        visited = dict()
        for i in range(row_len):
            col_len = len(grid[0])
            for j in range(col_len):
                n=0
                while n<limit:
                    if i+n<row_len and i-n>=0 and j+n<col_len and j-n>=0 and grid[i+n][j]=='G' and grid[i-n][j]=='G' and grid[i][j+n]=='G' and grid[i][j-n]=='G':
                        visited[codify(i)+codify(j)] = n*4 + 1
                        n += 1
                    else:
                        break
        
        perm = []
        for center, size in visited.items():
            visited_copy = visited.copy()
            visited_copy.pop(center)
            list1 = get_list(center, size)
            stop = False
            while not stop:
                k, v = get_max_val(visited_copy)
                visited_copy.pop(k)
                list2 = get_list(k, v)
                overlap = False                  
                for cell in list1:
                    if cell in list2:
                        overlap = True
                        break
                if not overlap:
                    stop = True                      
                    perm.append(size*v)
                    
                if len(visited_copy) == 0:
                    stop = True
        
        
        area_list.append(max(perm))
        limit += 1
        
    return max(area_list)