#!/usr/bin/env python3
"""
Saskatchewan HVAC Geographic Route Optimizer
Complete re-think of routes from scratch using actual geography
"""

from dataclasses import dataclass
from typing import List, Tuple, Optional
import math

# Constants
MILES_TO_KM = 1.60934
AVG_SPEED_KMH = 80
SITE_VISIT_HOURS = 2.5
REGULAR_HOURS = 8
MAX_HOURS = 12
OVERTIME_MULTIPLIER = 1.5

# Costs (user provided)
HOURLY_RATE = 85
MILEAGE_RATE = 1.25  # per km

# Hotel cost estimate for overnight stays
HOTEL_COST = 150

@dataclass
class Site:
    name: str
    lat: float
    lng: float
    km_from_regina: float
    km_from_saskatoon: float

# Parse coordinates from Book 4 (converting DMS to decimal)
def dms_to_decimal(dms_str):
    """Convert DMS string like '50°39'21.67"N' to decimal degrees"""
    # Clean up the string
    dms_str = dms_str.strip().replace('°', ' ').replace("'", ' ').replace('"', ' ')
    dms_str = dms_str.replace('�', ' ')  # Handle encoding issues
    parts = dms_str.split()
    try:
        degrees = float(parts[0])
        minutes = float(parts[1]) if len(parts) > 1 else 0
        seconds = float(parts[2].rstrip('NSEW')) if len(parts) > 2 else 0
        decimal = degrees + minutes/60 + seconds/3600
        if 'S' in dms_str or 'W' in dms_str:
            decimal = -decimal
        return decimal
    except:
        return None

def haversine_km(lat1, lon1, lat2, lon2):
    """Calculate distance between two points in km"""
    R = 6371  # Earth's radius in km
    lat1, lon1, lat2, lon2 = map(math.radians, [lat1, lon1, lat2, lon2])
    dlat = lat2 - lat1
    dlon = lon2 - lon1
    a = math.sin(dlat/2)**2 + math.cos(lat1) * math.cos(lat2) * math.sin(dlon/2)**2
    c = 2 * math.asin(math.sqrt(a))
    return R * c * 1.3  # 1.3 factor for road vs straight-line distance

# All sites with approximate coordinates and distances
# Using Book 5 distances and Book 4 coordinates where available
sites_data = [
    # name, lat, lng, km_from_regina, km_from_saskatoon
    # Regina area
    ("Regina (Shop)", 50.45, -104.62, 0, 257),
    ("Lumsden", 50.66, -104.86, 32, 225),
    ("Regina ReStore", 50.45, -104.59, 8, 257),
    ("Regina Butterfield", 50.47, -104.57, 3, 260),

    # Regina North corridor (toward Saskatoon)
    ("Bulyea", 50.98, -104.87, 71, 186),
    ("Strasbourg", 51.07, -104.95, 84, 173),
    ("Nokomis", 51.50, -105.00, 134, 123),
    ("Jansen", 51.92, -104.72, 198, 90),

    # Regina West
    ("Moose Jaw", 50.39, -105.54, 77, 310),
    ("Swift Current", 50.28, -107.80, 256, 480),

    # Regina East
    ("Yorkton", 51.21, -102.49, 185, 330),

    # Saskatoon area
    ("Saskatoon (Shop)", 52.13, -106.67, 257, 0),
    ("Saskatoon LINN", 52.15, -106.67, 259, 2),
    ("Saskatoon Old TT", 52.14, -106.60, 262, 8),
    ("Casa Rio", 52.03, -106.62, 275, 18),

    # Saskatoon nearby
    ("Neuanlage", 52.45, -106.47, 294, 37),
    ("Waldheim", 52.62, -106.65, 322, 65),
    ("Rosthern", 52.67, -106.32, 312, 55),
    ("Clavet", 51.94, -106.38, 297, 40),
    ("Cardinal Estates", 51.90, -106.50, 301, 44),
    ("Shields", 51.82, -106.41, 323, 66),

    # Saskatoon NE/E
    ("Allan", 51.89, -106.06, 332, 47),
    ("Young", 51.78, -105.76, 356, 99),
    ("Prud'Homme", 52.32, -105.93, 320, 63),
    ("Humboldt", 52.20, -105.18, 348, 116),
    ("Tarnopol", 52.73, -105.38, 361, 120),

    # Saskatoon North
    ("Prince Albert", 53.21, -105.75, 394, 137),
]

