Lecture "Dynamic programming algorithms", exercise 1

[essepuntato]

Using a dynamic programming approach, write an extension of the multiplication function introduced in the chapter "Recursion", i.e. def multiplication(int_1, int_2, solution_dict). This new function takes in input two integers to multiply and a dictionary with multiplications between numbers. The function returns the result of the multiplication and, at the same time, modifies the solution dictionary adding additional solutions when found. Accompany the implementation of the function with the appropriate test cases.

[AmeliaLamargese]

def test_multiplication(int1, int2, solution_dict, expected):
    result = multiplication_dp(int1, int2, solution_dict)
    if result == expected:
        return True
    else:
        return False    

def multiplication_dp(int1, int2, solution_dict):
    key = str(int1) + "_" + str(int2)
    if key not in solution_dict:   
        if int2 == 0:
            solution_dict[key] = 0
        elif int2 == 1:
            solution_dict[key] = int1
        else:
            solution_dict[key] = int1 + multiplication_dp(int1, int2-1, solution_dict)    

    return solution_dict.get(key)      

print(test_multiplication(2, 3, dict(), 6))
print(test_multiplication(2, 0, dict(), 0))
print(test_multiplication(2, 1, dict(), 2))
print(test_multiplication(10, 3, dict(), 30))

[Bianca-LM]

def test_multiplication(int_1, int_2, solution_dict, expected):
    result = multiplication(int_1, int_2, solution_dict)
    if expected == result:
        return True
    else:
        return False

def multiplication(int_1, int_2, solution_dict):
    if int_1*int_2 not in solution_dict: 
        if int_2 == 0:
            solution_dict[int_1*int_2] = 0
        else:
            solution_dict[int_1*int_2] = int_1 + multiplication(int_1, int_2 - 1, solution_dict)
    return solution_dict.get(int_1*int_2)

print(test_multiplication(2, 3, dict(), 6))
print(test_multiplication(2, 3, dict({2*3: 6}), 6))

[11051620]

[ManueleVeggi]

The dynamic programming algorithm could be written as:

def test_multiplication(int_1, int_2, solution_dict, expected):
    result = multiplication(int_1, int_2, solution_dict)
    if result == expected:
        return True
    else:
        return False

def multiplication(int_1, int_2, solution_dict):
    if int_2 not in solution_dict:
        if int_2 == 0:
            solution_dict[int_2] = 0
        elif int_2 == 1:
            solution_dict[int_2] = int_1
        else: 
            solution_dict[int_2] = int_1 + multiplication(int_1, int_2 - 1, solution_dict)
    
    return solution_dict.get(int_2)

print(test_multiplication(3,0,dict(),0))
print(test_multiplication(3,1,dict(),3))
print(test_multiplication(3,2,dict(),6))
print(test_multiplication(3,0,{0:0, 1:3, 2:6, 3:9},0))
print(test_multiplication(3,1,{0:0, 1:3, 2:6, 3:9},3))
print(test_multiplication(3,2,{0:0, 1:3, 2:6, 3:9},6))

The output is True for all the test cases

[chloeppd]

def test_multiplication(n1,n2,solution_dict,expected):
    result= multiplication(n1,n2,solution_dict)
    if result == expected:
        return True
    else:
        return False


def multiplication(n1,n2,solution_dict):
    if n1*n2 not in solution_dict:
        if n1==0 or n2==0:
            solution_dict[n1*n2]=0
        
        else: 
            solution_dict[n1*n2] = n1+multiplication(n1,n2-1, solution_dict)
    

    return solution_dict.get(n1*n2)   


dict1 = dict()
dict2= {2*6:12} 
print(test_multiplication(0,3,dict1,0))
print(test_multiplication(1,2,dict1,2))
print(test_multiplication(0,0,dict2,0))
print(test_multiplication(2,8,dict2,16))

[olgagolgan]

[martasoricetti]

[CarmenSantaniello]

def test_multiplication(int_1, int_2, solution_dict, expected):
    result = multiplication(int_1, int_2, solution_dict)
    if expected == result:
        return True
    else:
        return False

def multiplication(int_1, int_2, solution_dict):
    if int_2 not in solution_dict:
        if int_2 == 0:
            solution_dict[int_2] = 0
        elif int_2 == 1:
            solution_dict[int_2] = int_1 
        else:
            solution_dict[int_2] = int_1 + multiplication(int_1, int_2 - 1, solution_dict)

    return solution_dict.get(int_2)

print(test_multiplication(1,3,dict(),3))
print(test_multiplication(4,1,dict(),4))
print(test_multiplication(2,0,dict(),0))
print(multiplication(1,3,dict()))
print(multiplication(4,1,dict()))
print(multiplication(2,0,dict()))

[federicabonifazi]

def test_multiplication(int_1, int_2, solution_dict, expected):
    result=multiplication(int_1, int_2, solution_dict)
    if result==expected:
        return True
    else:
        return False


multiplication_dict={}
def multiplication(int_1, int_2, solution_dict):
    if int_1*int_2 not in solution_dict:
        if int_2==0 or int_1==0:
            solution_dict[int_1*int_2] = 0
        else:
            solution_dict[int_1*int_2] = int_1 + multiplication(int_1, int_2-1, solution_dict)                    
    return solution_dict.get(int_1*int_2)

print(test_multiplication(2, 4, multiplication_dict, 8))
print(test_multiplication(3, 5, multiplication_dict, 15))
print(test_multiplication(2, 0, multiplication_dict, 0))
print(test_multiplication(12, 67, multiplication_dict, 804))
print(test_multiplication(-2, 5, multiplication_dict, -10))
print(test_multiplication(-2, -2, multiplication_dict, 4))

