Testing if 2d lists are equal with recursion

Question

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.

No, it doesn't. A slice is not a mutation. The problem description doesn't say that the lists in the recursive call has to be the same lists, just that those lists are not mutated. If you can't do something reasonable, you could always define a helper function where an index is passed. — John Coleman, Dec 12 '22 at 21:01
@JohnColeman I am not allowed to do any manipulation on the list, only O1 (time comp) action, with no touching the original lists — Dr.jj, Dec 12 '22 at 21:05
@codingStarter only O1 action with no manipulation on the list — Dr.jj, Dec 12 '22 at 21:06
can the nested arrays be in any level? like, can you have an array like this? [[[1],2],[3]] — codingStarter, Dec 12 '22 at 21:39

score 0 · Answer 1 · answered Dec 14 '22 at 02:48

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

codingStarter · Answer 2 · 2022-12-13T12:49:30.963

-1

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

edited Dec 13 '22 at 12:49

answered Dec 12 '22 at 22:23

codingStarter

227
6

There is any way to split it to 2 functions? the main function has to get only 2 lists as parameters – Dr.jj Dec 12 '22 at 22:26
it has a default parameter, so it can take only two parameters. calling func([1],[1]) for example will work as expected – codingStarter Dec 12 '22 at 22:29
The function returns True for the following: ([[1,2,3], [4,5,6]],[[1,2,3], [4,5,3]])) – Dr.jj Dec 12 '22 at 22:33
You got it! I still can't really understand what's going on here, so if you can briefly explain what is happening here, that would be amazing :) – Dr.jj Dec 12 '22 at 22:46
If my answer is correct, please mark it as accepted – codingStarter Dec 13 '22 at 00:01
No recursive call here is O(1). [`isinstance` is preferred over `type`](https://stackoverflow.com/questions/1549801/what-are-the-differences-between-type-and-isinstance). – ggorlen Dec 13 '22 at 03:26
@ggorlen I meant to what he asked, if you look in the comments of the question - no loop or other action that are more than 0(1) for each stage of the recursive call, I will fix the rest – codingStarter Dec 13 '22 at 12:46

Testing if 2d lists are equal with recursion

2 Answers2