Thanksgiving Feast Predictor: Softmax for Dish Selection

Problem

Implement the softmax function to predict dish selection probabilities for a Thanksgiving feast. Given a list of raw scores (logits) for each dish, apply the softmax function to convert them into a probability distribution that sums to 1.

Solution

import math

def softmax(logits: list[float]) -> list[float]:
    max_logit = max(logits)
    exps = [math.exp(x - max_logit) for x in logits]
    total = sum(exps)
    return [e / total for e in exps]

Explanation

1. Subtract the maximum logit from each value for numerical stability (prevents overflow).
2. Compute the exponential of each shifted logit.
3. Divide each exponential by the sum of all exponentials to get probabilities.
4. The output is a valid probability distribution: all values are in [0, 1] and they sum to 1.

Complexity

• Time: O(n) where n is the number of logits
• Space: O(n) for the output probabilities