Testing if 2d lists are equal with recursion-CodePudding

I need to make a function which receive 2 nested lists, and checks if they are the same with recursion. The main problem is that I am not allowed to use the == operator on the lists, change the original lists, or use loops. The function returns True if the lists are the same, and False if not.

For example, The function will return True for the lists

lst_1 = [[1,2,3], [4,5,6]] lst_2 = [[1,2,3], [4,5,6]]

and returns False for the following:

lst_1 = [[1,2,3], [4,5,6]] lst_2 = [[1,2,3], [4,5]]

def func(l1, l2):
    if len(l1) != len(l2):
        return False
    if len(l1[0]) == 0 and len(l2[0]) == 0:
        return True
    if len(l1[-1]) == 0 and len(l2[-1]) == 0:
        del l1[-1]
        del l2[-1]

    if l1[-1][-1] != l2[-1][-1]:
        return False
    l1[-1].pop(-1)
    l2[-1].pop(-1)
    return func(l1, l2)

I have tried to do this with pop, but apparently it changes the original list.

CodePudding user response：

This is a silly set of restrictions, but fine!

For your list of lists to be equal, all corresponding elements from both lists have to be equal. If these elements are lists themselves, then the same logic applies for all elements in these lists.

Instead of iterating over the list, we can say that two lists are equal if their first elements are equal, and the lists making up the remaining elements are also equal.

def lists_equal(lst1, lst2):
    # If either argument is not a list, do the == check
    if not isinstance(lst1, list) or not isinstance(lst2, list):
        return lst1 == lst2

    # If both lists are empty, then the lists are equal
    if not lst1 and not lst2:
        return True

    # If either list is empty but both aren't, then the lists aren't equal
    if not lst1 or not lst2:
        return False

    # Both arguments are lists, so all of their elements must be equal
    #                  First elements equal              Remaining elements equal
    #                  vvvvvvvvvvvvvvvv                  vvvvvvvvvvvvvvvvvv
    return lists_equal(lst1[0], lst2[0]) and lists_equal(lst1[1:], lst2[1:])
    

tests = [
          ([[1,2,3], [4,5,6]], [[1,2,3], [4,5,6]], True),
          ([[1,2,3], [4,5,6]], [[1,2,3], [4,5]], False),
          ([[1,[2,3], [4, 5], 6], [4,5,6]], [[1,[2,3], [4, 5], 6], [4,5,6]], True),
          ([[1,[2,3], [4, 5], 6], [4,5,6]], [[1,[2,3], [4, 5], 6], [4,5]], False),
        ]

for lst1, lst2, result in tests:
    assert lists_equal(lst1, lst2) == result

CodePudding user response：

This function makes two recursive calls - One goes deeper into the current place in the array, the other goes to the next place in the array. this way the recursive will cover the all the elements of the list, and every nested list.

def func(l1, l2, index = 0):
    if(isinstance(l1,int) and isinstance(l2,int)):
        return l1 == l2
    if len(l1) != len(l2):
        return False
    if(isinstance(l1,list) and isinstance(l2,list)):
        if(index >= len(l1)):
            return True
        return func(l1[index],l2[index],0) and func(l1, l2,index  1)    
    return False