Home Programming CodeVita Fill The Cube Solution - Codevita

[SOLVED] Fill The Cube Solution – Codevita

Fill The Cube Solution – Codevita

Problem Description

A company manufactures walls which can be directly implanted at the site. The company uses small square bricks of material C and material D which have similar looks but have a huge difference in quality. The company manufactures walls of square shapes only to optimize their costs.

A novice employee created a square wall using bricks of material C and D. However, the client had asked the wall to be made of only high-quality material – material C.

To solve this problem, they will place the wall in a special furnace and heat it such that the material D melts and only material C remains. Material C brick will move down due to gravity if a material D brick below it melts. The new empty space created will be filled by new material C square walls. They also want to use biggest possible C square wall while building the final wall. For this they will position the wall in the furnace in an optimal way i.e. rotate by 90-degrees any number of times, if required, such that the biggest space possible for new material C wall is created. No rotations are possible when the furnace starts heating.

Given the structure of the original wall created by the novice employee, you need to find out the size of the new C square wall which can be fitted in the final wall which will be delivered to the client.

Constraints

[sg_popup id=”undefined” event=”onLoad”][/sg_popup]

1 < N < 100

Input

First Line will provide the size of the original wall N.

Next N lines will provide the type of material (C and D) used for each brick by the novice employee.

Output

Size of the biggest possible C square wall which can be fitted in the final wall.

Time Limit

1

Subscribe to our newsletter!

[newsletter_form type=”minimal” lists=”undefined” button_color=”undefined”]

Examples

Example 1

Input

4

C D C D

C C D C

D D D D

C D D D

Output

3

Explanation

If the wall is placed with its left side at the bottom, space for a new C wall of size 2×2 can be created. This can be visualized as follows

D C D D

C D D D

D C D D

C C D C

The melted bricks can be visualized as follows

– – – –

– C – –

C C – –

C C – C

Hence, the maximum wall size that can be replaced is 2×2.

If the wall is placed as it is with its original bottom side at the bottom, space for a new C wall of size 3×3 can be created. Post melting, this can be visualized as follows.

– – – –

C – – –

C – – –

C C C C

Hence, the maximum wall size that can be replaced is 3×3 in this approach.

Since no rotations followed by heating is going to a yield a space greater than 3×3, the output is 3.

Example 2

Input

7

C D D C D D D

C D D C D D D

D D D D D D C

D C D C D D D

D D D C D C D

C D D C D C C

C D C D C C C

Output

5

Explanation

If the wall is placed with its left side at the bottom, a space for new C wall of size 5×5 can be created. This can be visualized as follows

D D C D D C C

D D D D C C C

D D D D D D C

C C D C C C D

D D D D D D C

D D D C D D D

C C D D D C C

When this orientation of the wall is heated, a space for new C wall of size 5×5 is created after the D bricks melt

_ _ _ _ _ _ _

_ _ _ _ _ _ _

_ _ _ _ _ _C

_ _ _ _ _ _ C

_ _ _ _ _ C C

C C _ C C C C

C C C C C C C

Whereas, if the rotation was not done, the wall formed after the D bricks melt will be as follows

_ _ _ _ _ _ _

_ _ _ _ _ _ _

_ _ _ C _ _ _

C _ _ C _ _ _

C _ _ C _ _ C

C _ _ C _ C C

C C C C C C C

When this orientation of the wall is heated, a space for new C wall of size 3×3 only is created after the D bricks melt

Hence rotation is important and correct answer is 5×5

Since no rotations followed by heating is going to yield a space greater than 5×5, the output is 5.

[sociallocker id=”784″][/sociallocker]

3 COMMENTS

  1. Fill the Cube:

    from array import *
    import copy

    # Function to print the matrix
    def displayMatrix(mat):
    num=len(mat)
    for i in range(num):

    for j in range(num):

    print (mat[i][j], end = ‘ ‘)
    print (“\n”)

    #Function to rotate matrix
    def rotateMatrix(mat):
    N=len(mat)
    # Consider all squares one by one
    for x in range(0, int(N / 2)):

    # Consider elements in group
    # of 4 in current square
    for y in range(x, N-x-1):

    # store current cell in temp variable
    temp = mat[x][y]

    # move values from right to top
    mat[x][y] = mat[y][N-1-x]

    # move values from bottom to right
    mat[y][N-1-x] = mat[N-1-x][N-1-y]

    # move values from left to bottom
    mat[N-1-x][N-1-y] = mat[N-1-y][x]

    # assign temp to left
    mat[N-1-y][x] = temp

    #Searching biggest square matrix size
    def print_max_sub_matrix(grid):

    size = len(grid)
    cache = [[0 for k in range(size)] for l in range(size)]

    for i in range(size):
    for j in range(size):
    if (grid[i][j] == 1):
    if i == 0 or j == 0:
    cache[i][j] = min(grid[i][j], 1)
    else:
    cache[i][j] = min(cache[i][j-1], cache[i-1][j],cache[i-1][j-1]) + 1
    else:
    cache[i][j] = 0

    max_in_cache = cache[0][0]

    for i in range(size):
    for j in range(size):
    if max_in_cache < cache[i][j]:
    max_in_cache = cache[i][j]

    return max_in_cache

    #Meltdown
    def melt(brick):
    num=len(brick)
    for i in range(num):
    for j in range(num):
    if brick[i][j]=='D':
    if i==0:
    brick[i][j]='x'
    for z in range(i, 0, -1):
    brick[z][j]=brick[z-1][j]
    brick[z-1][j]='x'

    for i in range(num):
    for j in range(num):
    if brick[i][j]=='x':
    brick[i][j]=1
    else:
    brick[i][j]=0

    #Input for original wall size
    print("Input")
    size = int(input())

    #Input for bricks
    array_input = []
    for x in range(size):
    array_input.append([y for y in input().split()])

    temp_arr = copy.deepcopy(array_input)
    melt(temp_arr)
    max1 = print_max_sub_matrix(temp_arr)

    #1st rotation
    rotateMatrix(array_input)
    temp_arr = copy.deepcopy(array_input)
    melt(temp_arr)
    max2 = print_max_sub_matrix(temp_arr)

    #2nd rotation
    rotateMatrix(array_input)
    temp_arr = copy.deepcopy(array_input)
    melt(temp_arr)
    max3 = print_max_sub_matrix(temp_arr)

    #3rd rotation
    rotateMatrix(array_input)
    temp_arr = copy.deepcopy(array_input)
    melt(temp_arr)
    max4 = print_max_sub_matrix(temp_arr)

    #Final output
    print("Output")
    print(max(max1, max2, max3, max4))

LEAVE A REPLY

Please enter your comment!
Please enter your name here

five × 1 =

Most Popular

5 Best Wireless Neckband under Rs. 2000 – October 2020

If you are looking for Best Wireless Neckband under 2000, then you are at right place. We have covered all best neckbands...

15 Best Easiest Programming Languages in the World in 2020

A programming language in today’s generation can really ace up one’s skill set and benefit you in the long run. Having said...

Carl Pei – “Thank You OnePlus”

Just with a simple "Thank You" message , Carl Pei on Friday left OnePlus. He was the Man behind the Success of...

What is cloud computing? Introduction to Cloud Computing

In this article we will talk about one of the most trending and important technologies, which is playing a pivotal in our...

Recent Comments