Question

Longest ‘A’ Path

Objectives

• Manipulating two-dimensional lists
• Using recursion to solve a problem

Problem Specification

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)

Hint:

• OPTIONAL: you might want to use a boolean list with dimensions similar to the map, which keeps track of whether or not a particular ‘A’ has been counted as part of the A’s in the longest path.
• The following piece of code shows how the recursive calls can be made while keeping track of the current length of ‘A’s and finding the maximum length out of all four recursive calls from a specific position in the 2D list.

path_length = 1 + find_max(findPathLengthRecursive(i + 1, j),

                      findPathLengthRecursive(i - 1, j),

                      findPathLengthRecursive(i, j - 1),

                      findPathLengthRecursive(i, j + 1))

Note: Your output should match what has been displayed in the sample output, and instructions on what each function should do should be followed accurately.

Answer 1

Code In Python:

class Matrix:
  
matrix = []
visited = []
dp = []
  
def readDataFromFile(self,file_name):
  
fopen = open(file_name,"r")
  
fopen.readline()
  
for x in fopen:
  
a = []
  
for ch in x.strip():
a.append(ch)
  
self.matrix.append(a)
  
  

def findLongestPathLength(self):
  
  
  
row = len(self.matrix)
col = len(self.matrix[0])
  
self.dp = [[-1 for i in range(col)]for i in range(row)]
  
for i in range(0,row):
vis = []
for j in range(0,col):
vis.append(False)
self.visited.append(vis)
  
max_ = 0
  
  
for i in range(0,row) :
for j in range(0,col):
  
if self.visited[i][j] == False and self.matrix[i][j] == 'A':
self.count = 1
value = self.findLengthRecursive(i,j)+1
max_ = max(max_,value)
  
return max_
  
def findLengthRecursive(self,row,col):
  
n = len(self.matrix)
m = len(self.matrix[0])
  
self.visited[row][col] = True
  
if (self.dp[row][col] != -1):
return self.dp[row][col]
  
  
  
x, y, z, w = -1, -1, -1, -1
  
if row-1>=0 and col<m and self.visited[row-1][col] == False and self.matrix[row-1][col] == 'A':
x = 1+self.findLengthRecursive(row-1,col)
if row+1<n and col<m and self.visited[row+1][col] == False and self.matrix[row+1][col] == 'A':
y = 1+self.findLengthRecursive(row+1,col)
if row<n and col-1>=0 and self.visited[row][col-1] == False and self.matrix[row][col-1] == 'A':
z = 1+self.findLengthRecursive(row,col-1)
if row<n and col+1<m and self.visited[row][col+1] == False and self.matrix[row][col+1] == 'A':
w = 1+self.findLengthRecursive(row,col+1)
  
self.dp[row][col] = self.find_max(x,y,z,w)   
return self.dp[row][col]
  
def find_max(self,a,b,c,d):
return max(a, max(b, max(c, max(d, 1))))
  
  
def main():
  
file_name = input("Please enter the file name : ")
  
  
cls = Matrix()
  
cls.readDataFromFile(file_name)
  
max_ = cls.findLongestPathLength()
  
print(max_)
  
  
if __name__ == "__main__":
main()

Input :

sample.txt file which contain first example input

Output :

Please enter the file name : C:\Users\DELL\Desktop\sample.txt
Map dimensions:
Number of columns: 17 Number of rows: 7
Length of the longest A path: 10

Explaination:

Matrix class contains

matrix = []

visited = []

dp = []

readDataFromFile function which take argument as file_name and it will open the file read all the lines and store each character in the matrix

findLongestPathLength function will take no argument and it will perform task

• it will create two matrix one is visited and dp. visited matrix is first set to false and dp to -1
• visisted matrix is used for whether (i,j) is visisted or not
• dp matrix is used to store the longest path containing that contains 'A' from a position (i,j)
• we have two loops which will check for matrix(i,j) is 'A' and also visisted is False then will call findLengthRecursive for (i,j)
• and then it will check for max value
• return longest path

findLengthRecursive will take argument (row,col) and performs tasks

• it will first set visited[row][col] = True indicates that position is visited and it will not again go to that position
• then we will have four variable i.e. x,y,z,w that is initiliaze to -1 that are used to store longest path when we move top ,bottom,left,right respectively by including the current element
• if dp[row][col] != -1 it means that it is visited earlier so we will return the value at dp[row][col]
• so we have four condition to move top ,bottom,left and right
• for top we use (row-1,col) , for bottom we use (row,+1col),for left we use (row-1,col) and for right we use (row,col+1) for position (row,col)
• so for we need check condition like row and col will not out of bound, top,bottom,left and right position will not visited before and matrix of top ,bottom,left and right have value as 'A'
• once we find x,y,z and w we will take max of it using find_max function and store it in dp[row][col] that means longest path contains A from (row,col)
• then we will return dp[row] [col]

find_max function takes four argument a,b,c,d and return the maximum value amoung them