Find the biggest black square from an N*N matrix of black or white squares

Question:

Find the biggest black square from an N*N matrix of squares. 1 means it’s black, 0 means it’s white. Output should be the list of squares which forms the largest black square.

Input     : ‘{0#1#1#1#0#1#0#1,1#0#1#0#0#0#0#1,0#0#0#1#0#1#0#0,1#1#1#1#1#0#0#1,1#1#1#1#0#1#1#1,1#1#1#1#0#1#1#1,1#1#1#1#1#1#1#1,1#1#0#1#0#0#1#1}’

Output    :    {(3#0,3#1,3#2,3#3),(4#0,4#1,4#2,4#3),(5#0,5#1,5#2,5#3),(6#0,6#1,6#2,6#3)}

 

Solution(Python):

    # Author            :        Sreejith Sreekantan
    # Description        :        

    #                         Find the biggest black square from an N*N matrix of squares. 1 means it's black, 0 means it's white
    #                         Input     : '{0#1#1#1#0#1#0#1,1#0#1#0#0#0#0#1,0#0#0#1#0#1#0#0,1#1#1#1#1#0#0#1,1#1#1#1#0#1#1#1,1#1#1#1#0#1#1#1,1#1#1#1#1#1#1#1,1#1#0#1#0#0#1#1}'
    #                         Output    :    {(3#0,3#1,3#2,3#3),(4#0,4#1,4#2,4#3),(5#0,5#1,5#2,5#3),(6#0,6#1,6#2,6#3)}
    

#!/usr/bin/python

def largestSquareAt(sq, i, j, k=1):
    if not ( i+k<len(sq) and="" j+k<len(sq[i])="" ):=""   =""    =""  return="" 0=""  for="" x="" in="" range(0,k):=""  if="" sq[i+x][j+k-1]="='0':" y="" sq[i+k-1][j+y]="='0':" 1="" +="" largestsquareat(sq,="" i,="" j,="" k+1)  =""  ="" def="" biggestsquare(input1):="" len(input1)="=0" or="" not="" (="" input1.count('{')="=input1.count('}')" )="" :="" ''=""  i="str(input1)"  j="i" for="" j]=""  resx="-1"  rexy="-1"  ressize="-1"  res="[]" range(0,len(j)):=""  res.append([])="" range(0,len(j[x])):=""  res[x].append(largestsquareat(j,="" x,="" y))="" ressize<res[x][y]:=""  resy="y"  resstring="" ressize="">0:                                
        resstring = "{"
        for x in range(resx,resx+ressize):
            if x>resx:
                resstring += ","
            resstring += "("
            for y in range(resy,resy+ressize):
                if y>resy:
                    resstring += ","
                resstring += (str(x)+"#"+str(y))
            resstring += ")"    
        resstring += "}"
    
    return resstring  

input = '{0#1#1#0,0#1#1#1,0#1#1#1,1#1#1#1}'
input1 = '{0#1#1#1#0#1#0#1,1#0#1#0#0#0#0#1,0#0#0#1#0#1#0#0,1#1#1#1#1#0#0#1,1#1#1#1#0#1#1#1,1#1#1#1#0#1#1#1,1#1#1#1#1#1#1#1,1#1#0#1#0#0#1#1}'
input2 = '{0#1#1#1#0#1#0#1,1#0#1#0#0#0#0#1,0#0#0#1#0#1#0#0,1#1#1#1#1#0#0#1,1#1#0#1#0#1#1#1,1#1#1#1#0#1#1#1,1#1#1#1#1#1#1#1,1#1#0#1#0#0#1#1}'
input3= '{0#1#1#1#0#1#0#1,1#0#1#0#0#0#0#1,0#0#0#1#0#1#0#0,1#1#1#1#1#0#0#1,0#1#0#1#0#1#1#1,1#1#1#1#0#1#1#1,1#1#1#1#1#1#1#1,1#1#0#1#0#0#1#1}'
input4 = '{0#0#0#0,0#0#0#0,0#0#0#0,0#0#0#0}'
print biggestSquare('')    
print biggestSquare(input1)    
print biggestSquare(input2)        
print biggestSquare(input3)        
print biggestSquare(input4)

Published by

Sreejith

A strong believer of: 1. Knowledge is power 2. Progress comes from proper application of knowledge 3. Reverent attains wisdom 4. For one's own salvation, and for the welfare of the world

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s