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.

[delete4ever]

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

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

print(test_multiplication(123456, 78, dict(), 123456*78)) #True
print(test_multiplication(123456, 0, dict(), 0)) #True
print(test_multiplication(123456, 789, dict(), 123456*789)) #True

[n1kg0r]

def test_multiplication(int1, int2, expected):
    return multiplication(int1, int2, dict()) == 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)] = multiplication(int_1, int_2-1, solution_dict) + int_1 
    return solution_dict[(int_1, int_2)]

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

[EricaAndreose]

Update! Now I see what I got wrong.

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: dict):
    if int_1 > int_2:
        sol = (int_2, int_1)
    else: 
        sol = (int_1, int_2)

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

# Test runs returning True
print(test_multiplication(1, 0, dict(), 0))
print(test_multiplication(1, 2, dict(), 2))
print(test_multiplication(2, 5, dict(), 10))
print(test_multiplication(0, 5, dict(), 0))
print(test_multiplication(5, 1, dict(), 5))
print(test_multiplication(0, 0, dict(), 0))
print(test_multiplication(1, 0, dict(), 0))
print(test_multiplication(5, 7, dict(), 35))
print(test_multiplication(7, 7, dict(), 49))

Not sure it's the right solution. The two integers as input confused me a bit in interactions with the dictionary.

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: dict):
    sol = int_1 * int_2
    if sol not in solution_dict:
        if int_2 == 0:      # base case 1
            solution_dict[sol] = 0
        elif int_2 == 1:         # base case 2
            solution_dict[sol] = int_1
        else:      # recursive step
            solution_dict[sol] = int_1 + multiplication(int_1, int_2 - 1, solution_dict)
    return solution_dict.get(sol)

# Test runs returning True
print(test_multiplication(1, 0, dict(), 0))
print(test_multiplication(1, 2, dict(), 2))
print(test_multiplication(2, 5, dict(), 10))
print(test_multiplication(0, 5, dict(), 0))
print(test_multiplication(5, 1, dict(), 5))

[giorgiacrosilla]

# 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

# Code of the algorithm
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
        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.get(int_1 * int_2)

print(test_multiplication(0, 0, {}, 0))
print(test_multiplication(1, 0, {}, 0))
print(test_multiplication(2, 4, {}, 8))
print(test_multiplication(3, 3, {}, 9))

[lucia1299]

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

def multiplication_dict(int_1, int_2, solution_dict):
    solution_dict = dict()
    solution = int_1*int_2
    if solution in solution_dict:
        return solution_dict
    else:
        if int_2 == 0:
            solution = 0
            solution_dict["int1*2"] = solution
        else:
            solution = int_1 + multiplication_dict(int_1, int_2 - 1, solution_dict)
            solution_dict["int1*2"] = solution
        return solution

print(test_multiplication_dict(67, 0, {"int1*2", "0"}, 0)) #True 
print(test_multiplication_dict(9, 6, {"int1*2", "54"}, 54)) #True
print(test_multiplication_dict(5, 7, {"int1*2", "35"}, 35)) #True

[alka2696]

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_1 == 0 or int_2 == 0:
        return 0
    elif int_1 == 1:
        return int_2
    elif int_2 == 1:
        return int_1
    elif (int_1, int_2) in solution_dict:
        return solution_dict[(int_1, int_2)]
    elif (int_2, int_1) in solution_dict:
        return solution_dict[(int_2, int_1)]
    else:
        result = int_1 + multiplication(int_1, int_2-1, solution_dict)
        solution_dict[(int_1, int_2)] = result
        solution_dict[(int_2, int_1)] = result
        return result

solution_dict = {}

print(test_multiplication(0, 5, solution_dict, 0)) #True
print(test_multiplication(3, 2, solution_dict, 6)) #True