Find Captain Redbeard's Hidden Treasure

#127 · Calculus · Medium

Problem

Captain Redbeard buried treasure at the minimum point of a cost function. Given a polynomial cost function, use calculus (gradient descent or analytical derivative) to find the x-coordinate that minimizes the function.

Solution

import numpy as np

def find_treasure(coefficients: list[float], learning_rate: float = 0.01, max_iter: int = 10000, tol: float = 1e-8) -> float:
    # coefficients: [a_n, a_{n-1}, ..., a_1, a_0] for a_n*x^n + ...
    # Compute derivative coefficients
    degree = len(coefficients) - 1
    deriv_coeffs = []
    for i, c in enumerate(coefficients[:-1]):
        power = degree - i
        deriv_coeffs.append(c * power)

    def eval_poly(coeffs, x):
        result = 0.0
        for c in coeffs:
            result = result * x + c
        return result

    # Gradient descent
    x = 0.0
    for _ in range(max_iter):
        grad = eval_poly(deriv_coeffs, x)
        x_new = x - learning_rate * grad
        if abs(x_new - x) < tol:
            break
        x = x_new

    return round(x, 4)

Explanation

Given a polynomial in standard form, compute its derivative analytically by multiplying each coefficient by its power and reducing the degree by one.
Use Horner's method (eval_poly) to efficiently evaluate the derivative at any point x.
Apply gradient descent: repeatedly move x in the direction opposite to the gradient.
Converge when the step size drops below a tolerance.

Complexity

Time: O(I * D) where I = iterations, D = polynomial degree
Space: O(D) for storing derivative coefficients

← #126 #128 →