#๐Ÿ”’ how to get rid of length 0 strings

148 messages ยท Page 1 of 1 (latest)

stark karma
#

anyone know how i can fix my code to get rid of the first row and colum being 0: code: ```python

class LCSMatrix:
def init(self, str1, str2):
self.row_count = len(str1) + 1
self.column_count = len(str2) + 1
self.str1 = str1
self.str2 = str2
self.matrix = [[0] * (self.column_count) for _ in range(self.row_count)]

    for i in range(self.row_count):
        for j in range(self.column_count):
            if i == 0 or j == 0:
                self.matrix[i][j] = 0
            elif str1[i - 1] == str2[j - 1]:
                self.matrix[i][j] = 1 + self.matrix[i - 1][j - 1]
            else:
                self.matrix[i][j] = max(self.matrix[i - 1][j], self.matrix[i][j - 1])

# Returns the number of columns in the matrix, which also equals the length
# of the second string passed to the constructor.
def get_column_count(self):
    return self.column_count

# Returns the matrix entry at the specified row and column indices, or 0 if
# either index is out of bounds.
def get_entry(self, row_index, column_index):
    adjusted_row_index = row_index - 1
    adjusted_column_index = column_index - 1

    if 0 <= adjusted_row_index < self.row_count - 1 and 0 <= adjusted_column_index < self.column_count - 1:
        return self.matrix[adjusted_row_index + 1][adjusted_column_index + 1]
    else:
        return 0

# Returns the number of rows in the matrix, which also equals the length
# of the first string passed to the constructor.
def get_row_count(self):
    return self.row_count
elder magnetBOT
#

@stark karma

Python help channel opened

Remember to:

  • Ask your Python question, not if you can ask or if there's an expert who can help.
  • Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
  • Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

stark karma
#

    def helper(self, curr_rowIdx, curr_colIdx, currSeq):
        if curr_rowIdx == 0 or curr_colIdx == 0:
            if currSeq:
                return {currSeq[::-1]}  
            else:
                return set()  
        elif self.str1[curr_rowIdx - 1] == self.str2[curr_colIdx - 1]:
            return self.helper(curr_rowIdx - 1, curr_colIdx - 1, currSeq + self.str1[curr_rowIdx - 1])
        else:
            sequences = set()
            if self.matrix[curr_rowIdx - 1][curr_colIdx] >= self.matrix[curr_rowIdx][curr_colIdx - 1]:
                sequences |= self.helper(curr_rowIdx - 1, curr_colIdx, currSeq)

            if self.matrix[curr_rowIdx][curr_colIdx - 1] >= self.matrix[curr_rowIdx - 1][curr_colIdx]:
                sequences |= self.helper(curr_rowIdx, curr_colIdx - 1, currSeq)

            return sequences
    
    # Returns the set of distinct, longest common subsequences between the two
    # strings that were passed to the constructor.
    def get_longest_common_subsequences(self):
        return self.helper(self.row_count-1, self.column_count-1, "")
frigid scarab
#

why are you adding one to the counts

#

not my_list will return True if my_list is an empty list

#
                if i == 0 or j == 0:
                    self.matrix[i][j] = 0
``` you set it to 0 here
stark karma
#

wdym

frigid scarab
#

self.row_count = len(str1) + 1 self.column_count = len(str2) + 1

stark karma
#

but its only the matrices the strings are passing tho

#

FAIL: "ABBA" and "BAAB"
Expected matrix:
[0, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 1, 2]
[1, 2, 2, 2]
Actual matrix:
[0, 0, 0, 0, 0]
[0, 0, 1, 1, 1]
[0, 1, 1, 1, 2]
[0, 1, 1, 1, 2]
[0, 1, 2, 2, 2]

FAIL: "lower case" and "UPPER CASE"
Expected matrix:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
Actual matrix:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1]

