"""Original bounded one-dimensional stock cutting planner. MIT licensed."""
import hashlib
import json
from collections import Counter


def canonical(obj):
    return json.dumps(obj, sort_keys=True, separators=(",", ":"), ensure_ascii=False)


def integer(value, name, low, high):
    if type(value) is not int or not low <= value <= high:
        raise ValueError(f"{name} must be an integer in [{low}, {high}]")
    return value


def plan(data):
    if not isinstance(data, dict) or set(data) - {"stock_mm", "kerf_mm", "end_trim_mm", "pieces"}:
        raise ValueError("Expected stock_mm, kerf_mm, optional end_trim_mm and pieces only")
    stock = integer(data.get("stock_mm"), "stock_mm", 1, 100000)
    kerf = integer(data.get("kerf_mm"), "kerf_mm", 0, 100)
    trim = integer(data.get("end_trim_mm", 0), "end_trim_mm", 0, 1000)
    capacity = stock - 2 * trim
    if capacity <= 0:
        raise ValueError("End trims consume the stock")
    rows = data.get("pieces")
    if not isinstance(rows, list) or not 1 <= len(rows) <= 100:
        raise ValueError("pieces must contain 1..100 length/quantity rows")
    pieces = []
    for row in rows:
        if not isinstance(row, dict) or set(row) != {"length_mm", "quantity"}:
            raise ValueError("Each pieces row requires exactly length_mm and quantity")
        length = integer(row["length_mm"], "length_mm", 1, 100000)
        quantity = integer(row["quantity"], "quantity", 1, 200)
        if length + kerf > capacity:
            raise ValueError(f"Piece {length} plus kerf does not fit usable stock {capacity}")
        pieces.extend([length] * quantity)
    if len(pieces) > 200:
        raise ValueError("Maximum 200 expanded pieces")
    pieces.sort(reverse=True)
    bars = []
    for length in pieces:
        weight = length + kerf
        eligible = [i for i, b in enumerate(bars) if b["remaining_mm"] >= weight]
        if eligible:
            index = min(eligible, key=lambda i: (bars[i]["remaining_mm"] - weight, i))
        else:
            index = len(bars)
            bars.append({"bar": index + 1, "cuts_mm": [], "remaining_mm": capacity})
        bars[index]["cuts_mm"].append(length)
        bars[index]["remaining_mm"] -= weight
    total_pieces = len(pieces)
    finished = sum(pieces)
    saw_loss = kerf * total_pieces
    minimum = (finished + saw_loss + capacity - 1) // capacity
    counts = Counter(length for b in bars for length in b["cuts_mm"])
    assert counts == Counter(pieces)
    assert all(sum(b["cuts_mm"]) + len(b["cuts_mm"]) * kerf + b["remaining_mm"] == capacity for b in bars)
    return {
        "engine": "kerfledger-1.0.0", "algorithm": "deterministic_best_fit_decreasing",
        "optimality": "proven_bar_count_by_volume_bound" if len(bars) == minimum else "heuristic_not_proven_optimal",
        "input_sha256": hashlib.sha256(canonical(data).encode()).hexdigest(),
        "stock_mm": stock, "usable_per_bar_mm": capacity, "kerf_per_piece_mm": kerf,
        "trim_per_end_mm": trim, "bars_required": len(bars), "volume_lower_bound_bars": minimum,
        "pieces_delivered": total_pieces, "finished_length_mm": finished,
        "saw_loss_mm": saw_loss, "total_end_trim_mm": 2 * trim * len(bars),
        "total_remainder_mm": sum(b["remaining_mm"] for b in bars),
        "stock_purchased_mm": len(bars) * stock, "bars": bars,
        "balance_verified": finished + saw_loss + 2 * trim * len(bars) + sum(b["remaining_mm"] for b in bars) == len(bars) * stock,
        "warning": "Planning aid, not machine instructions. Conservative one kerf per piece, including last piece. No angle cuts, material mixing, structural or safety certification."
    }


EXAMPLE = {"stock_mm": 6000, "kerf_mm": 3, "end_trim_mm": 10,
           "pieces": [{"length_mm": 2400, "quantity": 3}, {"length_mm": 1500, "quantity": 4}, {"length_mm": 900, "quantity": 2}]}