Lecture "Dynamic programming algorithms", exercise 1

[essepuntato]

Write an extension of the multiplication function introduced in the chapter "Recursion", i.e. def multiplication(int_1, int_2, solution_dict), by using a dynamic programming approach. This new function takes in input two integers to multiply and a dictionary with solutions of 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.

[SarahTew]

This one works for 2 positive numbers and when int_1 is negative and int_2 is positive.

def multiplication(int_1, int_2, solution_dict):
   
    if int_1 > int_2:
        key_pair = (int_1, int_2)
    else:
        key_pair = (int_2, int_1)
    
    if key_pair not in solution_dict:
        if int_1 == 0 or int_2 == 0:
            solution_dict[key_pair] = 0
        else:
            solution_dict[key_pair] = int_1 + multiplication(int_1, int_2 - 1, solution_dict)
    return my_dict[key_pair]

my_dict = {}
print(multiplication(2,3, my_dict))
print(multiplication(5,7, my_dict))
print(multiplication(-4, 2, my_dict))

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
        
print(test_multiplication(2, 3, my_dict, 6))
print(test_multiplication(5, 7, my_dict, 35))
print(test_multiplication(-4, 2, my_dict, -8))
print(test_multiplication(0, 6, my_dict, 0))
print(test_multiplication(6, 0, my_dict, 0))

[dbrembilla]

Edited

def test(int_1, int_2, solution_dict, expected):
    return multiplication(int_1, int_2, solution_dict) == expected

def multiplication(int_1, int_2, solution_dict): #I stored the values using a tuple as key
    if (int_2, int_1) in solution_dict:
        return solution_dict[(int_2, int_1)]
    elif (int_1, int_2) or (int_2, int_1) not in solution_dict:
        if int_1 == 0 or int_2 == 0:
            return 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(0,0,{},0)) #true
print(test(9,3,{(3,4):12}, 27))#true
print(test(7,6,{(6,6):36}, 42))#true

[diegochillo]

I put some "print" to check if the program was fetching solutions from the dictionary or calculating them again.
I haven't worried about negative inputs because the original recursive function didn't take 'em in account.

def test_multiplication(int_1, int_2, d, expected):
     result = multiplication(int_1, int_2, d)
     return expected == result


def multiplication(int_1, int_2, d):
  
  si1=str(int_1); si2=str(int_2) # For debug purpose
  
  if int_1<=int_2:
    tpl=(int_1,int_2)
  else:
    tpl=(int_2,int_1)
  
  if tpl not in d:
     if (int_2 and int_1) == 0:
         d[tpl]=0
     else:
         d[tpl] = int_1 + multiplication(int_1, int_2 - 1,d)
         print ("DEBUG: Saved {} × {} = {}".format(si1,si2,str(d[tpl])))
  else:
     print ("DEBUG: Found {} × {} = {}".format(si1,si2,str(d[tpl])))
  
  return d[tpl]


# Test cases
solution_dict=dict()
print(test_multiplication(1, 8, solution_dict, 8)) 
print(test_multiplication(3, 7, solution_dict, 21))
print(test_multiplication(4, 5, solution_dict, 20))
print(test_multiplication(5, 4, solution_dict, 20))
print(test_multiplication(7, 3, solution_dict, 21))

print(test_multiplication(7, 5, solution_dict, 35))

print(test_multiplication(0, 6, solution_dict, 0))
print(test_multiplication(6, 0, solution_dict, 0))

[yunglong28]

def dyn_mul(int1, int2, dict1):
    factors = (int1, int2)
    if int1 == 0 or int2 == 0:  # base case 1
        dict1[factors] = 0
        return 0
    elif factors in dict1:  # base case 2
        return ('Already stored')
    else:
        dict1[factors] = int1 + dyn_mul(int1, int2 - 1, dict1)
    return dict1.get(factors)

def test_dyn_mul(int1, int2, dict1, expected):
    result = dyn_mul(int1, int2, dict1)
    if expected == result:
        return True
    else:
        return False

dictio2={}
print(test_dyn_mul (4, 2, dictio2, 8))  #True
print(test_dyn_mul(4, 2, dictio2, 'Already stored'))  #True
print(test_dyn_mul(-2, 3, dictio2, -6))  #True
print(test_dyn_mul(5, 6, dictio2, 30))  #True