FAIL: "LOOK" and "ZYBOOKS"
Expected matrix:
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 1, 1, 1]
[0, 0, 0, 1, 2, 2, 2]
[0, 0, 0, 1, 2, 3, 3]
Actual matrix:
[0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 1, 1, 1]
[0, 0, 0, 0, 1, 2, 2, 2]
[0, 0, 0, 0, 1, 2, 3, 3]

PASS: "ZYBOOKS" and "LOOK"
Expected LCS set:
{'OOK'}
Actual LCS set:
{'OOK'}

#

the LCS sets seem to be right

frigid scarab
#

well stop making matrix with extra row and column

frigid scarab
#
        self.row_count = len(str1) + 1
        self.column_count = len(str2) + 1
        self.matrix = [[0] * (self.column_count) for _ in range(self.row_count)]```
elder magnetBOT
#

Hey @frigid scarab!

It looks like you pasted Python code without syntax highlighting.

Please use syntax highlighting to improve the legibility of your code and make it easier for us to help you.

To do this, use the following method:
```py
print('Hello, world!')
```

This will result in the following:

print('Hello, world!')```
You can **edit your original message** to correct your code block.
frigid scarab
#

remove the + 1's

stark karma
#

i keep changing the line you suggested but its not working

stark karma
frigid scarab
#

so then you'll need to fix that

#

is it supposed to be 1-indexed?

stark karma
#

prompt:


A dynamic programming matrix can be used to solve the longest common subsequence problem. Rules for populating the matrix differ slightly from the longest common substring algorithm. Both algorithms populate rows from top to bottom, and left to right across a row. Each entry matrix[R][C] is computed as follows:

If characters match, both algorithms assign matrix[R][C] with 1 + matrix[R - 1][C - 1].
If characters do not match, the longest common _____.
substring algorithm assigns matrix[R][C] with 0
subsequence algorithm assigns matrix[R][C] with max(matrix[R - 1][C], matrix[R][C - 1])
Each algorithm uses 0 for out of bounds entries. Ex: When computing matrix[0][0] for a character match, instead of trying to access matrix[-1][-1], 0 is used instead.

Sample matrix
The image below shows the longest common subsequence matrix for strings "ALASKAN" and "BANANAS". Entries corresponding to a character match are highlighted.

7x7 matrix with the following numerical entries: Row 0: 0, 1, 1, 1, 1, 1, 1. Row 1: 0, 1, 1, 1, 1, 1, 1. Row 2: 0, 1, 1, 2, 2, 2, 2. Row 3: 0, 1, 1, 2, 2, 2, 3. Row 4: 0, 1, 1, 2, 2, 2, 3. Row 5: 0, 1, 1, 2, 2, 3, 3. Row 6: 0, 1, 2, 2, 3, 3, 3. Entries for matching characters are highlighted.

The largest number in the matrix indicates the length of the longest common subsequence. Ex: The largest entry in the matrix above is 3, so the longest common subsequence between "ALASKAN" and "BANANAS" is 3 characters long.

