Question

Write a Python application to find the longest ‘A’ path on a map of capital (uppercase) letters. The map is represented as a matrix (2-dimensional list) of capital letters. Starting from any point, you can go left, right, up and down (but not diagonally). A path is defined as the unbroken sequence of letters that only covers the spots with the letter A. The length of the A path is defined as the number of ‘A’s on the path. Your program needs to find the longest A path on the map. In the following example, the characters in the longest A path are highlighted and the length of the longest path is 7.

Note that you cannot move backwards over a character ‘A’ that has already been counted. In the example below, start from the ‘A’ in the 4^th row, 4^th column, move upwards and end at the ‘A’ on the second row, second column.

A    U    A    A   

B     A    A    A   

T     K     T     A   

A    A    X     A    <--- Start from here and move upwards.

D    A    S     X

Your program should read the data for the map from a text file (multiple .txt input files will be provided), find the longest A path, and output the length of that path. In the input file, the first line contains 2 integers m and n. These integers represent the number of columns m and the number of rows n of the map. Starting from the second line of the text file, the map is represented as n strings with m characters each.

Example Input:

17 7
VAAAAAPAAEAFRLDAR
AAAYPBAKAWPKAJEAA
AFAAAUTFENWAQALPC
YYXTHALXSCCMIAAGA
AAXAAZRANZAJALQAA
ZAAAXGJIOAAPAALAX
JAAAAIAAAAATAAADA

Example output:

Map dimensions:

Number of columns: 17 Number of rows: 7

Length of the longest "A" path: 10

Example input:

15 15
PAYAAHARACAAAAA
ASHAAOAEBFYALAS
YAAOVBAAAEJBAKQ
AAEAXAAAQAQEAAT
AEJZLMUAXHIAAYA
AFAEAAAFKAATPKA
AAKAAAUAATAAAPU
AAAAAAAXAKAAAAQ
VBAJHPAANWAAAAT
AAAWAAZOAIAOHOE
AAAJADMAIZANAEA
MAFWUAAKBPAALGB
AHKAITAAXFAGAAA
DIAGWZARRAANAUA
SAAXHAHAFJAYZAA

Example output:

Map dimensions:

Number of columns: 15 Number of rows: 15

Length of the longest "A" path: 20

Design Requirements

You MUST use recursion for this assignment. Recall that recursion is when a method calls itself (one or more times), and each call might again call itself, over and over until some base condition is met and the methods return.

Your design must use the following 3 functions:

'''

Use open(), readline() and/or readlines() functions to read the following from the input file:

- length and width of the map;

- the characters to be stored in the map.

Create the map using the data read from the input file.

Note: you may need to use strip and split functions.

The next part is OPTIONAL but might be helpful to use.

Declare and initialize a Boolean list with similar dimensions to the map; this list can be used to keep track of the A's in the input file that have already been counted in the path of A's being 'discovered' in the program.

Parameter to function: input file name.

'''

def readDataFromFile(filename)

'''

Iterate through all the positions in the map (2-dimensional list);

at each position, call the recursive method findPathLengthRecursive(), and at each position, update the maximum number of A's in the path so far.

Function return: The maximum number of A's in the path.

'''

findLongestPathLength()

'''

This method uses recursion to check the cells to the left, right, above and below the current cell to determine if any of these is an 'A' that hasn't yet been counted as part of the longest path of A's.

NOTE: Each 'A' in the path should be counted only once.

Function parameters:

i: The current row.

j: The current column.

Function return: Return either zero or the current length signifying the number of connected A's so far.

'''

findPathLengthRecursive(i, j)

'''

This method determines which of the four values passed to it is the maximum. The four values passed represent the path lengths for the four paths of recursive calls from a specific character in the 2D list.

Function parameters:

a: The length returned from position [i-1, j].

b: The length returned from position [i+1, j].

c: The length returned from position [i, j-1].

d: The length returned from position [i, j+1].

Function return: Returns the Maximum of all lengths passed to it.

'''  

find_max(a, b, c, d)

***********************

sam_1.txt

17 7
VAAAAAPAAEAFRLDAR
AAAYPBAKAWPKAJEAA
AFAAAUTFENWAQALPC
YYXTHALXSCCMIAAGA
AAXAAZRANZAJALQAA
ZAAAXGJIOAAPAALAX
JAAAAIAAAAATAAADA

sam_2.txt:

15 15
PAYAAHARACAAAAA
ASHAAOAEBFYALAS
YAAOVBAAAEJBAKQ
AAEAXAAAQAQEAAT
AEJZLMUAXHIAAYA
AFAEAAAFKAATPKA
AAKAAAUAATAAAPU
AAAAAAAXAKAAAAQ
VBAJHPAANWAAAAT
AAAWAAZOAIAOHOE
AAAJADMAIZANAEA
MAFWUAAKBPAALGB
AHKAITAAXFAGAAA
DIAGWZARRAANAUA
SAAXHAHAFJAYZAA

Answer 1

# python code for given problem

# Reading data from file
def readDataFromFile(file):
    f = open(file)
    dimensions=f.readline()
    dimensions=dimensions.split()
    columns=int(dimensions[0]) #no of colums
    rows=int(dimensions[1]) #no of rows
    matrix=[]
    # actually in this matrix we are stores 1 in place of 'A' otherwise 0
    for i in range(rows-1):
        line=f.readline()
        row=[]
        for j in range(len(line)-1):
            if line[j]=='A':
                row.append(1)
            else:
                row.append(0)
        matrix.append(row)
    f.close()
    return matrix,rows,columns # return matrix rows colums

# function for finding longest path length
def findLongestPathLength(matrix):
    longest_path=0;
    rows=len(matrix)
    columns=len(matrix[0])
    # function to make recursive calls in all four directions 
    def findPathLengthRecursive(i,j):
        if i>=0 and i<rows and j>=0 and j<columns and matrix[i][j]==1:
            matrix[i][j]=0  # marking it 0 so that it should not be counted again as it is visited 
            path1=findPathLengthRecursive(i+1,j)
            path2=findPathLengthRecursive(i,j+1)
            path3=findPathLengthRecursive(i-1,j)
            path4=findPathLengthRecursive(i,j-1)
            matrix[i][j]=1 #again assigning 1 it's actual value , for considering other paths also 
            return max(path1,path2,path3,path4)+1
        else:
            return 0
    for i in range(rows-1):
        for j in range(columns-1):
            if matrix[i][j]==1:
                longest_path=max(longest_path,findPathLengthRecursive(i,j)) # taking max of longest path
    return longest_path

if __name__ == "__main__":
    # you should have input file present in the same folder as of python file otherwise it will give error
    file=input("Enter the name of input file : ")
    matrix,rows,columns=readDataFromFile(file) # reading data and converting it into 2-d list
    print("Map dimensions : ")
    print("Number of columns: ",columns," Number of rows: ",rows)
    longest_path_length=findLongestPathLength(matrix) # finding the longest path length
    print("Length of the Longest Path 'A' path :", longest_path_length)
                    

Here are the screenshots of input and output