Comments (21)
diegochillo
commented on August 27, 2024
1
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.
from 2020-2021.
SarahTew
commented on August 27, 2024
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))
from 2020-2021.
dbrembilla
commented on August 27, 2024
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
from 2020-2021.
diegochillo
commented on August 27, 2024
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))
from 2020-2021.
yunglong28
commented on August 27, 2024
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
from 2020-2021.
giorgiasampo
commented on August 27, 2024
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))
from 2020-2021.
ChiaraCati
commented on August 27, 2024
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))
from 2020-2021.
GiuliaMenna
commented on August 27, 2024
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))
from 2020-2021.
LuisAmmi
commented on August 27, 2024
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
from 2020-2021.
AleRosae
commented on August 27, 2024
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))
from 2020-2021.
gabrielefiorenza
commented on August 27, 2024
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
from 2020-2021.
AlessandroBertozzi
commented on August 27, 2024
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.
from 2020-2021.
AlessandroBertozzi
commented on August 27, 2024
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).
from 2020-2021.
diegochillo
commented on August 27, 2024
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.
from 2020-2021.
fcagnola
commented on August 27, 2024
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)
from 2020-2021.
AlessandroBertozzi
commented on August 27, 2024
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.
from 2020-2021.
AlessandroBertozzi
commented on August 27, 2024
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.
from 2020-2021.
AlessandraFa
commented on August 27, 2024
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))
from 2020-2021.
SofiBar
commented on August 27, 2024
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))
from 2020-2021.
essepuntato
commented on August 27, 2024
@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?
from 2020-2021.
IlaRoss
commented on August 27, 2024
# 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)
from 2020-2021.
Related Issues (20)
- Lecture "Brute-force algorithms", exercise 5 HOT 15
- Lecture "Organising information: unordered structures", exercise 1 HOT 21
- Lecture "Organising information: unordered structures", exercise 2 HOT 19
- Lecture "Organising information: unordered structures", exercise 3 HOT 20
- Lecture "Recursion", exercise 1 HOT 19
- Lecture "Recursion", exercise 2 HOT 20
- Lecture "Divide and conquer algorithms", exercise 1 HOT 19
- Lecture "Divide and conquer algorithms", exercise 2 HOT 17
- Lecture "Divide and conquer algorithms", exercise 3 HOT 5
- Lecture "Dynamic programming algorithms", exercise 2 HOT 19
- Lecture "Organising information: trees", exercise 1 HOT 9
- Lecture "Organising information: trees", exercise 2 HOT 7
- Bonus exercise (AtariGo) HOT 2
- Lecture "Backtracking algorithms", exercise 1 HOT 6
- Lecture "Backtracking algorithms", exercise 2 HOT 5
- Lecture "Organising information: graphs", exercise 1 HOT 15
- Lecture "Organising information: graphs", exercise 2 HOT 14
- Lecture "Greedy algorithms", exercise 1 HOT 5
- Lecture "Greedy algorithms", exercise 2 HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from 2020-2021.