Multiple longest common subsequences
A pair of strings may have more than one longest common subsequence. Ex: "ALASKAN" and "BANANAS" have three longest common subsequences: "AAA", "AAN", and "AAS".```
frigid scarab
#

do you need get_entry ?

stark karma
#

im not 100% sure tbh i just wrote code solely on the prompt

stark karma
frigid scarab
#

where

stark karma
# frigid scarab where
 # Returns the matrix entry at the specified row and column indices, or 0 if
    # either index is out of bounds.
    def get_entry(self, row_index, column_index):
        if 0 <= row_index < self.row_count and 0 <= column_index < self.column_count:
            return self.matrix[row_index][column_index]
        else:
            return 0
frigid scarab
#

no where you use it

stark karma
frigid scarab
#

[row[1:] for row in matrix[1:]]

stark karma
#

but its being tested for the matrices

frigid scarab
#

that would probably shave off a first row and column i think

stark karma
#

Some test cases also test matrix entries returned from get_entry()

stark karma
frigid scarab
#

wherever you want a matrix that has one less row and column

stark karma
frigid scarab
#
 >>> matrix = [[1,2,3],[4,5,6],[7,8,9]]
 >>> [row[1:] for row in matrix[1:]]
 [[5, 6], [8, 9]]
stark karma
#
class LCSMatrix:
    def __init__(self, str1, str2):
        self.row_count = len(str1) + 1
        self.column_count = len(str2) + 1
        # Your code here
        self.str1 = str1
        self.str2 = str2
        self.matrix = [[0] * self.column_count for _ in range(self.row_count)]
        
        for i in range(self.row_count):
            for j in range(self.column_count):
                if i == 0 or j == 0:
                    self.matrix[i][j] = 0
                elif str1[i - 1] == str2[j - 1]:
                    self.matrix[i][j] = 1 + self.matrix[i - 1][j - 1]
                else:
                    self.matrix[i][j] = max(self.matrix[i - 1][j], self.matrix[i][j - 1])
    
    # Returns the number of columns in the matrix, which also equals the length
    # of the second string passed to the constructor.
    def get_column_count(self):
        return self.column_count
    
    # Returns the matrix entry at the specified row and column indices, or 0 if
    # either index is out of bounds.
    def get_entry(self, row_index, column_index):
        # Your code here (remove placeholder line below)
        trimmed_matrix = self.get_trimmed_matrix()
        if 1 <= row_index < self.row_count and 1 <= column_index < self.column_count:
            return trimmed_matrix[row_index - 1][column_index - 1]
        else:
            return 0
    
    # Returns the number of rows in the matrix, which also equals the length
    # of the first string passed to the constructor.
    def get_row_count(self):
        return self.row_count

#
def helper(self, curr_rowIdx, curr_colIdx, currSeq):
        if curr_rowIdx == 0 or curr_colIdx == 0:
            if currSeq:
                return {currSeq[::-1]}  
            else:
                return set()  
        elif self.str1[curr_rowIdx - 1] == self.str2[curr_colIdx - 1]:
      
            return self.helper(curr_rowIdx - 1, curr_colIdx - 1, currSeq + self.str1[curr_rowIdx - 1])
        else:
       
            sequences = set()
            if self.matrix[curr_rowIdx - 1][curr_colIdx] >= self.matrix[curr_rowIdx][curr_colIdx - 1]:
                sequences |= self.helper(curr_rowIdx - 1, curr_colIdx, currSeq)

            if self.matrix[curr_rowIdx][curr_colIdx - 1] >= self.matrix[curr_rowIdx - 1][curr_colIdx]:
                sequences |= self.helper(curr_rowIdx, curr_colIdx - 1, currSeq)

            return sequences
           
    
    # Returns the set of distinct, longest common subsequences between the two
    # strings that were passed to the constructor.
    def get_longest_common_subsequences(self):
        # Your code here (remove placeholder line below)
        return self.helper(self.row_count - 1, self.column_count - 1, "")
    
    def get_trimmed_matrix(self):
        return [row[1:] for row in self.matrix[1:]]
#

still tests fails: FAIL: "lower case" and "UPPER CASE"
Expected matrix:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
Actual matrix:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1]

FAIL: "PROGRAMMING" and "PROBLEM"
Expected matrix:
[1, 1, 1, 1, 1, 1, 1]
[1, 2, 2, 2, 2, 2, 2]
[1, 2, 3, 3, 3, 3, 3]
[1, 2, 3, 3, 3, 3, 3]
[1, 2, 3, 3, 3, 3, 3]
[1, 2, 3, 3, 3, 3, 3]
[1, 2, 3, 3, 3, 3, 4]
[1, 2, 3, 3, 3, 3, 4]
[1, 2, 3, 3, 3, 3, 4]
[1, 2, 3, 3, 3, 3, 4]
[1, 2, 3, 3, 3, 3, 4]
Actual matrix:
[0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 1, 1, 1, 1]
[0, 1, 2, 2, 2, 2, 2, 2]
[0, 1, 2, 3, 3, 3, 3, 3]
[0, 1, 2, 3, 3, 3, 3, 3]
[0, 1, 2, 3, 3, 3, 3, 3]
[0, 1, 2, 3, 3, 3, 3, 3]
[0, 1, 2, 3, 3, 3, 3, 4]
[0, 1, 2, 3, 3, 3, 3, 4]
[0, 1, 2, 3, 3, 3, 3, 4]
[0, 1, 2, 3, 3, 3, 3, 4]
[0, 1, 2, 3, 3, 3, 3, 4]

FAIL: "LOOK" and "ZYBOOKS"
Expected matrix:
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 1, 1, 1]
[0, 0, 0, 1, 2, 2, 2]
[0, 0, 0, 1, 2, 3, 3]
Actual matrix:
[0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 1, 1, 1]
[0, 0, 0, 0, 1, 2, 2, 2]
[0, 0, 0, 0, 1, 2, 3, 3]

frigid scarab
#

that code works absolutely fine. whether you implement correctly into your own is another matter

#

do the tests call get_entry a bunch of times to reconstruct a matrix or they just access self.matrix?

stark karma
#

for the matrices

frigid scarab
#

remove the - 1

#

or return -9 instead of 0, see what comes out

stark karma
frigid scarab
#

try ```py
else:
return -9

