Lecture "Dynamic programming algorithms", exercise 2
Opened this issue · 19 comments
essepuntato commented
Choose any recursive algorithm introduced in the previous chapters and provide a new implementation of it in Python following the dynamic programming approach.
SarahTew commented
I did the exponent algorithm from a previous set of exercises. I made two different programs, one that can only handle positive exponents and another one which can handle positive and negative exponents.
Positive Exponents Only:
def exponent_dict(base_number, exponent, dictionary):
key_pair = (base_number, exponent)
if exponent < 0:
return ("Positive Exponents Only!")
elif key_pair not in dictionary:
if exponent == 0:
return 1
else:
dictionary[key_pair] = base_number * exponent_dict(base_number, exponent - 1, dictionary)
return dictionary[key_pair]
my_dict = {}
print(exponent_dict(2,2,my_dict))
print(exponent_dict(3,3, my_dict))
print(exponent_dict(5,-2, my_dict))
print(exponent_dict(2, 0, my_dict))
def test_exponent_dict(base_number,exponent, dictionary, expected):
result = exponent_dict(base_number, exponent, dictionary)
if result == expected:
return True
else:
return False
print(test_exponent_dict(2,2,my_dict,4))
print(test_exponent_dict(2,1,my_dict,2))
print(test_exponent_dict(50,0, my_dict,1))
print(test_exponent_dict(3, -2, my_dict, "Positive Exponents Only!"))
Negative Exponents:
I kept getting an arithmetic error similar to what is happening here https://stackoverflow.com/questions/45071158/arithmetic-error-python-is-incorrectly-dividing-variables. In my code I have added rounding in order to get around this issue for large negative numbers. It rounds to the 17th place after the decimal point so that means it doesn't work correctly for very small negative exponents. I left a comment within the code if you want to see how it behaves without the rounding.
I understand why I'm getting the arithmetic error but I don't understand how to correct in this particular case. If anyone knows, please tell me.
def exponent2(base_number, exponent, dictionary):
key_pair = (base_number, exponent)
if key_pair not in dictionary:
if exponent == 0:
return 1
elif exponent <= 0:
dictionary[key_pair] = round(1 / base_number * exponent2(base_number, exponent + 1, dictionary),17)
#change the above line to see arithmetic error:
#dictionary[key_pair] = 1 / base_number * exponent2(base_number, exponent + 1, dictionary)
else:
dictionary[key_pair] = base_number * exponent2(base_number, exponent - 1, dictionary)
return dictionary[key_pair]
my_dict = {}
print(exponent2(2,2,my_dict))
print(exponent2(2,-1,my_dict))
print(exponent2(5,-3,my_dict))
print(exponent2(10, -8, my_dict))
def test_exponent2(base_number, exponent, dictionary, expected):
result = exponent2(base_number, exponent, dictionary)
if result == expected:
return True
else:
return False
print(test_exponent2(2,2,my_dict, 4))
print(test_exponent2(2,-1,my_dict, 0.5))
print(test_exponent2(5,-3,my_dict, 0.008))
diegochillo commented
Debug print instruction here too, to check when results are taken from the dictionary.
def exponentiation(base_number,exponent,d):
tpl=(base_number, exponent)
if tpl not in d:
if exponent == 0:
d[tpl]=1
elif exponent>0:
d[tpl]=base_number * exponentiation(base_number, exponent - 1,d)
else:
d[tpl]=(1 / base_number) * exponentiation(base_number, exponent+1,d)
else:
print ("DEBUG Found " + str(d[tpl]))
return d[tpl]
def test_exponentiation(base_number,exponent,d,expected):
result=exponentiation(base_number,exponent,d)
return result==expected
# Test cases
sd=dict()
print(test_exponentiation(17, 1, sd, 17))
print(test_exponentiation(2, 0, sd, 1))
print(test_exponentiation(3, 4, sd, 81))
print(test_exponentiation(3, 6, sd, 729))
print(test_exponentiation(3, 9, sd, 19683))
print(test_exponentiation(2, -4, sd, 0.0625))
print(test_exponentiation(2, -5, sd, 0.03125))
print(test_exponentiation(3, -3, sd, 0.037037037037037035))
giorgiasampo commented
def test_exponentiation(base, exp, solution_dict, expected):
result = exponentiation(base, exp, solution_dict)
return result==expected
def exponentiation(base, exp, solution_dict):
if base == 0:
solution_dict[base]= "Impossible"
elif exp == 0:
solution_dict[base]=1
elif exp == 1:
solution_dict[base] = base
else:
solution_dict[base] = base * exponentiation(base, exp - 1, solution_dict)
return solution_dict[base]
print(test_exponentiation(2,5,dict(),32))
print(test_exponentiation(2,0,dict(),1))
print(test_exponentiation(2,1,dict(),2))
print(test_exponentiation(0,5,dict(),"Impossible"))
dbrembilla commented
def exponentiation(base, exponent, sol_dict):
if base == 0 and exponent == 0:
return "Impossible"
elif base != 0 and exponent == 0:
return 1
elif exponent > 0 :
if base == 0:
return 0:
else:
sol_dict[(base, exponent)] = base * exponentiation(base, exponent-1, sol_dict)
elif exponent < 0: # rounded up to the 5th decimal
if base == 0:
return "Infinity"
else:
sol_dict[(base, exponent)] = round(1 / base * exponentiation(base, exponent+1, sol_dict), 5)
return sol_dict[(base, exponent)]
def test(base, exponent, sol_dict, expected):
return exponentiation(base, exponent, sol_dict) == expected
print(test(4,2,{}, 16)) #returns True
print(test(9,3, {}, 729))#returns True
print(test(4,-2,{},0.0625)) #True
print(test(0,0, {}, "Impossible"))#True
print(test(4,-5, {}, 0.00098))#True
AleRosae commented
def test_exp(base_number, exponent, sol_dict, expected):
return expected == exponentiation(base_number, exponent, sol_dict)
def exponentiation (base_number, exponent, sol_dict):
if base_number not in sol_dict:
if exponent == 0 and base_number == 0:
return "No!"
elif exponent == 0:
sol_dict[base_number] = 1
elif exponent == 1:
sol_dict[base_number] = base_number
elif exponent < 0:
sol_dict[base_number] = 1 / (base_number) * (exponentiation(base_number, exponent + 1, sol_dict))
else:
sol_dict[base_number] = base_number * exponentiation(base_number, exponent-1, sol_dict)
return sol_dict.get(base_number)
print(exponentiation(3,5,dict()))
print(test_exp(3,4, dict(), 81))
print(test_exp(17,1,dict(),17))
print(test_exp(2,0,dict(),1))
print(test_exp(2,-4,dict(),0.0625))
print(test_exp(0,0,dict(),"No!"))
LuisAmmi commented
def test_exponentiation(base_n, exp, dictionary, expected):
result = exponentiation(base_n, exp, dictionary)
if result == expected:
return True
else:
return False
def exponentiation(base_n, exp, dictionary):
if (base_n, exp) not in dictionary:
if exp == 0:
dictionary[(base_n, exp)] = 1 # base case
elif exp == 1:
dictionary[(base_n, exp)] = base_n # base case 2
else:
dictionary[(base_n, exp)] = base_n * exponentiation(base_n, exp - 1, dictionary)
return dictionary.get((base_n, exp))
print(test_exponentiation(3, 4, {}, 81)) # true
print(test_exponentiation(17, 1, {}, 17))
print(test_exponentiation(2, 0, {}, 1))
GiuliaMenna commented
def test_exp(base_number, exponent, dictionary, expected):
result = exp(base_number, exponent, dictionary)
if expected == result:
return True
else:
return False
def exp(base_number, exponent, dictionary):
if (base_number, exponent) not in dictionary:
if exponent == 0:
dictionary[(base_number, exponent)] = 1 #base case
else:
dictionary[(base_number, exponent)] = base_number * exp(base_number, exponent - 1, dictionary)
return dictionary.get((base_number, exponent))
print(test_exp(7,4, {}, 2401))
print(test_exp(28,1, {}, 28))
print(test_exp(9,0, {}, 1))
ChiaraCati commented
def test_exp(base, exponent, solution_dict, expected):
result = exponential(base, exponent, solution_dict)
if result == expected:
return True
else:
return False
def exponential(base, exponent, solution_dict):
if exponent >= 0: # for exponent
if exponent == 0:
solution_dict[exponent] = 1
elif exponent == 1:
solution_dict[exponent] = base
else:
solution_dict[exponent] = base * exponential(base, exponent - 1, solution_dict)
else:
n= 1 / base
if exponent == -1:
solution_dict[exponent] = n
else:
solution_dict[exponent] = round(n * exponential(base, exponent + 1, solution_dict), 2)
return solution_dict[exponent]
print(exponential(4, 2, dict()))
print(test_exp(3, 4, dict(), 81))
print(test_exp(17, 1, dict(), 17))
print(test_exp(2, 0, dict(), 1))
print(test_exp(4, -2, dict(), 0.06))
gabrielefiorenza commented
def test_binary_search(item, ordered_list, start, end,sd,expected):
result =binary_search(item, ordered_list, start, end,sd)
return expected == result
def binary_search(item, ordered_list, start, end,sd):
if item not in sd:
if item not in ordered_list:
sd[item]=None
else:
middle = (end-start)//2
if ordered_list[middle] == item:
sd[item] = middle+start
elif ordered_list[middle] < item:
sd[item]=binary_search(item,ordered_list,end-middle,end,sd)
elif ordered_list[middle] >item:
sd[item] = binary_search(item, ordered_list,start, start+middle,sd)
return sd.get(item)
mylist=list(["tablet", "pc", "pen","pencil","room"])
print(test_binary_search("pc",mylist,0,4,dict(),1)) # returns True
vanessabonanno commented
# dynamic programming approach
def test_exponentiation(num, exp, solution_dict, expected):
result = exponentiation(num, exp, solution_dict)
if result == expected:
return True
else:
return False
def exponentiation(num, exp, solution_dict):
if (num, exp) not in solution_dict:
if exp == 0:
# return 1 # original code - base condition now doesn't return 1
# but it adds elements to a dictionary:
solution_dict[(num, exp)] = 1
elif exp == 1:
# return num # original code
solution_dict[(num, exp)] = num
elif exp > 0:
# return num * exponentiation(num, exp - 1) # original code
solution_dict[(num, exp)] = num * exponentiation(num, exp - 1, solution_dict)
elif exp < 0:
# return 1 / num * exponentiation(num, exp + 1) # original code
solution_dict[(num, exp)] = 1 / num * exponentiation(num, exp + 1, solution_dict)
# I tried putting brackets before "num" and after "solution_dict)" above
# but somehow the result with a negative exponent was different (and wrong) than
# writing the division "1 / num * exponentiation(num, exp + 1, solution_dict)"
# without brackets and I don't understand why...
else:
return "Wrong input"
# at the end algorithm returns the value related to that key:
return solution_dict.get((num, exp))
my_dict = {}
print(exponentiation(3, 0, my_dict)) # output: 1
print(exponentiation(3, 2, my_dict)) # output: 9
print(exponentiation(3, 3, my_dict)) # output: 27
print(exponentiation(3, -3, my_dict)) # output: 0.037037037037037035
print(test_exponentiation(3, -3, my_dict, 0.037037037037037035)) # True
print(test_exponentiation(3, 0, my_dict, 0)) # False
fcagnola commented
from test import test_5_parameter
# dynamic programming approach
def binary_search(item, ordered_list, start, end, solutions):
if item in solutions: # base case for dynamic programming: if solution is in the dict, return that
return solutions[item]
mid = (start + end) // 2 # the middle of the section to be searched is stored in a variable
if item == ordered_list[mid]: # base case: if the item is found in the middle, return item and position
solutions[item] = mid # store the solution in the dict
return mid
elif start == mid: # with this line python won't raise RecursionError, if start == middle it means value not in list
return "Value not in list"
elif ordered_list[mid] < item: # if item comes after middle re-run search in the second half of the list
solutions[item] = binary_search(item, ordered_list, mid, end, solutions) # store the solution in the dict
return solutions[item]
elif ordered_list[mid] > item: # if item comes before middle re-run search in the first half of the list
solutions[item] = binary_search(item, ordered_list, start, mid, solutions) # store the solution in the dict
return solutions[item]
ord_list = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'z']
print(test_5_parameter(binary_search, "a", ord_list, 0, len(ord_list)-1, f, 0)) # Returns True
print(test_5_parameter(binary_search, "j", ord_list, 0, len(ord_list)-1, f, "Value not in list")) # Returns True
print(test_5_parameter(binary_search, "l", ord_list, 0, len(ord_list)-1, f, 9)) # Returns True
for i in "abcdefghijklmnopqrstuvwxyz":
print(binary_search(i, ord_list, 0, 21, d))
for i in "jaoknfbwobpqwmnsdènasjicubweovcpmdvowbjuvyvssca":
print(binary_search(i, ord_list, 0, len(ord_list)-1, d))
for i in "bvhsfoiuqgbawòodiaèpàòdhsjvblòoqèpwoiruytrhdsjalbcznm":
print(binary_search(i, ord_list, 0, len(ord_list) - 1, d))
print(d)
AlessandraFa commented
def test_new_exp(base_n, exp, exp_dict, expected):
result = new_exp(base_n, exp, exp_dict)
return result == expected
def new_exp(base_n, exp, exp_dic):
if base_n < 0:
return "Please insert positive base."
if exp <= 0 and base_n == 0:
return "Not possible. Try again."
if (base_n, exp) not in exp_dic:
if exp == 0:
exp_dic[(base_n, exp)] = 1
if exp < 0:
exp_dic[(base_n, exp)] = 1/base_n * new_exp(base_n, exp + 1, exp_dic)
else:
exp_dic[(base_n, exp)] = base_n * new_exp(base_n, exp - 1, exp_dic)
return exp_dic.get((base_n, exp))
dictionary = {}
print(test_new_exp(0, -2, dictionary, "Not possible. Try again."))
print(test_new_exp(2, 7, dictionary, 128))
print(test_new_exp(2, 3, dictionary, 8))
print(test_new_exp(-2, -4, dictionary, "Please insert positive base."))
print(test_new_exp(5, -1, dictionary, 1/5))
SofiBar commented
def exponentiation_dp(base_number, exponent, dic):
tup = (base_number, exponent)
if tup not in dic:
if exponent == 1:
dic[tup] = base_number
elif exponent == 0:
dic[tup] = 1
elif exponent < 0:
dic[tup] = 1/exponentiation_dp(base_number, -1*exponent, dic)
else:
dic[tup] = base_number*exponentiation_dp(base_number, exponent-1, dic)
return dic.get(tup)
def test_exponentiation_dp(base_number, exponent, dic, expected):
if exponentiation_dp(base_number, exponent, dic) == expected:
return True
else:
return False
expo_dict = {}
print(test_exponentiation_dp(2, 4, expo_dict, 16))
print(test_exponentiation_dp(-3, 1, expo_dict, -3))
print(test_exponentiation_dp(5, 0, expo_dict, 1))
print(test_exponentiation_dp(0, 4, expo_dict, 0))
print(test_exponentiation_dp(3, -2, expo_dict, 0.1111111111111111))
AlessandroBertozzi commented
def test_binary_search(item, ordered_list, start, end, empty_dictionary, expected):
result = binary_search(item, ordered_list, start, end, empty_dictionary)
return result == expected
library = {}
def binary_search(item, ordered_list, start, end, empty_dictionary):
my_list = ordered_list[start:end]
position = len(my_list) // 2
if item not in empty_dictionary:
# Basic case
if len(my_list) == 1 and item != my_list[position]:
return None
elif item == my_list[position]:
empty_dictionary[my_list[position]] = position
return position
# Divide and conquer
elif item < my_list[position]:
empty_dictionary[my_list[position]] = position
return binary_search(item, my_list, start, position, empty_dictionary)
else:
empty_dictionary[my_list[position]] = position
return position + binary_search(item, my_list, position, end, empty_dictionary)
else:
return empty_dictionary.get(item)
print(test_binary_search("Le metamorfosi", ["Alice in Wonderland", "Il castello", "Le chiavi del regno",
"Le metamorfosi", "Lolita", "Promessi sposi", "The Grapes of Wrath",
"The Great Gatsby"], 0, 7, library, 3))
print(test_binary_search("Le metamorfosi", ["Alice in Wonderland", "Il castello", "Le chiavi del regno",
"Le metamorfosi", "Lolita", "Promessi sposi", "The Grapes of Wrath",
"The Great Gatsby"], 0, 7, library, 3))
print(test_binary_search("Il castello", ["Alice in Wonderland", "Il castello", "Le chiavi del regno",
"Le metamorfosi", "Lolita", "Promessi sposi", "The Grapes of Wrath",
"The Great Gatsby"], 0, 7, library, 1))
I define an external dictionary and then, every time I run my function, I check if input book is in my library (list) menawhile storing its position in a dictionary for a future research.
essepuntato commented
@fcagnola and @AlessandroBertozzi: I believe that your approach works only if I use exactly the same list for all the various calls, otherwise you may get an error in return, right?
@fcagnola: it is important to define the tests, as required by the text of the exercise. As far as I can see, you avoid doing that since you prefer to run several executions of the function. But this does not allow you to check if the result you obtain after each execution is correct or not.
fcagnola commented
@fcagnola and @AlessandroBertozzi: I believe that your approach works only if I use exactly the same list for all the various calls, otherwise you may get an error in return, right?
@fcagnola: it is important to define the tests, as required by the text of the exercise. As far as I can see, you avoid doing that since you prefer to run several executions of the function. But this does not allow you to check if the result you obtain after each execution is correct or not.
@essepuntato you are right, for both observations. I hadn't really though of that limit, but it is in fact the case. If I were to, in any way, alter the input list, the algorithm would not work.
As for the test part, it was only laziness on my part, I had actually implemented the usual test function, I just hadn't copied it to the comment, I will edit the code and add it in now. thank you for taking the time to read all our code!
edoardodalborgo commented
def test_pokemon_champion(input_list, i, dict, expected):
return pokemon_champion(input_list, i, dict) == expected
def pokemon_champion(input_list, i, dict):
if len(input_list) > 1:
if i < len(input_list):
left = input_list[i]
right = input_list[i+1]
if right > left:
pair = (left, right)
else:
pair = (right, left)
if pair not in dict:
if left[1] > right[2]:
input_list.remove(right)
dict[pair] = left
else:
input_list.remove(left)
dict[pair] = right
i += 1
pokemon_champion(input_list, i, dict)
else:
i = 0
pokemon_champion(input_list, i, dict)
return input_list[0]
i = 0
my_rec_dict = {}
pokemon_tournament = [("Poliwag",10,5), ("Charmander",15,2), ("Abra",8,7), ("Pidgey",4,5), ("Goldeen",6,8), ("Bulbasaur",12,10), ("Charmeleon",18,8), ("Psyduck",3,4)]
print(test_pokemon_champion(pokemon_tournament, i, my_rec_dict, ('Bulbasaur', 12, 10)))
pokemon_tournament1 = [("Poliwag",10,5), ("Charmander",15,2), ("Abra",8,7), ("Pidgey",4,5), ("Goldeen",6,8), ("Charmeleon",18,8), ("Psyduck",3,4), ("Pidgey",4,5)]
print(test_pokemon_champion(pokemon_tournament1, i, my_rec_dict, ("Poliwag",10,5)))
IlaRoss commented
# tests
def test_exponentiation(base_number, exponent, solution_dictionary, expected):
result = exponentiation(base_number, exponent, solution_dictionary)
if result == expected:
return True
else:
return False
# algorithm
def exponentiation(base_number, exponent, solution_dictionary):
if base_number == 0:
return 0
else:
if exponent == 0:
return 1
mykey = (base_number, exponent)
if mykey in solution_dictionary.keys():
return solution_dictionary[mykey]
else:
if exponent > 0:
result = base_number * exponentiation(base_number, exponent-1, solution_dictionary)
solution_dictionary[mykey] = result
elif exponent < 0:
result = 1 / base_number * (exponentiation(base_number, exponent + 1, solution_dictionary))
solution_dictionary[mykey] = result
return solution_dictionary[mykey]
# test runs
adict = {}
print(test_exponentiation(3, 4, adict, 81))
print(test_exponentiation(17, 1, adict, 17))
print(test_exponentiation(2, 0, adict, 1))
print(test_exponentiation(3, 2, adict, 9))
print(test_exponentiation(0, 5, adict, 0))
print(test_exponentiation(-2, 3, adict, -8))
print(test_exponentiation(3, 0, adict, 1))
#print(adict)
yunglong28 commented
Sorry for not posting this before. I added the string to the already stored result option just to diversify the two outputs.
def dyamic_exponentiation (base, exponent, dict1):
power = (base, exponent)
if power not in dict1:
if exponent == 0:
dict1[power] = 1
elif exponent > 0:
dict1[power] = base * dyamic_exponentiation(base, exponent - 1, dict1)
else:
dict1[power] = (1 / base) * dyamic_exponentiation(base, exponent + 1, dict1)
else:
return "I stored the result already: " + str(dict1.get(power))
return dict1[power]
def test_dynamic_exponentiation (base, exponent, dict1, expected):
result = dyamic_exponentiation(base, exponent, dict1)
if result == expected:
return True
else:
return False
dictio = {}
print(test_dynamic_exponentiation(1, 0, dictio, 1)) #True
print(test_dynamic_exponentiation(1, 0, dictio,'I stored the result already: 1')) #True
print(test_dynamic_exponentiation(3,2, dictio, 9)) #True
print(test_dynamic_exponentiation(2, -2, dictio, 0.25)) #True