Answer To: Core Algorithm Overview Ryan Hildebrant C950: Data Structures & Algorithms II Student # XXXXXXXXXX...
Sandeep Kumar answered on May 04 2021
New/DeliveryStatus.py
IN_ROUTE = "In route"
DELIVERED = "Delivered"
AT_HUB = "At hub"
New/DistanceData.py
import csv
import datetime
from truck import truck, TRUCK_SPEED
# Read the map of distances between locations
with open('WGUPS_DISTANCE_FILE.csv') as input_file:
distance_list = csv.reader(input_file, delimiter=',')
distance_list = list(distance_list)
#(distance_list)
# Read the csv of address locations
with open('WGUPS_LOCATION_FILE.csv') as input_file:
location_list = csv.reader(input_file, delimiter=',')
location_list = list(location_list)
#print(location_list)
#Computes distance from point A to point B
def point_distance(a, b):
d = distance_list[a][b]
#Try it transposed if we can't find it
if d is '':
d = distance_list[b][a]
return d
New/Distances.py
import datetime
from truck import truck, TRUCK_SPEED
from IngestData import distances,locations
# a list of row/column values are inserted into this function. This function then calculates the total distance
# that distance is then returned and each iteration represents a distance between two locations
# Space-time complexity is O(1)
# Computes distance from point A to point B
def point_distance(a, b):
d = distances[a][b]
# Try it transposed if we can't find it
if d is '':
d = distances[b][a]
return float(d)
def check_distance(row_value, column_value, sum_of_distance):
distance = distances[row_value][column_value]
if distance is '':
distance = distances[column_value][row_value]
sum_of_distance += float(distance)
return sum_of_distance
# this function is very similar to the function above but returns a current distance
# Space-time complexity is O(1)
def check_current_distance(row_value, column_value):
distance = distances[row_value][column_value]
#Transpose the X and Y if we can't find it
if distance is '':
distance = distances[column_value][row_value]
return float(distance)
# this is the time that the first truck leaves the hub
first_time_list = ['8:00:00']
second_time_list = ['9:10:00'] #Don't let second truck leave until package is corrected
third_time_list = ['11:00:00']
# this function takes a distance then divides it by TRUCK_SPEED. It then uses divmod to display a time and appends 00
# this string that is a timestamp is then split and turned into a datetime timedelta object
# that object is then added to sum which represents total distance for a particular truck
# runtime of function is O(N)
def check_time_first_truck(distance):
new_time = distance / TRUCK_SPEED
distance_in_minutes = '{0:02.0f}:{1:02.0f}'.format(*divmod(new_time * 60, 60))
final_time = distance_in_minutes + ':00'
first_time_list.append(final_time)
sum = datetime.timedelta()
for i in first_time_list:
(h, m, s) = i.split(':')
d = datetime.timedelta(hours=int(h), minutes=int(m), seconds=int(s))
sum += d
return sum
# Repeated function for second truck
def check_time_second_truck(distance):
new_time = distance / TRUCK_SPEED
distance_in_minutes = '{0:02.0f}:{1:02.0f}'.format(*divmod(new_time * 60, 60))
final_time = distance_in_minutes + ':00'
second_time_list.append(final_time)
sum = datetime.timedelta()
for i in second_time_list:
(h, m, s) = i.split(':')
d = datetime.timedelta(hours=int(h), minutes=int(m), seconds=int(s))
sum += d
return sum
# Repeated function for the third truck
def check_time_third_truck(distance):
new_time = distance / TRUCK_SPEED
distance_in_minutes = '{0:02.0f}:{1:02.0f}'.format(*divmod(new_time * 60, 60))
final_time = distance_in_minutes + ':00'
third_time_list.append(final_time)
sum = datetime.timedelta()
for i in third_time_list:
(h, m, s) = i.split(':')
d = datetime.timedelta(hours=int(h), minutes=int(m), seconds=int(s))
sum += d
return sum
# this function returns the time objects to use in the Packages.py file
# Space-time complexity is O(1)
def check_address():
return locations
# these lists represent the sorted trucks that are put in order of efficiency in the function below
first_optimized_truck = []
first_optimized_truck_index_list = []
second_optimized_truck = []
second_optimized_truck_index_list = []
third_optimized_truck = []
third_optimized_truck_index_list = []
def calculate_shortest_distance(truck_distance_list, truck_number, current_location): # section 1
if len(truck_distance_list) == 0: # section 2
return truck_distance_list
else: #
try:
lowest_value = 50.0
new_location = 0
for index in truck_distance_list:
if check_current_distance(current_location, int(index[1])) <= lowest_value:
lowest_value = check_current_distance(current_location, int(index[1])) # section 3
new_location = int(index[1])
for index in truck_distance_list: # section 4
if check_current_distance(current_location, int(index[1])) == lowest_value:
if truck_number == 1:
first_optimized_truck.append(index)
first_optimized_truck_index_list.append(index[1])
pop_value = truck_distance_list.index(index)
truck_distance_list.pop(pop_value)
current_location = new_location
calculate_shortest_distance(truck_distance_list, 1, current_location)
elif truck_number == 2:
second_optimized_truck.append(index)
second_optimized_truck_index_list.append(index[1])
pop_value = truck_distance_list.index(index)
truck_distance_list.pop(pop_value)
current_location = new_location
calculate_shortest_distance(truck_distance_list, 2, current_location)
elif truck_number == 3:
third_optimized_truck.append(index)
third_optimized_truck_index_list.append(index[1])
pop_value = truck_distance_list.index(index)
truck_distance_list.pop(pop_value)
current_location = new_location
calculate_shortest_distance(truck_distance_list, 3, current_location)
except IndexError:
pass
first_optimized_truck_index_list.insert(0, '0')
# Space-time complexity is O(1)
def first_optimized_truck_index():
return first_optimized_truck_index_list
# Space-time complexity is O(1)
def first_optimized_truck_list():
return first_optimized_truck
second_optimized_truck_index_list.insert(0, '0')
# Space-time complexity is O(1)
def second_optimized_truck_index():
return second_optimized_truck_index_list
# Space-time complexity is O(1)
def second_optimized_truck_list():
return second_optimized_truck
third_optimized_truck_index_list.insert(0, '0')
# Space-time complexity is O(1)
def third_optimized_truck_index():
return third_optimized_truck_index_list
# Space-time complexity is O(1)
def third_optimized_truck_list():
return third_optimized_truck
New/HashTable.py
class HashTable:
# Just a convenience method to print out the whole table
def print(self):
print(*self.hashtable)
# Constructor
# space-time complexity O(1)
def __init__(self, size=40):
# initialize the hash table with empty bucket list entries.
self.hashtable = []
for kvp in range(size):
self.hashtable.append([])
# Getter to generate a key
# space-time complexity O(1)
def _get_hashkey(self, key):
return int(key) % len(self.hashtable)
# Inserts a new PackageEntry into the HashTable
# space-time complexity O(N)
def insert(self, key, value):
kv = [key, value]
hashkey = self._get_hashkey(key)
# Brand new insertion
if self.hashtable[hashkey] is None:
self.hashtable[hashkey] = kv
return True
else:
# Overwrite any previous value
for kvp in self.hashtable[hashkey]:
if kvp[0] == key:
kvp[1] = kv
return True
self.hashtable[hashkey].append(kv)
return True
# Remove a value from the hash table
# runtime is O(N)
def delete(self, key):
hashkey = self._get_hashkey(key)
# Nothing to delete
if self.hashtable[hashkey] is None:
return False
# Search the whole table for the key
for kvp in range(0, len(self.hashtable[hashkey])):
if self.hashtable[hashkey][kvp][0] == key:
self.hashtable[hashkey].pop(kvp)
return True
# Was none
return False
# Returns a value associated with a key
# space-time complexity O(N)
def get(self, key):
hashkey = self._get_hashkey(key)
if self.hashtable[hashkey] is not None:
for kvp in self.hashtable[hashkey]:
if kvp[0] == key:
return kvp[1]
# Couldn't find a value
...