stark karma
#

Returns the matrix entry at the specified row and column indices, or 0 if
# either index is out of bounds.

frigid scarab
#

i know that.

#

im not dumb

#

its for debugging purposes, to illustrate a point

stark karma
#

FAIL: "LOOK" and "ZYBOOKS"
Expected matrix:
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 1, 1, 1]
[0, 0, 0, 1, 2, 2, 2]
[0, 0, 0, 1, 2, 3, 3]
Actual matrix:
[-9, -9, -9, -9, -9, -9, -9, -9]
[-9, 0, 0, 0, 0, 0, 0, 0]
[-9, 0, 0, 0, 1, 1, 1, 1]
[-9, 0, 0, 0, 1, 2, 2, 2]
[-9, 0, 0, 0, 1, 2, 3, 3]

frigid scarab
#

so the fact it returns 0s for whatever case hides the fact its still returning the wrong size matrix

frigid scarab
#

return trimmed_matrix[row_index - 1][column_index - 1]

#

see some - 1 s there...?

stark karma
#

i added it tho cuz i kept getting index out of range

stark karma
#

as expected

frigid scarab
#

why do you use and in the condition

stark karma
#

i might need to fix code without adding +1 for row ount and column count

#

i think thats why the size matrix is off

stark karma
frigid scarab
#

i don't wanna spoon feed you

#

what's the function we've just been talking about?

stark karma
frigid scarab
#

yep. so look through it, all 5 lines

#

it has a single and

#

that's where

stark karma
frigid scarab
#

if i have matrix 10x10. 3 sets of coordinates are [5, 15] and [17, 17] and [14, 6]

#

which coordinates would it fail on and which coordinates should it fail on? using and vs or

untold cove
#

Is it just me or is this super hard to understand?

frigid scarab
#

actually scratch that thought with and. i was looking at exclusive boundaries rather than inclusive

stark karma
#

init__(): Two lines of code are given to assign the row_count and column_count attributes to string1's length and string2's length, respectively. The remainder of the method must be implemented to build the longest common subsequence matrix.
Use case sensitive character comparisons. Ex: 'a' and 'A' are not equal.
get_entry(): Returns the numerical entry at the given row and column indices, or 0 if either index is out of bounds.
get_longest_common_subsequences(): Returns a Python set object. The set contains strings indicating all longest common subsequences for the two strings passed to init().

frigid scarab
#

but there might just be some off-by-1 errors going on anyway

stark karma
frigid scarab
#

https://en.wikipedia.org/wiki/Off-by-one_error

