import numpy as np


def fit_linear_normal_eq(X, y, ridge_lambda=0.0):
    X_bias = np.hstack([X, np.ones((X.shape[0], 1))])
    d = X_bias.shape[1]
    reg = ridge_lambda * np.eye(d)
    reg[-1, -1] = 0.0  # don't regularize the bias term
    w = np.linalg.solve(X_bias.T @ X_bias + reg, X_bias.T @ y)
    return w  # last entry is the bias


def predict_linear(X, w):
    X_bias = np.hstack([X, np.ones((X.shape[0], 1))])
    return X_bias @ w


def sigmoid(z):
    return 1.0 / (1.0 + np.exp(-z))


def fit_logistic_gd(X, y, lr=0.1, epochs=1000, ridge_lambda=0.0):
    n, d = X.shape
    X_bias = np.hstack([X, np.ones((n, 1))])
    w = np.zeros(d + 1)
    for _ in range(epochs):
        y_hat = sigmoid(X_bias @ w)
        grad = X_bias.T @ (y_hat - y) / n
        grad[:-1] += ridge_lambda * w[:-1] / n  # skip bias
        w -= lr * grad
    return w


def predict_logistic(X, w, threshold=0.5):
    X_bias = np.hstack([X, np.ones((X.shape[0], 1))])
    probs = sigmoid(X_bias @ w)
    return (probs >= threshold).astype(int), probs
