Homework 8
the homework for 17 and 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 a 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 takes a proportional amount of time (1 job is +2 time)
- Exponential Efficiency (Bad): more work takes an exponential amount more time (1 job is 2x time)
- Heuristic Approach: When optimal solutions are inefficient, look for a possibly optimal solution that is more efficient
- Decidable Problem: A decision problem that has a clear solution that will always make a correct output
- Undecidable Problem: A decision problem with no solution that is not gaurenteed 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):
#--------------------
exists = False
while exists == False:
for i in range(len(array)):
if value == array[i]:
exists = True
return exists
if exists == False:
return exists
#--------------------
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,
'RanchoBernardo':50
},
'Westview':{
'DelNorte':15,
'MtCarmel':35,
'Poway':25,
'RanchoBernardo': 45
},
'MtCarmel':{
'Westview':35,
'DelNorte':20,
'Poway':40,
'RanchoBernardo':30
},
'Poway':{
'Westview':25,
'MtCarmel':40,
'DelNorte':35,
'RanchoBernardo':15
},
'RanchoBernardo':{
'Westview':45,
'MtCarmel':30,
'Poway':15,
'DelNorte':50
}
}
import random
s = 900 #perm
t = 0 #temp
bruh = [] # perm
help = [] # temp
print(dataset["DelNorte"])
def r():
return random.randrange(4)
def ui(mu, oh):
m = 0
global t
for n, c in mu.items():
if m == oh:
t += c
return n
m += 1
def uid(mu, oh):
global t
for n, c in mu.items():
if n == oh:
t += c
return n
def listaddomgihatethissomuch():
i = 0
global help
global bruh
bruh.clear()
while i < len(help):
bruh.append(help[i])
i += 1
def dupcheck():
global help
lll = help[0:5]
lom = set(help[0:5])
if len(lll) != len(lom):
return False
else:
return True
def n():
global s
global t
a = ui(dataset["DelNorte"], r())
help.append("DelNorte")
help.append(a)
b = ui(dataset[a], r())
help.append(b)
c = ui(dataset[b], r())
help.append(c)
d = ui(dataset[c], r())
help.append(d)
e = uid(dataset[d], "DelNorte")
help.append(e)
if dupcheck() == True:
if t < s:
s = t
listaddomgihatethissomuch()
t = 0
help.clear()
adding = 0
while adding < 1000:
n()
adding += 1
print(s)
print(bruh)
oh my god i just looked at the requirements and there's no way im doing that right now. right now being 7:42 pm on thursday. I think I could definitely do that but I spent so much time doing this that I don't want to. there wasn't really anything too hard about this. the only thing slowing me was my self. I kept getting off track and couldn't think several times while trying to figure out what i was doing. I could have done this pretty quickly if I was normal and had an attention span longer than a goldfish. The code isnt too hard to understand. there's two lists and two variables. one pair is temporary and the other pair is the final pair. the temporary pair resets after each loop. if the temporary variable (the distance) is less than the final variable, then the final list and variable change to the temporary variable and list's values. The order of schools is randomized. It doesn't check for duplicates and doesn't end on del norte. it does, however, start on del norte.
Ignore the whining of the little baby up there ^^^ I figured it out.