probably like 2nd most common bug in entirety of programming

An off-by-one error or off-by-one bug (known by acronyms OBOE, OBO, OB1 and OBOB) is a logic error that involves a number that differs from its intended value by +1 or โˆ’1. It often occurs in computer programming when a loop iterates one time too many or too few, usually caused by the use of non-strict inequality (โ‰ค) as the terminating condition ...

stark karma
#

idk where the index is getting out of range from

frigid scarab
#

you can do your own testing

#

put in your own matrix and test some boundary coordinates for what should be correct or incorrect results

frigid scarab
stark karma
#

if curr_rowIdx == 0 or curr_colIdx == 0:
RecursionError: maximum recursion depth exceeded in comparison

#
class LCSMatrix:
    def __init__(self, str1, str2):
        self.row_count = len(str1) 
        self.column_count = len(str2) 
     
        self.str1 = str1
        self.str2 = str2
        self.matrix = [[0] * self.column_count for _ in range(self.row_count)]
        
        for i in range(self.row_count):
            for j in range(self.column_count):
                if i == 0 or j == 0:
                    self.matrix[i][j] = 0
                elif str1[i] == str2[j]:
                    self.matrix[i][j] = 1 + self.matrix[i][j]
                else:
                    self.matrix[i][j] = max(self.matrix[i ][j], self.matrix[i][j])
    
    # Returns the number of columns in the matrix, which also equals the length
    # of the second string passed to the constructor.
    def get_column_count(self):
        return self.column_count
    
    # Returns the matrix entry at the specified row and column indices, or 0 if
    # either index is out of bounds.
    def get_entry(self, row_index, column_index):
        
        trimmed_matrix = self.get_trimmed_matrix()
        if 1 <= row_index < self.row_count and 1 <= column_index < self.column_count:
            return trimmed_matrix[row_index][column_index]
        else:
            return -9 
    
    # Returns the number of rows in the matrix, which also equals the length
    # of the first string passed to the constructor.
    def get_row_count(self):
        return self.row_count
   

frigid scarab
#

it called itself over and over again

stark karma
#
def helper(self, curr_rowIdx, curr_colIdx, currSeq):
        if curr_rowIdx == 0 or curr_colIdx == 0:
            if currSeq:
                return {currSeq[::-1]}  
            else:
                return set()  
        elif self.str1[curr_rowIdx] == self.str2[curr_colIdx]:
      
            return self.helper(curr_rowIdx, curr_colIdx, currSeq + self.str1[curr_rowIdx])
        else:
       
            sequences = set()
            if self.matrix[curr_rowIdx ][curr_colIdx] >= self.matrix[curr_rowIdx][curr_colIdx]:
                sequences |= self.helper(curr_rowIdx, curr_colIdx, currSeq)

            if self.matrix[curr_rowIdx][curr_colIdx] >= self.matrix[curr_rowIdx][curr_colIdx]:
                sequences |= self.helper(curr_rowIdx, curr_colIdx, currSeq)

            return sequences
           
    
    # Returns the set of distinct, longest common subsequences between the two
    # strings that were passed to the constructor.
    def get_longest_common_subsequences(self):
        
        return self.helper(self.row_count, self.column_count, "")
    
    def get_trimmed_matrix(self):
        return [row[1:] for row in self.matrix[1:]]
#

File "/usercode/LCSMatrix.py", line 67, in get_longest_common_subsequences
return self.helper(self.row_count, self.column_count, "")
File "/usercode/LCSMatrix.py", line 48, in helper
elif self.str1[curr_rowIdx] == self.str2[curr_colIdx]:
IndexError: string index out of range

frigid scarab
#
    def __init__(self, str1, str2):
        self.row_count = len(str1) 
        self.column_count = len(str2) 
     
        self.str1 = str1
        self.str2 = str2
        self.matrix = [[0] * self.column_count for _ in range(self.row_count)]

