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.

[frammenti]

Improved version with only one for cycle in the dictionary

def test_multiplication_dp2(n1, n2, solution_dict):
    expected = n1 * n2
    result = multiplication_dp2(n1, n2, solution_dict)
    return result == expected

def multiplication_dp2(n1, n2, solution_dict):
    if n1 < n2:
        n1, n2 = n2, n1
    # Computation of shortest route to target
    yn = n1 + n2 # generation
    xn = n1 - n2 # position in generation
    s = n2 # steps
    t1, t2 = n1, 0 # target coordinates
    for (d1, d2) in solution_dict:
        if d1 < d2:
            d1, d2 = d2, d1
        yd = d1 + d2
        xd = d1 - d2
        if 0 <= abs(xn - xd) <= 2:
            sd = abs(yn - yd)
        else:
            sd = abs(xn - xd)
        # If it takes fewer steps to get to dictionary item considered, target is changed
        if sd < s:
            s = sd
            t1, t2 = d1, d2
    # Steps split for n1 and n2
    s1 = t1 - n1
    s2 = t2 - n2
    # Recursive step
    return multiplication(n1, n2, s1, s2, solution_dict)

def multiplication(n1, n2, s1, s2, solution_dict):
    key = (n1, n2)
    rkey = (n2, n1)
    if key not in solution_dict and rkey not in solution_dict:
        if n2 == 0:
            solution_dict[key] = 0
        elif s1 < 0:
            solution_dict[key] = n2 + multiplication(n1 - 1, n2, s1 + 1, s2, solution_dict)
        elif s2 < 0:
            solution_dict[key] = n1 + multiplication(n1, n2 - 1, s1, s2 + 1, solution_dict)
        elif s1 > 0:
            solution_dict[key] = multiplication(n1 + 1, n2, s1 - 1, s2, solution_dict) - n2
        elif s2 > 0:
            solution_dict[key] = multiplication(n1, n2 + 1, s1, s2 - 1, solution_dict) - n1
    elif rkey in solution_dict:
        solution_dict[key] = solution_dict.pop(rkey)
    return solution_dict[key]

solution_dict1 = {(7, 5): 35}
solution_dict2 = {(8, 5): 40}
solution_dict3 = {(7, 5): 35, (8, 5): 40}
solution_dict4 = {(13, 4): 52}
solution_dict5 = {(13, 2): 26}
solution_dict6 = {(3, 4): 12}
solution_dict7 = {(2, 2): 4}

print(test_multiplication_dp2(7, 7, solution_dict1))
print(test_multiplication_dp2(9, 7, solution_dict1))
print(test_multiplication_dp2(9, 7, solution_dict2))
print(test_multiplication_dp2(10, 7, solution_dict3))
print(test_multiplication_dp2(10, 7, solution_dict4))
print(test_multiplication_dp2(10, 7, solution_dict5))
print(test_multiplication_dp2(5, 5, solution_dict6))
print(test_multiplication_dp2(5, 5, solution_dict7))

print(solution_dict1)
# {(7, 5): 35, (7, 6): 42, (7, 7): 49, (8, 7): 56, (9, 7): 63}
print(solution_dict2)
# {(8, 5): 40, (8, 6): 48, (8, 7): 56, (9, 7): 63}
print(solution_dict3)
# {(7, 5): 35, (8, 5): 40, (8, 6): 48, (8, 7): 56, (9, 7): 63, (10, 7): 70}
print(solution_dict4)
# {(13, 4): 52, (12, 4): 48, (11, 4): 44, (10, 4): 40, (10, 5): 50, (10, 6): 60, (10, 7): 70}
print(solution_dict5)
# {(13, 2): 26, (10, 0): 0, (10, 1): 10, (10, 2): 20, (10, 3): 30, (10, 4): 40, (10, 5): 50, (10, 6): 60, (10, 7): 70}
print(solution_dict6)
# {(4, 3): 12, (4, 4): 16, (4, 5): 20, (5, 5): 25}
print(solution_dict7)
# {(2, 2): 4, (5, 0): 0, (5, 1): 5, (5, 2): 10, (5, 3): 15, (5, 4): 20, (5, 5): 25}

Old version

def test_multiplication_dp(n1, n2, solution_dict):
    expected = n1 * n2
    result = multiplication_dp(n1, n2, solution_dict)
    return result == expected

