161 lines
6.3 KiB
Python
161 lines
6.3 KiB
Python
# Student ID: 012498637
|
|
# Student Name: Zakaria Benmoulay
|
|
# Course: C950 - Data Structures and Algorithms II
|
|
|
|
from datetime import datetime, timedelta
|
|
|
|
|
|
SPEED_MPH = 18 # all trucks travel at 18 mph
|
|
HUB_ADDRESS = "Salt Lake City, UT 84107" # WGU hub — matches the distance table
|
|
|
|
|
|
class Truck:
|
|
# Let's initialize the truck with assigned packages and starting conditions.
|
|
def __init__(self, truck_id, packages, depart_time, package_table,
|
|
address_list, distance_matrix):
|
|
|
|
self.truck_id = truck_id
|
|
self.package_ids = list(packages) # copy so original list is not modified
|
|
self.depart_time = depart_time
|
|
self.package_table = package_table
|
|
self.address_list = address_list
|
|
self.distance_matrix = distance_matrix
|
|
|
|
# Simulation state — updated as deliver_all() runs
|
|
self.current_address = HUB_ADDRESS # truck starts at the hub
|
|
self.current_time = depart_time # clock starts at departure time
|
|
self.total_miles = 0.0 # accumulates mileage during delivery
|
|
self.route = [] # list of (package_id, address, arrival_time)
|
|
|
|
|
|
# Distance and time helpers
|
|
def _distance(self, addr_a, addr_b):
|
|
|
|
def find_index(addr):
|
|
addr_clean = addr.strip().lower()
|
|
|
|
# Pass 1: exact match
|
|
for i, a in enumerate(self.address_list):
|
|
if a.strip().lower() == addr_clean:
|
|
return i
|
|
|
|
# Pass 2: substring match (handles abbreviations and extra words)
|
|
for i, a in enumerate(self.address_list):
|
|
if addr_clean in a.strip().lower() or a.strip().lower() in addr_clean:
|
|
return i
|
|
|
|
# Pass 3: match on the first two tokens (street number + street name)
|
|
tokens = addr_clean.split()
|
|
if tokens:
|
|
prefix = " ".join(tokens[:2])
|
|
for i, a in enumerate(self.address_list):
|
|
if a.strip().lower().startswith(prefix):
|
|
return i
|
|
|
|
raise ValueError(f"Address not found in distance table: '{addr}'")
|
|
|
|
i = find_index(addr_a)
|
|
j = find_index(addr_b)
|
|
return self.distance_matrix[i][j]
|
|
|
|
def _travel_time(self, miles):
|
|
|
|
hours = miles / SPEED_MPH
|
|
return timedelta(hours=hours)
|
|
|
|
|
|
# Core nearest-neighbor delivery algorithm
|
|
def deliver_all(self, return_to_hub=False):
|
|
|
|
# Step 1 — Mark all packages on this truck as En Route at departure time
|
|
for pid in self.package_ids:
|
|
pkg = self.package_table.lookup(pid)
|
|
if pkg:
|
|
pkg.mark_en_route(self.depart_time, self.truck_id)
|
|
|
|
# Work from a copy so the original package_ids list is preserved
|
|
remaining = list(self.package_ids)
|
|
|
|
# Step 2 — Nearest-neighbor delivery loop
|
|
while remaining:
|
|
|
|
# Inner scan: find the package with the shortest distance
|
|
# from the truck's current location
|
|
nearest_pid = None
|
|
nearest_dist = float("inf") # start with infinity so any real distance wins
|
|
|
|
for pid in remaining:
|
|
pkg = self.package_table.lookup(pid)
|
|
if pkg is None:
|
|
continue
|
|
|
|
# Get the correct address for this package at this time
|
|
# (handles Package 9's address correction at 10:20 AM)
|
|
address = self._resolve_address(pid, self.current_time)
|
|
dist = self._distance(self.current_address, address)
|
|
|
|
# Update nearest if this package is closer than the current best
|
|
if dist < nearest_dist:
|
|
nearest_dist = dist
|
|
nearest_pid = pid
|
|
|
|
if nearest_pid is None:
|
|
break # safety check — should not happen with valid data
|
|
|
|
# Step 2b — Drive to the nearest package's address
|
|
pkg = self.package_table.lookup(nearest_pid)
|
|
dest_address = self._resolve_address(nearest_pid, self.current_time)
|
|
travel = self._travel_time(nearest_dist)
|
|
|
|
self.current_time += travel # advance the simulated clock
|
|
self.total_miles += nearest_dist # accumulate mileage
|
|
self.current_address = dest_address # move truck to new location
|
|
|
|
# Step 2c — Mark the package as delivered at the current time
|
|
pkg.mark_delivered(self.current_time)
|
|
self.route.append((nearest_pid, dest_address, self.current_time))
|
|
|
|
# Step 2d — Remove from remaining list
|
|
remaining.remove(nearest_pid)
|
|
|
|
# Step 3 — Return to hub if needed (for driver reassignment to Truck 3)
|
|
if return_to_hub:
|
|
dist_home = self._distance(self.current_address, HUB_ADDRESS)
|
|
self.total_miles += dist_home
|
|
self.current_time += self._travel_time(dist_home)
|
|
self.current_address = HUB_ADDRESS
|
|
|
|
# Package 9 address correction
|
|
def _resolve_address(self, package_id, current_time):
|
|
|
|
pkg = self.package_table.lookup(package_id)
|
|
|
|
if package_id == 9:
|
|
# Define the correction time as 10:20 AM on the simulation date
|
|
correction_time = self.depart_time.replace(
|
|
hour=10, minute=20, second=0, microsecond=0
|
|
)
|
|
if current_time >= correction_time:
|
|
return "410 S State St" # corrected address after 10:20 AM
|
|
else:
|
|
return pkg.address # wrong address before 10:20 AM
|
|
|
|
return pkg.address # all other packages return their address unchanged
|
|
|
|
|
|
# Route summary display
|
|
def print_route(self):
|
|
|
|
print(f"\n=== Truck {self.truck_id} Route ===")
|
|
print(f"Departed hub : {self.depart_time.strftime('%I:%M %p')}")
|
|
for pid, addr, arrival in self.route:
|
|
pkg = self.package_table.lookup(pid)
|
|
deadline = pkg.deadline if pkg else "?"
|
|
print(
|
|
f" Pkg {pid:>2} -> {addr:<40} "
|
|
f"Arrived: {arrival.strftime('%I:%M %p')} "
|
|
f"Deadline: {deadline}"
|
|
)
|
|
print(f"Total miles : {self.total_miles:.2f}")
|
|
print(f"Finished at : {self.current_time.strftime('%I:%M %p')}")
|