if you are working with a "0-based index" matrix now like i suggested (by removing the + 1s there), so 10 elements go from index 0 to index 9

#

which imo is just most natural to do because python itself is natively 0-based

#

many of the other parts of the code might need to be adjust to not start at 1 or not use a + 1 or - 1

frigid scarab
#

yeah i saw, but for instance now using if 1 <= row_index < self.row_count and 1 <= column_index < self.column_count: there are 1s there, so get_entry would naturally chop off the 1st row and column (at index 0) by default

#

maybe you even want that since you said you wanted a first column and row gone

#

you wouldn't need my other single line solution any more

stark karma
frigid scarab
#

no, try get rid of trimmed matrix

#

if the exercise says you need to do bounds checking you probably still need that in there

stark karma
#
 def get_entry(self, row_index, column_index):
       
        if 0 <= row_index < self.row_count and 0 <= column_index < self.column_count:
            return self.matrix[row_index][column_index]
        else:
            return 0
frigid scarab
#

or you could try 0 instead of 1, sure

stark karma
#

File "/usercode/LCSTestCase.py", line 33, in execute
actual = user_matrix.get_longest_common_subsequences()
File "/usercode/LCSMatrix.py", line 66, in get_longest_common_subsequences
return self.helper(self.row_count, self.column_count, "")
File "/usercode/LCSMatrix.py", line 47, in helper
elif self.str1[curr_rowIdx] == self.str2[curr_colIdx]:
IndexError: string index out of range

frigid scarab
#

give it as simple a test case as possible but try and break it

#

difference is you can see the datastructures and pointers etc as it breaks

#

but you want very simple test data or it'll be crazy complicated

stark karma
#

ill probably need to change this: ```python
ef helper(self, curr_rowIdx, curr_colIdx, currSeq):
if curr_rowIdx == 0 or curr_colIdx == 0:
if currSeq:
return {currSeq[::-1]}
else:
return set()
elif self.str1[curr_rowIdx] == self.str2[curr_colIdx]:

        return self.helper(curr_rowIdx, curr_colIdx, currSeq + self.str1[curr_rowIdx])
    else:
stark karma
#

im passing thhe string tests tho: PASS
: "CTATGCATTTACGCTATCGCTAT" and "ACTGATCTCAGCTTACTATCGCATCGATCT"

Expected LCS set:

{'CTATGCTTACTATCGCTAT', 'CTATCTTTACTATCGCTAT', 'CTATGCTTTACGCATCGTT', 'CTATGCTTTACGCATCGCT', 'CTATGCTTTACGCATCGAT', 'CTATCATTTACGCATCGAT', 'CTATCATTACTATCGCTAT', 'CTATCATTTACGCATCGCT', 'CTATCATTTACGCATCGTT'}

Actual LCS set:

{'CTATGCTTACTATCGCTAT', 'CTATCTTTACTATCGCTAT', 'CTATGCTTTACGCATCGTT', 'CTATGCTTTACGCATCGCT', 'CTATGCTTTACGCATCGAT', 'CTATCATTTACGCATCGAT', 'CTATCATTACTATCGCTAT', 'CTATCATTTACGCATCGCT', 'CTATCATTTACGCATCGTT'}

PASS
: "THE QUICK BROWN FOX" and "JUMPS OVER THE LAZY DOG"

Expected LCS set:

{'THE  O'}

Actual LCS set:

{'THE  O'}
frigid scarab
#

im not sure you need trimmed matrix any more

stark karma
#
class LCSMatrix:
    def __init__(self, str1, str2):
        self.row_count = len(str1) 
        self.column_count = len(str2) 

        self.str1 = str1
        self.str2 = str2
        self.matrix = [[0] * self.column_count for _ in range(self.row_count)]
        
        for i in range(self.row_count):
            for j in range(self.column_count):
                if i == 0 or j == 0:
                    self.matrix[i][j] = 0
                elif str1[i] == str2[j]:
                    self.matrix[i][j] = self.matrix[i][j]
                else:
                    self.matrix[i][j] = max(self.matrix[i][j], self.matrix[i][j])
   
    def get_column_count(self):
        return self.column_count

    def get_entry(self, row_index, column_index):
        if 0 <= row_index < self.row_count and 0 <= column_index < self.column_count:
            return self.matrix[row_index][column_index]
        else:
            return -9
    
    def get_row_count(self):
        return self.row_count
    
    def helper(self, curr_rowIdx, curr_colIdx, currSeq):
        if curr_rowIdx == 0 or curr_colIdx == 0:
            if currSeq:
                return {currSeq[::-1]}  
            else:
                return set()  
        elif self.str1[curr_rowIdx] == self.str2[curr_colIdx]:
      
            return self.helper(curr_rowIdx, curr_colIdx, currSeq + self.str1[curr_rowIdx])
        else:
       
            sequences = set()
            if self.matrix[curr_rowIdx ][curr_colIdx] >= self.matrix[curr_rowIdx][curr_colIdx]:
                sequences |= self.helper(curr_rowIdx, curr_colIdx, currSeq)

            if self.matrix[curr_rowIdx][curr_colIdx] >= self.matrix[curr_rowIdx][curr_colIdx]:
                sequences |= self.helper(curr_rowIdx, curr_colIdx, currSeq)

            return sequences
           
    def get_longest_common_subsequences(self):
       
        return self.helper(self.row_count, self.column_count, "")
    ```