[tommasobattisti]

def test_multiplication(int_1, int_2, solution_dict, expected):
    result = multiplication(int_1, int_2, solution_dict)
    if expected == result:
        return True
    else:
        return False

mult_dict = {}

def multiplication(int_1, int_2, solution_dict):
    factors = (int_1, int_2)
    if factors not in solution_dict:
        if int_2 == 0:
            solution_dict[factors] = 0
        elif int_1 == 1:
            solution_dict[factors] = int_2
        elif int_2 == 1:
            solution_dict[factors] = int_1
        else:
            solution_dict[factors] = int_1 + multiplication(int_1, int_2 -1 , solution_dict)
    return solution_dict.get(factors)


print(test_multiplication(7, 1, mult_dict, 7))
print(test_multiplication(1, 4, mult_dict, 4))
print(test_multiplication(7, 4, mult_dict, 28))
print(test_multiplication(7, 3, mult_dict, 21))
print(test_multiplication(3, 0, mult_dict, 0))

[AnastasiyaSopyryaeva]

# Test case for the function
def test_multiplication_extended(int_1, int_2, solution_dict, expected):
    result = multiplication_extended(int_1, int_2, solution_dict)
    if expected == result:
        return True
    else:
        return False


# Code of the function
def multiplication_extended(int_1, int_2, solution_dict):
    if int_1*int_2 not in solution_dict:
        if int_2 == 0 or int_1 == 0:
            solution_dict[int_1*int_2] = 0
        elif int_1 == 1:
            solution_dict[int_1*int_2] = int_2
        elif int_2 == 1:
            solution_dict[int_1*int_2] = int_1
        else: 
            solution_dict[int_1*int_2] = int_1 + multiplication_extended(int_1, int_2 - 1, solution_dict)
    return solution_dict.get(int_1*int_2)


print(test_multiplication_extended(3,0,dict(),0)) #true
print(test_multiplication_extended(3,1,dict(),3)) #true
print(test_multiplication_extended(3,2,dict(),6)) #true
print(test_multiplication_extended(3,6,{3*6:18, 5*5:25},18))  #true
print(test_multiplication_extended(6,5,{4*8:32, 10*3:30, 20*5:100},30)) #true

[angstigone]

[ghasempouri1984]

my_dict = {}

#  the function
def multiplication(int_1, int_2, solution_dict):
    if int_1 < int_2:
        mult_pair = (int_1, int_2)
    else:
        mult_pair = (int_2, int_1)

    if mult_pair not in solution_dict:
        if int_2 == 0:
            solution_dict[mult_pair] = 0
        else:
            solution_dict[mult_pair] = int_1 + multiplication(int_1, int_2 - 1, solution_dict)

    return solution_dict[mult_pair]

# Test case 
def test_multiplication(int_1, int_2, solution_dict, expected):
    result = multiplication(int_1, int_2, solution_dict)
    if expected == result:
        return True
    else:
        return False

print(test_multiplication(0, 0, my_dict, 0))
print(test_multiplication(1, 0, my_dict, 0))
print(test_multiplication(2, 3, my_dict, 6))

[essepuntato]

Hi,

just a few comments for you to check in your solutions:

• You cannot use the multiplication operator "*" in the definition of your function since you are actually defining such an operator with your function. Using "*" is like defining a term in a word dictionary by using itself in the definition! Your function should define the operation, not reuse the existing one. Revise your algorithm to avoid using "*".

• Try to run your function passing the same dictionary with existing solutions in all the tests, avoiding creating a new dictionary every time. To do that, just initialise an empty dictionary in a variable and then pass it every time as input of your tests.

• Try to run your code using Python Tutor and see if the dictionary with existing solutions is used in some tests. If it is not used in all the tests, then what's the usefulness of having such a dictionary? Two possible explanations of this situation may be that (a) you are not storing the solutions in the dictionary as you think and, as such, they are not reused, or (b) you create a new dictionary in every test and thus no past solutions are really reused. Modify your code to avoid such situations.

[ahsanv101]

print(test_mult_rec(3, 3, dict(), 9))
print(test_mult_rec(2, 0, dict(), 0))
print(test_mult_rec(0, 34, dict(), 0))
print(test_mult_rec(1, 6, dict(), 6))

[RebeccaJillianBeattie]

[teragramgius]

This issue made me think of the tables that were at the last page of copybooks at the elementary school.

So at a first sight, I tried to show the binar characteristic of the muktiplication function htat takes as input two integers and a dictionary.

Indeed, the multiplication is commutative, this also means that it takes just a 0 to have the result equal to zero, for example.

A first attempt was naming two different tuples, i.e. tuple_x and tuple_y, but at the end I wasn't able to have a satysfing result.

So I tried in another way, having two tuples named in the same way, but in which the order of the two factors switches.

def test_multiplication(int_1, int_2, solution_dict, expected):

result = multiplication(int_1, int_2, solution_dict)

if expected == result:

return True

else:

return False

def multiplication(int_1, int_2, solution_dict):

solution_dict = {}

if int_1 < int_2:

twodimensiontuple = (int_1, int_2)

else:

twodimensiontuple = (int_2, int_1)

if twodimensiontuple not in solution_dict:

if int_2 == 0:

solution_dict[twodimensiontuple] = 0

else:

solution_dict[twodimensiontuple] = int_1 + multiplication(int_1, int_2 - 1, solution_dict)

return solution_dict[twodimensiontuple]

testdict = {}

print(test_multiplication(1, 0, testdict, 0)) True

print(test_multiplication(1, 2, testdict, 2)) True

print(test_multiplication(4, 8, testdict, 32)) True

print(test_multiplication(5, 12, testdict, 60)) True