# Build site objects
sites = []
for name, lat, lng, km_regina, km_saskatoon in sites_data:
    if "Shop" not in name:  # Exclude the shops themselves
        sites.append(Site(name, lat, lng, km_regina, km_saskatoon))

# Distance matrix (using haversine + road factor, or known distances)
# Known inter-site distances from Book 4 (converted to km)
known_distances_miles = {
    # Regina Local route
    ("Regina (Shop)", "Lumsden"): 20,
    ("Lumsden", "Regina ReStore"): 21,
    ("Regina ReStore", "Regina Butterfield"): 2,

    # Regina N route
    ("Regina (Shop)", "Bulyea"): 44,
    ("Bulyea", "Strasbourg"): 8,
    ("Strasbourg", "Nokomis"): 31,
    ("Nokomis", "Jansen"): 40,
    ("Jansen", "Regina (Shop)"): 112,

    # Regina W route
    ("Regina (Shop)", "Moose Jaw"): 48,
    ("Moose Jaw", "Swift Current"): 111,
    ("Swift Current", "Regina (Shop)"): 153,

    # Regina YQV
    ("Regina (Shop)", "Yorkton"): 115,

    # Saskatoon Local
    ("Saskatoon (Shop)", "Saskatoon LINN"): 1,
    ("Saskatoon LINN", "Saskatoon Old TT"): 5,
    ("Saskatoon Old TT", "Casa Rio"): 11,
    ("Casa Rio", "Saskatoon (Shop)"): 14,

    # Saskatoon NE
    ("Saskatoon (Shop)", "Humboldt"): 70,
    ("Humboldt", "Tarnopol"): 45,
    ("Tarnopol", "Prud'Homme"): 48,
    ("Prud'Homme", "Saskatoon (Shop)"): 40,

    # Saskatoon PA
    ("Saskatoon (Shop)", "Neuanlage"): 23,
    ("Neuanlage", "Rosthern"): 17,
    ("Rosthern", "Prince Albert"): 47,
    ("Prince Albert", "Waldheim"): 63,
    ("Waldheim", "Saskatoon (Shop)"): 34,

    # Saskatoon SE
    ("Saskatoon (Shop)", "Clavet"): 25,
    ("Clavet", "Allan"): 17,
    ("Allan", "Young"): 15,
    ("Young", "Shields"): 31,
    ("Shields", "Cardinal Estates"): 11,
    ("Cardinal Estates", "Saskatoon (Shop)"): 22,
}

# Convert to km and make bidirectional
known_distances_km = {}
for (a, b), miles in known_distances_miles.items():
    km = miles * MILES_TO_KM
    known_distances_km[(a, b)] = km
    known_distances_km[(b, a)] = km

def get_distance(site1_name, site2_name):
    """Get distance between two sites in km"""
    if (site1_name, site2_name) in known_distances_km:
        return known_distances_km[(site1_name, site2_name)]

    # Fall back to haversine calculation
    s1 = next((s for s in sites_data if s[0] == site1_name), None)
    s2 = next((s for s in sites_data if s[0] == site2_name), None)
    if s1 and s2:
        return haversine_km(s1[1], s1[2], s2[1], s2[2])
    return 999999  # Unknown

def calc_day_time(distance_km, num_sites):
    """Calculate total time for a day's work"""
    driving = distance_km / AVG_SPEED_KMH
    service = num_sites * SITE_VISIT_HOURS
    return driving + service

def calc_day_cost(distance_km, total_hours):
    """Calculate cost for a day"""
    regular = min(total_hours, REGULAR_HOURS)
    overtime = max(0, total_hours - REGULAR_HOURS)
    labour = (regular * HOURLY_RATE) + (overtime * HOURLY_RATE * OVERTIME_MULTIPLIER)
    mileage = distance_km * MILEAGE_RATE
    return labour, mileage