frigid scarab
#

i dunno if the -9 actually like fucks up the algorithm at some point, it may do

#

i just suggested that to show the difference between what get entry would show and what the matrix was

stark karma
#

FAIL: "BAA" and
"ABBA"

Expected matrix:

[0, 1, 1, 1]

[1, 1, 1, 2]

[1, 1, 1, 2]

Actual matrix:

[0, 0, 0, 0, 0]

[0, 0, 1, 1, 1]

[0, 1, 1, 1, 2]

[0, 1, 1, 1, 2]
frigid scarab
#

Each algorithm uses 0 for out of bounds entries. Ex: When computing matrix[0][0] for a character match, instead of trying to access matrix[-1][-1], 0 is used instead.

stark karma
#

this is only testing get entry

frigid scarab
#

try put back 1 instead of 0 ๐Ÿคฃ

stark karma
#

File "/usercode/main.py", line 149, in <module>
if test_case.execute(test_feedback):
File "/usercode/LCSTestCase.py", line 33, in execute
actual = user_matrix.get_longest_common_subsequences()
File "/usercode/LCSMatrix.py", line 66, in get_longest_common_subsequences
return self.helper(self.row_count, self.column_count, "")
File "/usercode/LCSMatrix.py", line 47, in helper
elif self.str1[curr_rowIdx] == self.str2[curr_colIdx]:
IndexError: string index out of range

frigid scarab
#

maybe your algorithm needs to work with an 'internal' version of get entry

#

like just copy paste the function call it something else

#

use that for internal algorithm

#

and use the 1 verison for 'official' version so it gives right matrix for that test

#

or this modification

#
        for i in range(self.row_count):
            for j in range(self.column_count):
                if i == 0 or j == 0:
                    self.matrix[i][j] = 0
                elif str1[i] == str2[j]:
                    self.matrix[i][j] = self.matrix[i][j]
                else:
                    self.matrix[i][j] = max(self.matrix[i][j], self.matrix[i][j])
