Find Exit Matrix Generator

General info

This program generates an n*m matrix with empty fields in each row based on the user's input of the dimensions and probability coefficient. Its primary objective is to determine whether there exists a path from the top layer to the bottom of the matrix.

To run the program, execute the file in a Python environment. If the user enters an invalid value, the program will ask them to input valid values.

An exquisite solution because I do not use brute force; the code looks for the exit in a single iteration through the matrix. The code does not require any external libraries or modules.

Algorithm description

Function generate_matrix() This function prompts the user to enter the size of the field, and the probability of a single cell being empty or full. The program cannot look for a path in nonempty cells. If the input is invalid, it prompts the user again until valid input is given. Then, the function creates two matrices, one for the actual values of the field (this matrix is used for backend calculations) and one matrix for the visual display of the field. Finally, the function returns the two matrices and the probability mentioned above.

Function apply_mines() This function takes in the two matrices generated by generate_matrix() and applies the probability to the actual field matrix based on the probability provided. This creates a visual display of the field matrix with "X" instead of an empty space. But also creates a behind stage matrix for path calculation purposes.

Function find_exit() This function takes in the actual "backend" matrix and attempts to find a path from the top row to the bottom row of the matrix. How? When the matrix is generated, the backend matrix is created like this: [0,1,2,3,4,5,6....n] depending on the input. Where integer values are the indexes of each ‘cell’ of the layer. When the probability is applied, each value is either deleted or remains; and the list of empty ‘cells’ looks like this: [3,5,9 .... n] These are the empty ‘cells’ values that can be used for potential path searching. But not all values can be selected for a further path implementation; first of all, we take each value and compare it to values in the next layer for a direct or indirect route to the next layer. Lets look at an example: [..., ..., ....,..., ..., ., 6...15 ] level 3 paragon =[6, 15] [..., ..., ....,3 ,4 ,5 ,6 ,10 ,14, 15 ] - level 4 paragon = [3] [0 , 1 , 2 , 3, ...,...,...,9] - level 5 If we "came down" from level 3 to level 4 through the paragon of 6 then we have to look for a way down from level 4 to level 5 somewhere apart from 6, because it does not have a straight connection from lvl 4 to 5. My algorithm checks if there is a path between the values 6 and 3 and if 3 is eligible for a path to the next level. Since we have a straight connection 3 would be the next paragon for level 5. The algorithm is built to find all possible paragons simultaneously on each level, so if a single path fails to continue at one point, other possible paths are still executed without the need to come 'back up' and try other routes.

In simple words: We do not need to store a record of past paths because the program tracks them all at the same time without storing the history. 

The function returns a message indicating whether a path was found or not. This code is a simple yet complex algorithm that generates random matrixes and looks for an exit. #Alex_K