print("=" * 80)
print("SASKATCHEWAN HVAC GEOGRAPHIC ROUTE OPTIMIZATION")
print("Complete Re-think from Scratch")
print("=" * 80)
print()
print("Parameters:")
print(f"  Tech hourly rate: ${HOURLY_RATE}")
print(f"  Mileage rate: ${MILEAGE_RATE}/km")
print(f"  Site visit time: {SITE_VISIT_HOURS} hours")
print(f"  Regular day: {REGULAR_HOURS} hours")
print(f"  Max day: {MAX_HOURS} hours")
print(f"  Overnight hotel: ${HOTEL_COST}")
print()

# Analyze site clusters geographically
print("=" * 80)
print("GEOGRAPHIC ANALYSIS - SITE CLUSTERS")
print("=" * 80)
print()

# Group sites by which shop is closer
regina_sites = [s for s in sites if s.km_from_regina <= s.km_from_saskatoon]
saskatoon_sites = [s for s in sites if s.km_from_saskatoon < s.km_from_regina]

print("SITES CLOSER TO REGINA:")
for s in sorted(regina_sites, key=lambda x: x.km_from_regina):
    print(f"  {s.name}: {s.km_from_regina:.0f} km from Regina, {s.km_from_saskatoon:.0f} km from Saskatoon")
print()

print("SITES CLOSER TO SASKATOON:")
for s in sorted(saskatoon_sites, key=lambda x: x.km_from_saskatoon):
    print(f"  {s.name}: {s.km_from_saskatoon:.0f} km from Saskatoon, {s.km_from_regina:.0f} km from Regina")
print()

# Key insight: Jansen is actually closer to Saskatoon!
print("KEY INSIGHT: Site assignment by nearest shop")
print("-" * 50)
for s in sites:
    closer = "Regina" if s.km_from_regina <= s.km_from_saskatoon else "Saskatoon"
    diff = abs(s.km_from_regina - s.km_from_saskatoon)
    note = " ← REASSIGN?" if diff > 50 and closer != ("Regina" if s.km_from_regina < 150 else "Saskatoon") else ""
    print(f"  {s.name}: {closer} is closer by {diff:.0f} km{note}")
print()

# Build optimized routes
print("=" * 80)
print("OPTIMIZED ROUTE PROPOSAL")
print("=" * 80)
print()

# Define optimized multi-day routes
optimized_trips = [
    {
        "name": "Regina Local",
        "base": "Regina",
        "days": [
            {
                "sites": ["Lumsden", "Regina ReStore", "Regina Butterfield"],
                "km": 69,  # Known from Book 4
                "overnight": False
            }
        ]
    },
    {
        "name": "Regina West (2-day trip)",
        "base": "Regina",
        "days": [
            {
                "sites": ["Moose Jaw", "Swift Current"],
                "km": 256,  # Regina -> MJ (77) -> SC (179)
                "overnight": True,  # Stay in Swift Current
                "hotel_location": "Swift Current"
            },
            {
                "sites": [],  # Return day
                "km": 256,  # SC -> Regina
                "overnight": False
            }
        ]
    },
    {
        "name": "Regina North Short",
        "base": "Regina",
        "days": [
            {
                "sites": ["Bulyea", "Strasbourg"],
                "km": 168,  # Regina -> Bulyea (71) -> Strasbourg (13) -> Regina (84)
                "overnight": False
            }
        ]
    },
    {
        "name": "Yorkton",
        "base": "Regina",
        "days": [
            {
                "sites": ["Yorkton"],
                "km": 370,  # Round trip
                "overnight": False
            }
        ]
    },
    {
        "name": "North Corridor (2-day trip from Saskatoon)",
        "base": "Saskatoon",
        "days": [
            {
                "sites": ["Jansen", "Nokomis"],  # Reassigned from Regina!
                "km": 213,  # Saskatoon -> Jansen (90) -> Nokomis (64) -> stay
                "overnight": True,
                "hotel_location": "Nokomis/Watrous area"
            },
            {
                "sites": [],
                "km": 123,  # Nokomis -> Saskatoon
                "overnight": False
            }
        ]
    },
    {
        "name": "Saskatoon Local",
        "base": "Saskatoon",
        "days": [
            {
                "sites": ["Saskatoon LINN", "Saskatoon Old TT", "Casa Rio"],
                "km": 50,
                "overnight": False
            }
        ]
    },
    {
        "name": "Saskatoon South Cluster",
        "base": "Saskatoon",
        "days": [
            {
                "sites": ["Clavet", "Cardinal Estates", "Shields"],
                "km": 132,  # Loop through south sites
                "overnight": False
            }
        ]
    },
    {
        "name": "Saskatoon East",
        "base": "Saskatoon",
        "days": [
            {
                "sites": ["Allan", "Young"],
                "km": 198,  # Saskatoon -> Allan -> Young -> Saskatoon
                "overnight": False
            }
        ]
    },
    {
        "name": "Saskatoon NE (Humboldt corridor)",
        "base": "Saskatoon",
        "days": [
            {
                "sites": ["Prud'Homme", "Humboldt", "Tarnopol"],
                "km": 327,  # Full NE loop
                "overnight": False
            }
        ]
    },
    {
        "name": "Saskatoon North (PA corridor)",
        "base": "Saskatoon",
        "days": [
            {
                "sites": ["Neuanlage", "Waldheim", "Rosthern"],
                "km": 170,
                "overnight": False
            }
        ]
    },
    {
        "name": "Prince Albert",
        "base": "Saskatoon",
        "days": [
            {
                "sites": ["Prince Albert"],
                "km": 274,  # Round trip
                "overnight": False
            }
        ]
    },
]