``` is no longer needed
#

because things should just call get entry, and if they ask for [0, -1] instead of erroring with a range error because -1 is out of bounds it would return 0

stark karma
#

oh so i almost got it lol

#

i got the matrices to pass now

#

but the string tests are failing

#

it keeps returning just set()

#

FAIL: "five food groups" and "dairy, vegetables, fruits, grains, and protein"
Expected LCS set:
{'ive f grs', 'ive f grp', 'ive fd ro', 'ive f gro'}
Actual LCS set:
set()

FAIL: "A MAN A PLAN A CANAL PANAMA" and "THE RAIN IN SPAIN STAYS MAINLY IN THE PLAIN"
Expected LCS set:
{' AN PAN A ANL PAN'}
Actual LCS set:
set()

#
class LCSMatrix:
    def __init__(self, str1, str2):
        self.row_count = len(str1) 
        self.column_count = len(str2) 
        self.str1 = str1
        self.str2 = str2
        self.matrix = [[0] * self.column_count for _ in range(self.row_count)]
        
        for i in range(self.row_count):
            for j in range(self.column_count):
                if str1[i] == str2[j]:
                    if i == 0 or j == 0:
                        self.matrix[i][j] = 1
                    else:
                        self.matrix[i][j] = self.matrix[i - 1][j - 1] + 1
                else:
                    if i == 0 and j == 0:
                        self.matrix[i][j] = 0
                    elif i == 0:
                        self.matrix[i][j] = self.matrix[i][j - 1]
                    elif j == 0:
                        self.matrix[i][j] = self.matrix[i - 1][j]
                    else:
                        self.matrix[i][j] = max(self.matrix[i - 1][j], self.matrix[i][j - 1])
   
    def get_column_count(self):
        return self.column_count
   
    def get_entry(self, row_index, column_index):
        
        if 0 <= row_index < self.row_count and 0 <= column_index < self.column_count:
            return self.matrix[row_index][column_index]
        else:
            return 0
  
    def get_row_count(self):
        return self.row_count
#
def helper(self, curr_rowIdx, curr_colIdx, currSeq):
        if curr_rowIdx < 0 or curr_colIdx < 0:
            if currSeq:
                return {currSeq[::-1]}  
            else:
                return set()  
        elif self.str1[curr_rowIdx] == self.str2[curr_colIdx]:
            return self.helper(curr_rowIdx - 1, curr_colIdx - 1, currSeq + self.str1[curr_rowIdx])
        else:
            sequences = set()
            if curr_rowIdx > 0 and self.matrix[curr_rowIdx - 1][curr_colIdx] >= self.matrix[curr_rowIdx][curr_colIdx]:
                sequences |= self.helper(curr_rowIdx - 1, curr_colIdx, currSeq)
            if curr_colIdx > 0 and self.matrix[curr_rowIdx][curr_colIdx - 1] >= self.matrix[curr_rowIdx][curr_colIdx]:
                sequences |= self.helper(curr_rowIdx, curr_colIdx - 1, currSeq)
            return sequences
 
    def get_longest_common_subsequences(self):
       
        return self.helper(self.row_count-1, self.column_count-1, "")
#

have to fix helper function

frigid scarab
#

if curr_rowIdx > 0 and self.matrix[curr_rowIdx - 1][curr_colIdx] >= self.matrix[curr_rowIdx][curr_colIdx]:

#

you're accessing the matrix directly

#

get its elements using your function

#

get_entry

#

thats most of the point of having it in the first place

stark karma
#

im not really sure how to pass both the string tests and matrices tests. its either or every case lol

#

it only fails for some tests tho: PASS
: "BAA" and "ABBA"

Expected matrix:

[0, 1, 1, 1]

[1, 1, 1, 2]

[1, 1, 1, 2]

Actual matrix:

[0, 1, 1, 1]

[1, 1, 1, 2]

[1, 1, 1, 2]

Expected LCS set:

{'AA', 'BA'}

Actual LCS set:

{'AA', 'BA'}

FAIL
: "function" and "method"

Expected matrix:

[0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0]

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

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

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

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

Actual matrix:

[0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0]

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

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

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

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

Expected LCS set:

{'to'}

Actual LCS set:

set()
frigid scarab
elder magnetBOT
#
Python help channel closed

This help channel has been closed and it's no longer possible to send messages here. If your question wasn't answered, feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.