Failed test cases are 9,15,21 (Help)

This is the program
def multiply_optimized(poly1,poly2):
if not poly1 and not poly2:
return []
if poly1 == []:
return poly2
if poly2 == []:
return poly1
if len(poly1) == 1:
if poly1[0] == 0:
return [0]
else:
return [poly1[0]* x for x in poly2]
elif len(poly2) == 1:
if poly2[0] == 0:
return [0]
else:
return [poly2[0]* y for y in poly1]
(A0,A1),(B0,B1) = split(poly1,poly2)
Y = multiply_optimized(add(A0,A1),add(B0,B1))
U = multiply_optimized(A0,B0)
Z = multiply_optimized(A1,B1)
temp_ = add(U,Z)
temp = subtract(Y, temp_)
mid = max(len(poly1), len(poly2))
n = mid//2
return add(add(U,increase_exponent(temp, n)),increase_exponent(Z, 2*n))

This is addition: -
def add(poly1, poly2):
result = [0] * max(len(poly1), len(poly2))
for i in range(len(result)):
if i < len(poly1):
result[i] += poly1[i]
if i < len(poly2):
result[i] += poly2[i]
return result

This is subtraction:-
def subtract(poly1,poly2):
result = [0] * max(len(poly1), len(poly2))
for i in range(len(result)):
if i < len(poly2):
result[i] = poly2[i] - result[i]
if i < len(poly1):
result[i] = poly1[i] - result[i]
return result

Hey, I think I replied to you in the previous post.
Did you try this?
https://jovian.ai/forum/t/what-is-the-wrong-in-this-code/38274/2?u=utkarsh736

Yes i tried this but still it’s not working

were the same test getting failed?

9, 15, 21 these tests are failed

can you try this in your computer to get the proper result?

hey please help me I stucked here from lots of time. I am not getting what may be the problem there

I meant when you made the suggested changes did the same tests failed?
Also, these are the Jovian test cases for submission or your own test cases?

yes I failed the same test cases of jovian even i made chenges in code

def multiply_optimized(poly1,poly2):
if not poly1 and poly2:
return []

if len(poly1) == 1:
    if poly1[0] == 0:
        return [0]
    else:
        return [poly1[0]* x for x in poly2]
    
elif len(poly2) == 1:
    if poly2[0] == 0:
        return [0]
    else:
        return [poly2[0]* y for y in poly1]
    
(A0,A1),(B0,B1) = split(poly1,poly2)
Y = multiply_optimized(add(A0,A1),add(B0,B1))
U = multiply_optimized(A0,B0)
Z = multiply_optimized(A1,B1)
temp_ = add(U,Z)
temp = subtract(Y, temp_)
mid = max(len(poly1), len(poly2))
n = mid//2
return add(add(U,increase_exponent(temp, n)),increase_exponent(Z, 2*n))

This error i got at test case 20 when i did changes as you say
But test case 21 is passed only test case 9,15 are not passed and at test case 20 got this error
: maximum recursion depth exceeded in comparison
RecursionError: maximum recursion depth exceeded in comparison

We want to return an empty list when either of the lists poly1 or poly2 is empty.
if not poly1 or poly2:

and will check if both are empty, since we need to check if even 1 is empty, we need to use or.

There might be some other changes required but maybe first try this.

ok i will try this first

hey i made the changes which you suggested me but now it shows most of the test cases are failed.
def multiply_optimized(poly1,poly2):
if not poly1 or poly2:
return []

if len(poly1) == 1:
    if poly1[0] == 0:
        return [0]
    else:
        return [poly1[0]* x for x in poly2]
    
elif len(poly2) == 1:
    if poly2[0] == 0:
        return [0]
    else:
        return [poly2[0]* y for y in poly1]
    
(A0,A1),(B0,B1) = split(poly1,poly2)
Y = multiply_optimized(add(A0,A1),add(B0,B1))
U = multiply_optimized(A0,B0)
Z = multiply_optimized(A1,B1)
temp_ = add(U,Z)
temp = subtract(Y, temp_)
mid = max(len(poly1), len(poly2))
n = mid//2
return add(add(U,increase_exponent(temp, n)),increase_exponent(Z, 2*n))

How is it performing on your defined test cases?
Can you link your notebook?

Also, some conditions like

if poly1[0] == 0:
    return [0]

Might be giving wrong answers.

A look at your defined test cases might give a better understanding.

for the following test case my function add unexpected numbers like 0,-1,-2.
input:-
‘poly1’: [1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 9, 9, 9, 9, 99, 0, 0, 0, -1, -2],
‘poly2’: [6, 4, 3, 2, 9, 0, -2, 1, 2, 3, 5, 6, 7]

Expected:-
[6, 16, 29, 44, 68, 92, 114, 137, 162, 184, 207, 233, 264, 286, 848, 638, 535, 439, 1063, 175, 7, 298, 374, 441, 614, 660, 689, -7, -11, -16, -19, -14]

my output :-
[6, 16, 29, 44, 68, 92, 114, 137, 162, 184, 207, 233, 264, 286, 848, 638, 535, 439, 1062, 173, 7, 298, 374, 442, 616, 660, 689, -7, -10, -14, -19, -14, 0, -1, -2]

Here my function add unexpected numbers in reverse order 0, -1, -2.

I believe the change we made earlier is correct but there might be some other errors in the code.
Like the subtract function or some condition.
Maybe link your code or notebook or post the code in code format and I might be able to have a better understanding.

I’m facing a similar issue, all but #15 is getting passed. I also avoided using the sub function completely:

def multiply_optimized(poly1, poly2):
    
    if len(poly1) == 1 and poly2[len(poly1) - 1] == 0 or len(poly2) == 1 and poly2[len(poly2) - 1] == 0:
        result = [0]
    elif len(poly1) == 0 or len(poly2) == 0:
        result = [0]
    elif len(poly1) == 1:
        result = [poly1[0] * poly2[i] for i in range(len(poly2))]
    elif len(poly2) == 1:
        result = [poly2[0] * poly[i] for i in range(len(poly1))]
    else:
        n = max(len(poly1), len(poly2))
        poly1, poly2 = split(poly1, poly2)
        
        Y = multiply_optimized(add(poly1[0], poly1[1]), add(poly2[0], poly2[1]))
        U = multiply_optimized(poly1[0], poly2[0])
        Z = multiply_optimized(poly1[1], poly2[1])
        Z1 = increase_exponent(Z, 2*(n//2))
        X = add(U, Z)
        X1 = increase_exponent(add(Y, [-x for x in X]), n//2)  # sub here
        Y1 = add(U, X1)
        
        print(U, Z, X1)
        
        
        result = add(Y1, Z1)
        
    return result

Hey @sanghamitra1-618 I tried your code and it seems to work fine for the test case you mentioned in an earlier discussion and other test cases that I tried.

But it seems to fail for test cases that have an empty list or null list like [0,0,0] or something like that.

I think that your recursion part is alright, and the problem seems to be in the bases cases, especially for conditions that handle empty lists or null lists.

Could you try to explain the base cases as to how they are functioning or take a look at them yourself, you might find the error.

Hey so I tried your code, and one basic error that we missed was in my suggestion
instead of
if not poly1 or poly2, it should be,
if not ploy1 or not poly2.
We missed the not for poly2,(my bad).
Because of this the function never really did anything it just checked the first condition and when there was any element in poly2 which would be most cases it would return [].

There still seems to be some error as it failed one case with null lists but that would be from the base case, making this correction would solve most of the test cases.

First, let’s correct that and we’ll look at the base case next