Comments (19)
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))
from 2020-2021.
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))
from 2020-2021.
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"))
from 2020-2021.
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
from 2020-2021.
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!"))
from 2020-2021.
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))
from 2020-2021.
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))
from 2020-2021.
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))
from 2020-2021.
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
from 2020-2021.
# 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
from 2020-2021.
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)
from 2020-2021.
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))
from 2020-2021.
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))
from 2020-2021.
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.
from 2020-2021.
@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.
from 2020-2021.
@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!
from 2020-2021.
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)))
from 2020-2021.
# 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)
from 2020-2021.
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
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 1 HOT 21
- 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.