# Calculate totals
total_labour_cost = 0
total_mileage_cost = 0
total_hotel_cost = 0
total_sites = 0
total_days = 0
total_hours = 0
total_km = 0
total_regular = 0
total_overtime = 0

print("DETAILED TRIP BREAKDOWN:")
print("-" * 80)
print()

for trip in optimized_trips:
    print(f"TRIP: {trip['name']} (from {trip['base']})")
    trip_labour = 0
    trip_mileage = 0
    trip_hotel = 0

    for i, day in enumerate(trip["days"]):
        day_num = i + 1
        sites_today = day["sites"]
        km = day["km"]
        hours = calc_day_time(km, len(sites_today))
        labour, mileage = calc_day_cost(km, hours)

        regular = min(hours, REGULAR_HOURS)
        overtime = max(0, hours - REGULAR_HOURS)

        total_regular += regular
        total_overtime += overtime

        trip_labour += labour
        trip_mileage += mileage

        if day.get("overnight"):
            trip_hotel += HOTEL_COST

        status = "✓" if hours <= MAX_HOURS else "⚠ OVER"
        ot_str = f" (OT: {overtime:.1f}h)" if overtime > 0 else ""

        if sites_today:
            print(f"  Day {day_num}: {', '.join(sites_today)}")
            print(f"         {km:.0f} km | {len(sites_today)} sites | {hours:.1f}h {status}{ot_str}")
            print(f"         Labour: ${labour:.2f} | Mileage: ${mileage:.2f}")
            total_sites += len(sites_today)
        else:
            print(f"  Day {day_num}: Return travel")
            print(f"         {km:.0f} km | {hours:.1f}h")
            print(f"         Labour: ${labour:.2f} | Mileage: ${mileage:.2f}")

        if day.get("overnight"):
            print(f"         → Overnight in {day['hotel_location']} (${HOTEL_COST})")

        total_hours += hours
        total_km += km
        total_days += 1

    trip_total = trip_labour + trip_mileage + trip_hotel
    total_labour_cost += trip_labour
    total_mileage_cost += trip_mileage
    total_hotel_cost += trip_hotel

    print(f"  TRIP TOTAL: ${trip_total:.2f}")
    print()

total_cost = total_labour_cost + total_mileage_cost + total_hotel_cost

