Homework 3.17 - 3.18
Vocabulary
- Problem: A general description of a task that can or cannot be solved algorithmically
- Decision Problem: A problem with a yes or no answer
- Organization Problem: A problem with the goal of finding the best answer
- Instance: A problem with a specific input
- Efficiency: Amount of computing needed to solve a problem
- Polynomial Efficiency (Good): More work take sa proportional amount of time. 1 job = +2 time
- Exponential Efficiency (Bad): More work takes an exponential amount of time. 1 job = x2 time
- Heuristic Approach: When optimal solutions are inefficient, look for a possibly optimal solution that is more effecient
- Decidable Problem: A decision problme that has a clear solution that will always make a correct output
- Undecidable Problem: A decision problem with no solution that is not guaranteed to produce the correct output
import time
numlist = [1,3,5,7,9,11,13,15,17,19]
valuelist = [0,3,6,9,12,15,18,21]
def isvalue(value,array):
#--------------------
# Basic Binary Search
low = 0
high = len(array) - 1
while low < high:
middle = (low + high) // 2
if(array[middle] == value):
return True
# high = middle - 1
elif array[middle] < value:
low = middle + 1
return False
#--------------------
starttime = time.time()
for i in range(100000):
for i in range(len(valuelist)):
x = isvalue(valuelist[i],numlist)
endtime = time.time()
print(endtime-starttime,'seconds')
Homework!
Make an algorithm that finds the fastest route that hits every location once starting and ending at Del Norte. Make sure to show your thinking. If you are strugling, try using a huristic approach. Remember, what matters more than having perfectly functioning code is that you tried your hardest.
dataset = {
'DelNorte':{
'Westview':15,
'MtCarmel':20,
'Poway':35,
'RanchoBernrdo':50
},
'Westview':{
'DelNorte':15,
'MtCarmel':35,
'Poway':25,
'RanchoBernrdo': 45
},
'MtCarmel':{
'Westview':35,
'DelNorte':20,
'Poway':40,
'RanchoBernrdo':30
},
'Poway':{
'Westview':25,
'MtCarmel':40,
'DelNorte':35,
'RanchoBernrdo':15
},
'RanchoBernardo':{
'Westview':45,
'MtCarmel':30,
'Poway':15,
'DelNorte':50
}
}
def fastestroute(start,data):
drivetime = 0
order = []
for key1, value1 in dataset.items():
print("key1", key1, "value1", value1)
print(value1)
temp = ""
temp += key1
lowestValue = 0
for key2, value2 in value1.items():
print("value2", value2)
if lowestValue == 0:
lowestValue = value2
if value2 <= lowestValue:
lowestValue = value2
drivetime = drivetime + lowestValue
lowestKey = key2
order.append(key2)
print("Lowest Value is:", lowestValue)
print("Drivetime:", drivetime)
print("Lowest Key", lowestKey)
print(order)
return(drivetime,order)
dataset['start']
for data in dataset:
print(drivetime, order)
def nested_dict_values_iterator(data):
for value in data.values():
if isinstance(value, dict):
for v in nested_dict_values_iterator(value):
yield v
else:
yield value
#for value in nested_dict_values_iterator(dataset):
# print(value)
def fastestroute2(start, data):
drivetime = 0
order = []
order.append(start)
global lowestKey
lowestKey = start
for i in dataset:
#print("Dataset", dataset[i])
#print("data i: ", data[i].keys())
#print(data[i].values())
#print("Data Poway", data['Poway'])
for key2, value2 in dataset.items():
key2 = lowestKey
print("First Dictionary key2", key2, "value2", value2)
#print(value2)
temp = ""
temp += key2
lowestValue = 0
for key2, value2 in value2.items():
print("Second Dictionary key2", key2)
print("value2", value2)
if lowestValue == 0:
lowestValue = value2
if value2 <= lowestValue and key2 not in order:
lowestValue = value2
drivetime = drivetime + lowestValue
lowestKey = key2
print("Lowest key inside Second Dictionary : ", lowestKey)
# check if key is not already in order[]
if key2 not in order:
order.append(key2)
print("Lowest Value is:", lowestValue)
print("Drivetime:", drivetime)
print("Lowest Key", lowestKey)
print(order)
return(drivetime,order)
start = 'DelNorte'
fastestroute2(start,dataset)
# 'dataset' is the name of the nested key value pair
#fastestroute(start,dataset)
#print(data)
# print(data, dataset[data])
#print(dataset.values())
#min(dataset, key=dataset.get)
#print(dataset.values())
#print(max(dataset.values()))