def multiplication_dp(n1, n2, solution_dict):
    n1, n2 = factor_swap(n1, n2, solution_dict)
    key = (n1, n2)
    rkey = (n2, n1)
    if key not in solution_dict and rkey not in solution_dict:
        if n2 == 0:
            solution_dict[key] = 0
        else:
            result = n1 + multiplication_dp(n1, n2 - 1, solution_dict)
            solution_dict[key] = result
    elif rkey in solution_dict:
        result = solution_dict.pop(rkey)
        solution_dict[key] = result
    return solution_dict[key]

def factor_swap(n1, n2, solution_dict):
    if n1 != n2:
        for ni in range(n1, -1, -1):
            if (ni, n2) in solution_dict or (n2, ni) in solution_dict:
                delta1 = n1 - ni
                break
        else:
            delta1 = n1
        for ni in range(n2, -1, -1):
            if (n1, ni) in solution_dict or (ni, n1) in solution_dict:
                delta2 = n2 - ni
                break
        else:
            delta2 = n2
        if delta1 < delta2:
            n1, n2 = n2, n1
    return n1, n2

solution_dict1 = {(7, 5): 35}
solution_dict2 = {(8, 5): 40}
solution_dict3 = {(7, 5): 35, (8, 5): 40}

print(test_multiplication_dp(7, 7, solution_dict1))
print(test_multiplication_dp(9, 7, solution_dict1))
print(test_multiplication_dp(9, 7, solution_dict2))
print(test_multiplication_dp(10, 7, solution_dict3))

print(solution_dict1)
# {(7, 5): 35, (7, 6): 42, (7, 7): 49, (7, 8): 56, (7, 9): 63}
print(solution_dict2)
# {(5, 8): 40, (5, 9): 45, (9, 6): 54, (9, 7): 63}
print(solution_dict3)
# {(7, 5): 35, (8, 5): 40, (8, 6): 48, (8, 7): 56, (7, 9): 63, (7, 10): 70}

[katyakrsn]

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:  # base case 1
            solution_dict[int_1, int_2] = 0
        elif int_2 == 1:  # base case 2
            solution_dict[int_1, int_2] = int_1
        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), 0)

print(test_multiplication(3, 4, {}, 12))  # test case: 3 * 4 = 12
print(test_multiplication(5, 0, {}, 0))  # test case: 5 * 0 = 0
print(test_multiplication(0, 9, {}, 0))  # test case: 0 * 9 = 0

[valentinabertelli]

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
        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, 4, dict(), 12)) #True
print (test_multiplication(5, 10, dict(), 50)) #True
print (test_multiplication(8, 2, dict(), 16)) #True
print (test_multiplication(3, 0, dict(), 0)) #True

[qwindici]

New solution using the same dictionary in every test

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

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

my_dict = {}
print(test_multiplication(3, 10, my_dict, 30))
print(test_multiplication(0, 2, my_dict, 0))
print(test_multiplication(5, 7, my_dict, 35))
print(test_multiplication(15, 4, my_dict, 60))
print(test_multiplication(2, 7, my_dict, 14))
print(my_dict)

Same idea using tuples

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

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

my_dict = {}
print(test_multiplication(3, 10, my_dict, 30))
print(test_multiplication(0, 2, my_dict, 0))
print(test_multiplication(5, 7, my_dict, 35))
print(test_multiplication(15, 4, my_dict, 60))
print(test_multiplication(2, 7, my_dict, 14))
print(my_dict)

Old version:

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

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

print(test_multiplication(3, 10, {}, 30))
print(test_multiplication(0, 2, {}, 0))
print(test_multiplication(5, 7, {}, 35))
print(test_multiplication(15, 4, {}, 60))

[vattelalberto]

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
        else:
            solution_dict[int_2] = int_1 + multiplication(int_1, int_2 - 1, solution_dict)

    return solution_dict[int_2]

print(test_multiplication(0, 0, dict(), 0))
print(test_multiplication(1, 0, dict(), 0))
print(test_multiplication(5, 7, dict(), 35))

[Liber-R]

[simocasaz]

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
        else:
            solution_dict[int_2] = int_1 + multiplication(int_1, int_2 - 1, solution_dict)

    return solution_dict.get(int_2)

print(test_multiplication(6, 5, dict(), 30))
print(test_multiplication(6, 8, dict(), 48))
print(test_multiplication(8, 0, dict(), 0))
print(test_multiplication(0, 0, dict(), 0))
print(test_multiplication(34, 523, dict(), 17782))
print(test_multiplication(5, 32, dict(), 160))

[rufferbaraldi]

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