print("=" * 80)
print("OPTIMIZED PLAN SUMMARY")
print("=" * 80)
print()
print(f"Total sites serviced: {total_sites}")
print(f"Total days required: {total_days}")
print(f"Total kilometers: {total_km:.0f} km")
print(f"Total hours: {total_hours:.1f}")
print(f"  - Regular hours: {total_regular:.1f}")
print(f"  - Overtime hours: {total_overtime:.1f}")
print()
print("COSTS PER CYCLE:")
print(f"  Labour cost:    ${total_labour_cost:,.2f}")
print(f"  Mileage cost:   ${total_mileage_cost:,.2f}")
print(f"  Hotel cost:     ${total_hotel_cost:,.2f}")
print(f"  TOTAL:          ${total_cost:,.2f}")
print()
print("ANNUAL COSTS (2 cycles):")
print(f"  Labour:         ${total_labour_cost * 2:,.2f}")
print(f"  Mileage:        ${total_mileage_cost * 2:,.2f}")
print(f"  Hotels:         ${total_hotel_cost * 2:,.2f}")
print(f"  TOTAL:          ${total_cost * 2:,.2f}")
print()
print(f"Cost per site visit: ${total_cost / total_sites:,.2f}")
print()

# Comparison with original
print("=" * 80)
print("COMPARISON WITH ORIGINAL BOOK 4 ROUTES")
print("=" * 80)
print()

# Original costs (recalculated with user's rates)
orig_km = 2190
orig_regular = 63.1
orig_overtime = 26.8
orig_labour = (orig_regular * HOURLY_RATE) + (orig_overtime * HOURLY_RATE * OVERTIME_MULTIPLIER)
orig_mileage = orig_km * MILEAGE_RATE
orig_total = orig_labour + orig_mileage

print(f"{'Metric':<25} {'Original':>15} {'Optimized':>15} {'Difference':>15}")
print("-" * 70)
print(f"{'Days':<25} {'8':>15} {total_days:>15} {total_days-8:>+15}")
print(f"{'Kilometers':<25} {orig_km:>15,.0f} {total_km:>15,.0f} {total_km-orig_km:>+15,.0f}")
print(f"{'Regular Hours':<25} {orig_regular:>15.1f} {total_regular:>15.1f} {total_regular-orig_regular:>+15.1f}")
print(f"{'Overtime Hours':<25} {orig_overtime:>15.1f} {total_overtime:>15.1f} {total_overtime-orig_overtime:>+15.1f}")
print(f"{'Labour Cost':<25} ${orig_labour:>14,.2f} ${total_labour_cost:>14,.2f} ${total_labour_cost-orig_labour:>+14,.2f}")
print(f"{'Mileage Cost':<25} ${orig_mileage:>14,.2f} ${total_mileage_cost:>14,.2f} ${total_mileage_cost-orig_mileage:>+14,.2f}")
print(f"{'Hotel Cost':<25} ${'0':>14} ${total_hotel_cost:>14,.2f} ${total_hotel_cost:>+14,.2f}")
print(f"{'TOTAL COST':<25} ${orig_total:>14,.2f} ${total_cost:>14,.2f} ${total_cost-orig_total:>+14,.2f}")
print()

print("=" * 80)
print("KEY OPTIMIZATIONS MADE")
print("=" * 80)
print()
print("1. REASSIGNED JANSEN & NOKOMIS to Saskatoon branch")
print("   - These sites are actually closer to Saskatoon than Regina")
print("   - Jansen: 90km from Saskatoon vs 198km from Regina")
print("   - Saves significant driving on the old 'Regina-N' route")
print()
print("2. CREATED 2-DAY TRIPS where geography makes sense")
print("   - Swift Current: Drive out Day 1, service + return Day 2")
print("   - North Corridor: Service Jansen/Nokomis with overnight")
print("   - Reduces daily hours, avoids impossible 14+ hour days")
print()
print("3. REGROUPED SASKATOON SITES by geography")
print("   - South cluster: Clavet, Cardinal Estates, Shields")
print("   - East: Allan, Young")
print("   - NE corridor: Prud'Homme, Humboldt, Tarnopol")
print("   - North: Neuanlage, Waldheim, Rosthern")
print("   - PA: Solo trip (too far to combine)")
print()
print("4. ALL DAYS NOW UNDER 12 HOURS")
print("   - Original had 3 days over 12h (impossible)")
print("   - Optimized: longest day is ~11.6h (NE route)")
print()