2020 CCC J5/Q2 Escape Room (Python) BFS Optimization

Question

Is there a way to optimize my code even further? I am trying to solve the 2020 CCC J5/Q2 question and I have passed all the test cases except for a few, which I am exceeding the time limit.

Link to the question (It is the last question) https://cemc.uwaterloo.ca/contests/computing/2020/ccc/juniorEF.pdf

#definitions
row = int(input())
column = int(input())
array = [list(map(int, input().split())) for x in range(row)]
area = row*column

#Setting the queue to only have -1
pathways = [-1]*(area+1)
emptyS = 0
currentPath = 0
inList = [False] * 1000001

#Setting the first number in the queue to equal the number at [0][0]
pathways[emptyS] = array[0][0]
emptyS += 1`enter code here`
#Checking if the number at [0][0] is the answer (the answer is the area of the array)
if pathways[currentPath] == area:
    print('yes')
    raise SystemExit(0)

#Using BFS to find the answer
#Looping until the queue hits -1
while pathways[currentPath] != -1:
    for x in range(1, row+1):
        if pathways[currentPath] % x == 0:
            for y in range(1, column+1):

#I wasn't sure how to add 1 to every index of my 2d array, so I added 1 in the for loop, and arrayMN is the actual index in my loop.
                arrayMN = array[x-1][y-1]
                if pathways[currentPath] == x*y:

                    #Checking if the value is equal to the answer
                    if arrayMN == area:
                        print("yes")
                        raise SystemExit(0)

                    #If it isn't equal, either replace the -1 in pathways with the number (add it to the queue) or don't add it to prevent a loop)
                    if inList[arrayMN] == False:
                        pathways[emptyS] = arrayMN
                        emptyS += 1
                        inList[arrayMN] = True
    currentPath += 1

#If none of the above works, it is not possible
print('no')

This is my first forum post, so if there are any things I can do to improve my posts, please let me know.

question from:https://stackoverflow.com/questions/65855914/2020-ccc-j5-q2-escape-room-python-bfs-optimization

Answer 1

Yes. Here are changes that I made to my own code that originally followed an algorithm similar to yours to finally get all tests to pass within time limit.

The inner for y loop is not necessary because the y position is already known once you know that pathways[currentPath] is divisible by x. You can get the value by: y = pathways[currentPath] // x and need to check that is not more than your number of columns you have by: y <= column before using it to calculate arrayMN.

The inner for x loop would not be necessary by turning array into a dictionary of cell value : row * column where value occurs pair. When you first get the input, for each value check if it's in the dictionary. If it is not, add a set containing its row * column value. If it is, just add the row * column value to the existing set. Now you can work backwards: start from the exit cell value and add the corresponding values from the dictionary to your queue, and repeat until the queue is empty (no escape) or your find 1 in the queue (escape).

Also, consider using a deque from the collections library instead of pathways list as your queue, and use a set instead inList to keep track of cell values. Unlike your code, the list I originally used for my queue was changing in length, and the Python documentation was clear that deque would be faster:

https://docs.python.org/3/library/collections.html#collections.deque