[giorgiasampo]

def test_multiplication(int_1, int_2, solution_dict, expected):
    result = multiplication(int_1, int_2, solution_dict)
    return result==expected

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

print(test_multiplication(5,4,dict(), 20))
print(test_multiplication(0,4,dict(), 0))
print(test_multiplication(5,0,dict(), 0))

[ChiaraCati]

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 == 0 or int_1 == 0:
        solution_dict[int_2] = 0

    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, 2, dict(), 6))
print(test_multiplication(-3, 2, dict(), -6))
print(test_multiplication(0, 5, dict(), 0))
print(test_multiplication(9, 0, dict(), 0))

[GiuliaMenna]

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

def multiplication(int1, int2, solution_dict):
    if (int1, int2) not in solution_dict:
        if int1 == 0 or int2 == 0:
            return 0
        else:
            solution_dict[(int1,int2)] = int1 + multiplication(int1, int2 -1, solution_dict)
    return solution_dict.get((int1, int2))


print(test_multiplication(2,3,{},6))
print(test_multiplication(7,5,{},35))
print(test_multiplication(0,1,{},0))

[LuisAmmi]

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

def multiplication(int1, int2, dictionary):
    if (int1, int2) not in dictionary:
        if int1 == 0 or int2 == 0: # base case 1
            dictionary[(int1, int2)] = 0
        else:
            dictionary[(int1, int2)] = int1 + multiplication(int1, int2 - 1, dictionary)
    return dictionary.get((int1, int2))

print(test_multiplication(3,0,{},0))  # True
print(test_multiplication(9,3,{}, 27)) # True
print(test_multiplication(7,6,{}, 42)) # True

[AleRosae]

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

    return solution_dict.get(int_1)

def test_multiplication (int_1, int_2, solution_dict, expected):
    return multiplication(int_1, int_2, solution_dict) == expected


print(test_multiplication(4,4,dict(), 16))
print(test_multiplication(3,5,dict(), 15))
print(test_multiplication(3,1,dict(), 3))
print(test_multiplication(214566,0,dict(), 0))

[gabrielefiorenza]

def test_multiplication(int_1,int_2,solution_dict,expected):
    result = multiplication(int_1,int_2,solution_dict)
    return result== expected

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(4,7,dict(),28)) #it returns True

[AlessandroBertozzi]

I think this kind of programming approach is inefficient for this alghoritm. I don't reuse any element which I previously memorized in my dictionary.

[diegochillo]

I think this kind of programming approach is inefficient for this alghoritm. I don't reuse any element which I previously memorized in my dictionary.

It's efficient if you use the same dictionary for successive calls of the function: if after calculating 3x4 and storing the result in the dictionary, you call the function to calculate 3x9, the function will be faster because it'll find the solution of 3x4 in the dictionary and will not have to do again the recursions from 3x4 to 3x1.

[AlessandroBertozzi]

I think this kind of programming approach is inefficient for this alghoritm. I don't reuse any element which I previously memorized in my dictionary.

It's efficient if you use the same dictionary for successive calls of the function: if after calculating 3x4 and storing the result in the dictionary, you call the function to calculate 3x9, the function will be faster because it'll find the solution of 3x4 in the dictionary and will not have to do again the recursions from 3x4 to 3x1.

Yes, exactly. It is useful if you define a dictionary which is external to the function. Maybe another problem is that you can reuse the dictionary only with the same integer (int_1).

[diegochillo]

I think this kind of programming approach is inefficient for this alghoritm. I don't reuse any element which I previously memorized in my dictionary.

It's efficient if you use the same dictionary for successive calls of the function: if after calculating 3x4 and storing the result in the dictionary, you call the function to calculate 3x9, the function will be faster because it'll find the solution of 3x4 in the dictionary and will not have to do again the recursions from 3x4 to 3x1.

Yes, exactly. It is useful if you define a dictionary which is external to the function. Maybe another problem is that you can reuse the dictionary only with the same integer (int_1).

But if the key of your dictionary is the couple of factors (as a tuple), and if you always sort the couple in the same way before adding it to the dictionary and before looking for it, it's not important if the number you are reusing is int_1 or int_2.