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

  • 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)