print(test_multiplication(4, 3, dict(), 12))
print(test_multiplication(5, 2, dict(), 10)) 
print (test_multiplication(7, 2, dict(), 14))
print (test_multiplication(2, 0, dict(), 0))

[CarlaMenegat]

[Chiaramartina]

[essepuntato]

Thanks for your take. Just a few comments:

• @qwindici @vattelalberto @CarlaMenegat, try to run an additional, last test, i.e. print(test_multiplication(2, 7, my_dict, 14)) by passing a dictionary that will be modified by all the previous tests.
• @simocasaz, try to run an additional, last test, i.e. print(test_multiplication(2, 32, my_dict, 64)) by passing a dictionary that will be modified by all the previous tests.
• @rufferbaraldi, try to run the tests by always passing the same dictionary (that will be modified in each test.
• @Chiaramartina, try to run an additional, last test, i.e. print(test_multiplication(2, 8, my_dict, 16)) by passing a dictionary that will be modified by all the previous tests.

[MariaFrancesca6]

def test_multiplication(int_1,int_2,solution_dict,expected):
    result = multiplication(int_1, int_2, solution_dict)
    if result == expected:
        return True
    else:
        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_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(5,4,{},20))
print(test_multiplication(3,0,{},0))

[matildepassafaro]

# test case for the function
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

# code for the function
def multiplication(int_1, int_2, solution_dict):
    # checking if solution exists
    my_key = (int_1, int_2)
    if my_key not in solution_dict:
        # base case
        if int_1 == 0 or int_2 == 0:
            solution_dict[my_key] = 0
        # recursive step
        else:
            solution_dict[my_key] = int_1 + multiplication(int_1, int_2 - 1, solution_dict)

    return solution_dict.get(my_key)

# tests
print(test_multiplication(3, 4, dict(), 12))
print(test_multiplication(7, 8, dict(), 56))
print(test_multiplication(0, 0, dict(), 0))
print(test_multiplication(0, 3, dict(), 0))

[Sergpoipoip]

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

def multiplication(int_1, int_2, solution_dict):
    if int_1 < int_2:
        int_1, int_2 = int_2, int_1
    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] = multiplication(int_1, int_2 - 1, solution_dict) + int_1
    return solution_dict.get((int_1, int_2))

solution_dict = {}
print(test_multiplication(3, 10, solution_dict, 30))
print(test_multiplication(0, 0, solution_dict, 0))
print(test_multiplication(11, 1, solution_dict, 11))

[vattelalberto]

Revised version of my algorithm, now that I actually understood the purpose of using a dictionary

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):
    #to avoid redundant entries in the dictionary the first element is always the greater
    if int_1 < int_2:
         return multiplication(int_2, int_1, solution_dict)
    if (int_1, int_2) not in solution_dict:
        #check for basic solution when multiplied by 0
        if int_2 == 0:
            solution_dict[(int_1, int_2)] = 0
        #check for basic solution when multiplied by 1
        elif int_2 == 1:
            solution_dict[(int_1, int_2)] = int_1
        else:
            solution_dict[(int_1, int_2)] = int_1 + multiplication(int_1, int_2 - 1, solution_dict)

    return solution_dict[(int_1, int_2)]

my_dict = dict()

print(test_multiplication(0, 0, my_dict, 0))
print(test_multiplication(1, 0, my_dict, 0))
print(test_multiplication(5, 7, my_dict, 35))
print(test_multiplication(2, 7, my_dict, 14))
print(test_multiplication(7, 2, my_dict, 14))

[valetedd]

def test_multiplication_dp(n, m, d, expected):
    result = multiplication_dp(n, m, d)
    if expected == result:
        return True
    else:
        return False
# Code of the function
def multiplication_dp(n, m, d):
# Checking if a solution exists
    if n * m not in d:
        if m == 0 or n == 0: # base case 
            d[n * m] = 0 
        else: # recursive step
        # the dictionary will be passed as input of the recursive
        # calls of the function
            d[n * m] = n + multiplication_dp(n, m - 1, d)
    return d.get(n * m)

empty_dic = {}

#tests
print(test_multiplication_dp(3, 5, empty_dic, 15))
print(test_multiplication_dp(-1, 7, empty_dic, -7))
print(test_multiplication_dp(20, 50, empty_dic, 1000))
print(test_multiplication_dp(-17, -5, empty_dic, 85))
print(test_multiplication_dp(0, 0, empty_dic, 0))
print(test_multiplication_dp(1, 1, empty_dic, 1))