fork(1) download
copy 
  1. import numpy as np
  2.  
  3. def calculate_time(x_values):
  4.     """Calculates the total travel time given the entry points."""
  5.     speeds = [9, 8, 7, 6, 5, 10]
  6.     marsh_width = 10 * np.sqrt(2)  # Width of each region in the East-West direction
  7.  
  8.     # Ensure x_values has at least 6 elements
  9.     if len(x_values) < 6:
  10.         raise ValueError("x_values should have at least 6 elements.")
  11.  
  12.     x = [0.0] + x_values  # Include initial x0=0
  13.     total_time = 0.0
  14.  
  15.     for i in range(len(speeds)):
  16.         # Horizontal distance in this region
  17.         dx = marsh_width if i < 5 else (50 + x[5]) - (5 * marsh_width)
  18.  
  19.         # Vertical distance in this segment
  20.         if i+1 < len(x):  
  21.             dy = abs(x[i+1] - x[i])
  22.         else:
  23.             dy = 0  # Prevent out-of-range errors
  24.  
  25.         # Total distance in this segment
  26.         distance = np.sqrt(dx**2 + dy**2)
  27.  
  28.         # Time taken for this segment
  29.         total_time += distance / speeds[i]
  30.  
  31.     return total_time * 2 - calculate_time_last_segment(x_values)
  32.  
  33. def calculate_time_last_segment(x_values):
  34.     """Calculates time for the last segment separately."""
  35.     speeds = [10]
  36.  
  37.     # Ensure x_values has at least 6 elements
  38.     if len(x_values) < 6:
  39.         raise ValueError("x_values should have at least 6 elements.")
  40.  
  41.     x = [0.0] + x_values  # Include initial x0=0
  42.     total_time = 0.0
  43.     i = 5
  44.  
  45.     # Horizontal distance in this region
  46.     dx = (50 + x[5]) - (5 * 10 * np.sqrt(2))
  47.  
  48.     # Vertical distance in this segment
  49.     if i+1 < len(x):
  50.         dy = abs(x[i+1] - x[i])
  51.     else:
  52.         dy = 0  # Prevent out-of-range errors
  53.  
  54.     # Total distance in this segment
  55.     distance = np.sqrt(dx**2 + dy**2)
  56.  
  57.     total_time += distance / speeds[0]  # Use first element instead of `speeds[i]`
  58.  
  59.     return total_time
  60.  
  61. def numerical_gradient(func, x_values, h=1e-6):
  62.     """Calculates the numerical gradient of a function."""
  63.     gradient = []
  64.  
  65.     for i in range(len(x_values)):
  66.         x_plus_h = x_values.copy()
  67.         x_minus_h = x_values.copy()
  68.  
  69.         x_plus_h[i] += h
  70.         x_minus_h[i] -= h
  71.  
  72.         partial_derivative = (func(x_plus_h) - func(x_minus_h)) / (2 * h)
  73.         gradient.append(partial_derivative)
  74.  
  75.     return np.array(gradient)
  76.  
  77. def gradient_descent(initial_x, learning_rate, num_iterations, h=1e-5):
  78.     """Performs gradient descent."""
  79.     x_values = np.array(initial_x)  # Convert list to numpy array
  80.  
  81.     for i in range(num_iterations):
  82.         grad = numerical_gradient(calculate_time, x_values, h)
  83.         x_values = x_values - learning_rate * grad
  84.         x_values = np.maximum(0, x_values)  # Constraint: x_values must be non-negative
  85.  
  86.         # Learning rate annealing with lower bound
  87.         learning_rate = max(learning_rate * 0.999, 1e-4)  
  88.  
  89.         if i % 100 == 0:
  90.             time = calculate_time(x_values)
  91.             print(f"Iteration {i}: Time = {time:.10f}")
  92.  
  93.     return x_values
  94.  
  95. # Initial guess (straight line path)
  96. initial_x = [5 * np.sqrt(2) * i for i in range(1, 6)]
  97. initial_x.append(0.0)
  98.  
  99. # Gradient Descent parameters
  100. learning_rate = 0.1  # Tunable parameter
  101. num_iterations = 2000
  102.  
  103. final_x = gradient_descent(initial_x, learning_rate, num_iterations)
  104. final_time = calculate_time(final_x)
  105.  
  106. print(f"Final x values: {final_x}")
  107. print(f"Shortest time: {final_time:.10f} days")
Success #stdin #stdout 2.79s 41564KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Iteration 0: Time = 34.5067546639
Iteration 100: Time = 30.2764161408
Iteration 200: Time = 27.2818799139
Iteration 300: Time = 25.1802849406
Iteration 400: Time = 23.7766294118
Iteration 500: Time = 22.8890723883
Iteration 600: Time = 22.3395973900
Iteration 700: Time = 21.9926246408
Iteration 800: Time = 21.7639813752
Iteration 900: Time = 21.6060889909
Iteration 1000: Time = 21.4923821663
Iteration 1100: Time = 21.4270898340
Iteration 1200: Time = 21.4018450737
Iteration 1300: Time = 21.3813138238
Iteration 1400: Time = 21.3643701494
Iteration 1500: Time = 21.3501078005
Iteration 1600: Time = 21.3380957061
Iteration 1700: Time = 21.3278536212
Iteration 1800: Time = 21.3189535778
Iteration 1900: Time = 21.3112137183
Final x values: [13.09016291 16.08770809 19.63687244 21.38094278 21.28676165 20.70972173]
Shortest time: 21.3047166519 days
https://ideone.com/qAtchN
language:
Python 3 (python  3.12)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!