#!/usr/bin/env python3
"""Auto-generated by AGI Loop cycle #1138
Task: ,</think>

Write a Python function that calculates the optimal truck route based on real-time traffic data and delivery deadlines, returning the shortest time path with a deviation of no more than 15%
Generated: 2026-02-12T21:37:57.533393
"""

import heapq
import json
import random
from datetime import datetime, timedelta

# Simulated real-time traffic data (edges with current travel time)
traffic_data = {
    "A": {"B": 10, "C": 15},
    "B": {"A": 10, "C": 5, "D": 12},
    "C": {"A": 15, "B": 5, "D": 8},
    "D": {"B": 12, "C": 8, "E": 10},
    "E": {"D": 10}
}

# Simulated delivery deadlines (in minutes from start)
delivery_deadlines = {
    "A": 0,
    "B": 30,
    "C": 45,
    "D": 60,
    "E": 75
}

def calculate_optimal_route(graph, start, end, deadlines):
    """
    Calculate the optimal truck route based on real-time traffic data and delivery deadlines.
    Returns the shortest time path with a deviation of no more than 15% from the theoretical minimum.
    """
    # Step 1: Dijkstra's algorithm to find theoretical minimum time
    def dijkstra(graph, start, end):
        distances = {node: float('inf') for node in graph}
        distances[start] = 0
        pq = [(0, start)]
        visited = set()
        prev = {}

        while pq:
            curr_dist, curr_node = heapq.heappop(pq)
            if curr_node in visited:
                continue
            visited.add(curr_node)
            if curr_node == end:
                break
            for neighbor, weight in graph[curr_node].items():
                distance = curr_dist + weight
                if distance < distances[neighbor]:
                    distances[neighbor] = distance
                    prev[neighbor] = curr_node
                    heapq.heappush(pq, (distance, neighbor))
        # Reconstruct path
        path = []
        node = end
        while node in prev:
            path.append(node)
            node = prev[node]
        path.append(start)
        path.reverse()
        return distances[end], path

    theoretical_min_time, theoretical_path = dijkstra(graph, start, end)

    # Step 2: Simulated real-time path with deviation
    def get_real_time_path(graph, start, end, theoretical_time, deviation_percent=0.15):
        real_time_graph = graph.copy()
        for u in real_time_graph:
            for v in real_time_graph[u]:
                # Add some random variation to simulate real-time traffic
                variation = random.uniform(-deviation_percent, deviation_percent)
                real_time_graph[u][v] = graph[u][v] * (1 + variation)
        # Use Dijkstra again on real-time graph
        distances = {node: float('inf') for node in real_time_graph}
        distances[start] = 0
        pq = [(0, start)]
        visited = set()
        prev = {}

        while pq:
            curr_dist, curr_node = heapq.heappop(pq)
            if curr_node in visited:
                continue
            visited.add(curr_node)
            if curr_node == end:
                break
            for neighbor, weight in real_time_graph[curr_node].items():
                distance = curr_dist + weight
                if distance < distances[neighbor]:
                    distances[neighbor] = distance
                    prev[neighbor] = curr_node
                    heapq.heappush(pq, (distance, neighbor))
        # Reconstruct path
        path = []
        node = end
        while node in prev:
            path.append(node)
            node = prev[node]
        path.append(start)
        path.reverse()
        return distances[end], path

    real_time_path_time, real_time_path = get_real_time_path(graph, start, end, theoretical_min_time)

    # Step 3: Check if real-time path meets delivery deadlines
    def meets_deadlines(path, deadlines):
        current_time = 0
        for i in range(1, len(path)):
            current_time += graph[path[i-1]][path[i]]
            if current_time > deadlines[path[i]]:
                return False
        return True

    if meets_deadlines(real_time_path, deadlines):
        return real_time_path
    else:
        # If not met, find a slightly longer path with 15% deviation
        # Use modified Dijkstra with deadline constraints
        def dijkstra_with_deadlines(graph, start, end, deadlines):
            distances = {node: float('inf') for node in graph}
            distances[start] = 0
            pq = [(0, start)]
            visited = set()
            prev = {}

            while pq:
                curr_dist, curr_node = heapq.heappop(pq)
                if curr_node in visited:
                    continue
                visited.add(curr_node)
                if curr_node == end:
                    break
                for neighbor, weight in graph[curr_node].items():
                    time_to_neighbor = curr_dist + weight
                    if time_to_neighbor <= deadlines[neighbor]:
                        if time_to_neighbor < distances[neighbor]:
                            distances[neighbor] = time_to_neighbor
                            prev[neighbor] = curr_node
                            heapq.heappush(pq, (time_to_neighbor, neighbor))
            # Reconstruct path
            path = []
            node = end
            while node in prev:
                path.append(node)
                node = prev[node]
            path.append(start)
            path.reverse()
            return distances[end], path

        adjusted_path_time, adjusted_path = dijkstra_with_deadlines(graph, start, end, deadlines)
        return adjusted_path

def main():
    start = "A"
    end = "E"
    optimal_path = calculate_optimal_route(traffic_data, start, end, delivery_deadlines)
    print(f"Optimal Route: {optimal_path}")

if __name__ == "__main__":
    main()