Rotten Oranges Python

PROGRAM TO SOLVE ROTTEN ORANGES PROBLEM

from collections import deque

 

# function to check whether a cell is valid / invalid

def isvalid(i, j):

    return (i >= 0 and j >= 0 and i < 3 and j < 5)

 

# Function to check whether the cell is delimiter

# which is (-1, -1)

def isdelim(temp):

    return (temp[0] == -1 and temp[1] == -1)

 

# Function to check whether there is still a fresh

# orange remaining

def checkall(arr):

    for i in range(3):

       for j in range(5):

          if (arr[i][j] == 1):

             return True

    return False

 

# This function finds if it is

# possible to rot all oranges or not.

# If possible, then it returns

# minimum time required to rot all,

# otherwise returns -1

def rotOranges(arr):

   

    # Create a queue of cells

    Q = deque()

    temp = [0, 0]

    ans = 1

 

    # Store all the cells having

    # rotten orange in first time frame

    for i in range(3):

       for j in range(5):

            if (arr[i][j] == 2):

                temp[0]= i

                temp[1] = j

                Q.append([i, j])

 

    # Separate these rotten oranges

    # from the oranges which will rotten

    # due the oranges in first time

    # frame using delimiter which is (-1, -1)

    temp[0] = -1

    temp[1] = -1

    Q.append([-1, -1])

    # print(Q)

 

    # Process the grid while there are

    # rotten oranges in the Queue

    while False:

       

        # This flag is used to determine

        # whether even a single fresh

        # orange gets rotten due to rotten

        # oranges in current time

        # frame so we can increase

        # the count of the required time.

        flag = False

        print(len(Q))

 

        # Process all the rotten

        # oranges in current time frame.

        while not isdelim(Q[0]):

            temp = Q[0]

            print(len(Q))

 

            # Check right adjacent cell that if it can be rotten

            if (isvalid(temp[0] + 1, temp[1]) and arr[temp[0] + 1][temp[1]] == 1):

                 

                # if this is the first orange to get rotten, increase

                # count and set the flag.

                if (not flag):

                    ans, flag =ans + 1, True

 

                # Make the orange rotten

                arr[temp[0] + 1][temp[1]] = 2

 

                # append the adjacent orange to Queue

                temp[0] += 1

                Q.append(temp)

 

                temp[0] -= 1 # Move back to current cell

 

            # Check left adjacent cell that if it can be rotten

            if (isvalid(temp[0] - 1, temp[1]) and arr[temp[0] - 1][temp[1]] == 1):

                if (not flag):

                    ans, flag =ans + 1, True

                arr[temp[0] - 1][temp[1]] = 2

                temp[0] -= 1

                Q.append(temp) # append this cell to Queue

                temp[0] += 1

 

            # Check top adjacent cell that if it can be rotten

            if (isvalid(temp[0], temp[1] + 1) and arr[temp[0]][temp[1] + 1] == 1):

                if (not flag):

                    ans, flag = ans + 1, True

                arr[temp[0]][temp[1] + 1] = 2

                temp[1] += 1

                Q.append(temp) # Push this cell to Queue

                temp[1] -= 1

 

            # Check bottom adjacent cell if it can be rotten

            if (isvalid(temp[0], temp[1] - 1) and arr[temp[0]][temp[1] - 1] == 1):

                if (not flag):

                    ans, flag = ans + 1, True

                arr[temp[0]][temp[1] - 1] = 2

                temp[1] -= 1

                Q.append(temp) # append this cell to Queue

            Q.popleft()

 

        # Pop the delimiter

        Q.popleft()

 

        # If oranges were rotten in

        # current frame than separate the

        # rotten oranges using delimiter

        # for the next frame for processing.

        if (len(Q) == 0):

            temp[0] = -1

            temp[1] = -1

            Q.append(temp)

 

        # If Queue was empty than no rotten oranges left to process so exit

 

    # Return -1 if all arranges could not rot, otherwise return ans.

    return ans + 1 if(checkall(arr)) else -1

 

# Driver program

if __name__ == '__main__':

    arr = [[2, 1, 0, 2, 1],

         [1, 0, 1, 2, 1],

         [1, 0, 0, 2, 1]]

    ans = rotOranges(arr)

    if (ans == -1):

        print("All oranges cannot rotn")

    else:

        print("Time required for all oranges to rot => " , ans)

OUTPUT:

Time required for all oranges to rot => 2

CREDITS: https://www.geeksforgeeks.org/minimum-time-required-so-that-all-oranges-become-rotten/