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.

[fcagnola]

d = dict()  # this dictionary will store the results of the multiplications in this form {"int1Xint2":result}

def multiplication(int_1, int_2, solutions):

    if str(int_1)+"X"+str(int_2) in solutions:  # base case: result is in the dict, either "int1Xint2" or "int2Xint1"
        return solutions[str(int_1)+"X"+str(int_2)]
    elif str(int_2)+"X"+str(int_1) in solutions:
        return solutions[str(int_2)+"X"+str(int_1)]

    else:
        if int_2 == 0:  # base case for the recursion, if the number is multiplied by 0, add result to dict and return 0
            solutions[str(int_1) + "X" + str(int_2)] = 0
            return 0
        else:  # otherwise compute the solution recursively, store it in the dictionary and return that entry
            solutions[str(int_1) + "X" + str(int_2)] = int_1 + multiplication(int_1, int_2 - 1, solutions)
            return solutions[str(int_1) + "X" + str(int_2)]

# test case, in this function I thought it would be useful to use many numbers in order to see the efficiency in action.
# printing the dict after computing all the results show how many computations have not been calculated twice thanks 
# to the dynamic programming approach
for one in [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]: 
    for two in [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]:
        print(multiplication(one, two, d))

print(d)

[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).

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.

Yeah, sorting can be a good solution for this problem.

[AlessandroBertozzi]

d = dict()  # this dictionary will store the results of the multiplications in this form {"int1Xint2":result}

def multiplication(int_1, int_2, solutions):

    if str(int_1)+"X"+str(int_2) in solutions:  # base case: result is in the dict, either "int1Xint2" or "int2Xint1"
        return solutions[str(int_1)+"X"+str(int_2)]
    elif str(int_2)+"X"+str(int_1) in solutions:
        return solutions[str(int_2)+"X"+str(int_1)]

    else:
        if int_2 == 0:  # base case for the recursion, if the number is multiplied by 0, add result to dict and return 0
            solutions[str(int_1) + "X" + str(int_2)] = 0
            return 0
        else:  # otherwise compute the solution recursively, store it in the dictionary and return that entry
            solutions[str(int_1) + "X" + str(int_2)] = int_1 + multiplication(int_1, int_2 - 1, solutions)
            return solutions[str(int_1) + "X" + str(int_2)]

# test case, in this function I thought it would be useful to use many numbers in order to see the efficiency in action.
# printing the dict after computing all the results show how many computations have not been calculated twice thanks 
# to the dynamic programming approach
for one in [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]: 
    for two in [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]:
        print(multiplication(one, two, d))

print(d)

Yeah, in your case the function saved 45 passages. But if i change the number which are not very similar, the problem remain. More times you use this function with an external dict, more possibilites you have to save passages in the future multiplication.

[AlessandraFa]

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:
        mykey = (int_1, int_2)
    else:
        mykey = (int_2, int_1)
    if mykey not in solution_dict:
        if int_1 == 0 or int_2 == 0:
            solution_dict[mykey] = 0
        else:
            solution_dict[mykey] = int_1 + multiplication(int_1, int_2 - 1, solution_dict)
    return solution_dict.get(mykey)

my_dict = {}

print(test_multiplication(0, 0, my_dict, 0))
print(test_multiplication(12, 6, my_dict, 72))
print(test_multiplication(7, 5, my_dict, 35))
print(test_multiplication(5, 7, my_dict, 35))
print(test_multiplication(3, 7, my_dict, 21))
print(test_multiplication(3, 8, my_dict, 24))
print(test_multiplication(3, 3, my_dict, 9))

[SofiBar]

def test_multiplication_dp(int_1, int_2, dic, expected):
    if multiplication_dp(int_1, int_2, dic) == expected:
        return True
    else:
        return False

def multiplication_dp(int_1, int_2, dic):
    k = (int_1, int_2)

    if int_2 < 0:
        return "parameter not valid"

    if k not in dic:
        if int_2 == 0:
            dic[k] = 0
        elif int_2 == 1:
            dic[k] = int_1
        else:
            dic[k] = int_1 + multiplication_dp(int_1, int_2 - 1, dic)
        return dic.get(k)

dict_n = {}
print(test_multiplication_dp(3, 4, dict_n, 12))
print(test_multiplication_dp(-3, 4, dict_n, -12))
print(test_multiplication_dp(-3, -4, dict_n, "parameter not valid"))
print(test_multiplication_dp(0, 1, dict_n, 0))

[essepuntato]

@dbrembilla, just a suggestion: remind that the multiplication is commutative (i.e. n1 * n2 == n2 * n1), which means that if you already computed the solution of n1 * n2, then you have also the solution for n2 * n1.

About @yunglong28's code:

return ('Already stored')

You should return the value, not "Already stored".

For all (in case you did not do it): try to create just one dictionary before running the tests and then passing every time that dictionary as input of your executions. Does it work always as expected?

[IlaRoss]

# Test case for the algorithm
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

# Algorithm
def multiplication(int_1, int_2, solution_dict):
    if int_1 == 0 or int_2 == 0:
        return 0

    if int_1 > int_2:
        mymult = [int_2, int_1]
        akey = tuple(mymult)
    else:
        mymult = [int_1, int_2]
        akey = tuple(mymult)

    if (akey) in solution_dict.keys():
        return solution_dict[akey]
    else:
        if mymult[1] == 0:
            return 0
        else:
            result = mymult[0] + multiplication(mymult[0], mymult[1]-1, solution_dict)
            mykey = tuple(mymult)
            solution_dict[(mykey)] = result

        return solution_dict[(mykey)]

# Some test runs
adict = {}
print(test_multiplication(3, 5, adict, 15))
print(test_multiplication(4, 4, adict, 16))
print(test_multiplication(3, 4, adict, 12))
print(test_multiplication(7, 6, adict, 42))
print(test_multiplication(0, 0, adict, 0))
print(test_multiplication(0, 3, adict, 0))
print(test_multiplication(6, 7, adict, 42))
print(test_multiplication(7, 5, adict, 35))

# print(adict)