cut_optimizer.py

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Cut Plan Optimizer for 8-ft 2×4s (or any stock length)

OVERVIEW
========
This program computes an *optimal* cutting plan that minimizes the number of
stock boards needed to produce a set of requested piece lengths. It models:

- A per-cut saw kerf between adjacent pieces on a board (internal kerf).
- A *conditional end-trim kerf*: if the used length does **not** perfectly
  equal the stock length, you’ll make one final squaring/trim cut at the end.
  That extra kerf is reserved in fit checks and included in the waste number.

It also prints **mark positions** (in inches from the original left end) for
each cut, assuming you mark to the **left** of the cut and cut **left→right**.
With this convention, the blade removes kerf to the **right** of your pencil
line, producing pieces at the intended lengths.

I/O (Inputs and Outputs)
========================
Inputs (choose one):
  1) Edit the DEFAULT `requirements` mapping in this file:
       {length_in_inches: quantity, ...}
  2) Use CLI flags (repeatable) to pass pieces:
       -p LENGTH QTY  (e.g., -p 33 2 -p 25 2 ...)
     You can specify the unit for LENGTHs via --units inches|feet (default:
     inches). If you pass feet, the program converts to inches internally.
  3) Adjust optional parameters via CLI:
       --stock 96          (stock length in inches; default 96 for 8 ft)
       --stock-ft 8        (stock length in feet; overrides --stock)
       --kerf 0.125        (internal kerf per cut in inches)
       --end-trim 0.125    (end-trim kerf; default: same as --kerf)
       --no-marks          (suppress mark position prints)

Outputs (to stdout):
  - Minimal number of boards required.
  - For each board:
      * Piece breakdown
      * Mark positions (left-of-blade, left→right)
      * Optional “final end-trim mark” (if not an exact fill)
      * Kerf totals, used length, and waste per board
  - Total waste across all boards.

NOTES & ASSUMPTIONS
===================
- Kerf direction convention: marks are to the **left** of each cut; saw removes
  kerf on the **right** of the line. If you flip this practice, adjust the
  marking logic accordingly.
- Floating-point tolerances are used to treat “exact” fills robustly.
- The search uses an exact branch-and-bound with memoization and symmetry
  breaking. For typical small/medium cut lists (like framing) it’s fast and
  exact without external libraries.

USAGE EXAMPLES
==============
1) Use defaults embedded in the file:
     python cut_optimizer.py

2) Same requirements as the prompt via CLI:
     python cut_optimizer.py \
       -p 33 2 -p 25 2 -p 13.8 2 -p 10.25 2 -p 20 4 -p 36.25 4 \
       --stock 96 --kerf 0.125

3) Specify lengths in feet and an 8-ft stock:
     python cut_optimizer.py -p 2.75 2 -p 2.0833 2 --units feet --stock-ft 8

"""

from __future__ import annotations

import argparse
from collections import Counter
from functools import lru_cache
from typing import Dict, Iterable, List, Tuple

# ---------------------------- Defaults (editable) -----------------------------

# Default stock and kerfs (can be overridden by CLI)
DEFAULT_STOCK_LENGTH_IN = 96.0      # inches (8 ft)
DEFAULT_KERF_IN = 0.125             # inches per internal cut
DEFAULT_END_TRIM_IN = None          # None → use kerf; else set a number in inches

# Default requirements (can be overridden by CLI -p flags)
# Example from the prompt:
requirements: Dict[float, int] = {
    33.0: 2,
    25.0: 2,
    13.8: 2,
    10.25: 2,
    20.0: 4,
    36.25: 4,
}

# ------------------------------- Constants -----------------------------------

TOL = 1e-9  # numeric tolerance for “exact” comparisons


# ----------------------------- Helper Functions ------------------------------

def multiset_to_list(req: Dict[float, int]) -> List[float]:
    """
    Expand a {length: qty} mapping into a flat list of piece lengths.

    Parameters
    ----------
    req : Dict[float, int]
        Mapping from piece length (inches) to quantity.

    Returns
    -------
    List[float]
        Flat list of piece lengths (inches), with each length repeated by qty.
    """
    pieces: List[float] = []
    for length, qty in req.items():
        pieces.extend([float(length)] * int(qty))
    return pieces


def internal_used_no_end(board_pieces: Tuple[float, ...], kerf: float) -> float:
    """
    Compute total used length from pieces and internal kerfs only (no end trim).

    For N pieces on a board, there are max(0, N-1) internal kerfs.

    Parameters
    ----------
    board_pieces : Tuple[float, ...]
        Piece lengths (inches) assigned to a board.
    kerf : float
        Internal kerf per cut (inches).

    Returns
    -------
    float
        Sum of piece lengths plus internal kerfs.
    """
    if not board_pieces:
        return 0.0
    return sum(board_pieces) + (len(board_pieces) - 1) * kerf


def board_is_exact(board_pieces: Tuple[float, ...], stock: float, kerf: float) -> bool:
    """
    Determine if a board is an exact fill, i.e., no end trim is needed.

    Parameters
    ----------
    board_pieces : Tuple[float, ...]
        Piece lengths (inches) assigned to a board.
    stock : float
        Stock length (inches).
    kerf : float
        Internal kerf per cut (inches).

    Returns
    -------
    bool
        True if internal_used_no_end == stock within tolerance.
    """
    return abs(stock - internal_used_no_end(board_pieces, kerf)) <= 1e-6


def board_used_length(
    board_pieces: Tuple[float, ...], stock: float, kerf: float, end_trim: float
) -> float:
    """
    Compute total consumed stock including conditional end-trim kerf.

    If the internal sum is “exact,” no end-trim is added. Otherwise, add end_trim.

    Parameters
    ----------
    board_pieces : Tuple[float, ...]
        Pieces on the board (inches).
    stock : float
        Stock length (inches).
    kerf : float
        Internal kerf (inches).
    end_trim : float
        End-trim kerf (inches) reserved if not exact.

    Returns
    -------
    float
        Total used length accounting for conditional end-trim.
    """
    base = internal_used_no_end(board_pieces, kerf)
    return base if board_is_exact(board_pieces, stock, kerf) else base + end_trim


def waste_for_board(
    board_pieces: Tuple[float, ...], stock: float, kerf: float, end_trim: float
) -> float:
    """
    Compute tail waste after applying conditional end-trim kerf when not exact.

    Parameters
    ----------
    board_pieces : Tuple[float, ...]
        Pieces on the board (inches).
    stock : float
        Stock length (inches).
    kerf : float
        Internal kerf (inches).
    end_trim : float
        End-trim kerf (inches).

    Returns
    -------
    float
        Non-negative waste length (inches).
    """
    return max(0.0, stock - board_used_length(board_pieces, stock, kerf, end_trim))


def can_add_to_board(
    board_pieces: Tuple[float, ...],
    new_len: float,
    stock: float,
    kerf: float,
    end_trim: float,
) -> bool:
    """
    Check if adding a piece fits the stock, honoring the conditional end-trim rule.

    Adding a piece is allowed if:
      (A) It yields an exact fill (no end-trim needed), OR
      (B) It still fits after reserving one end-trim kerf (non-exact fill).

    Parameters
    ----------
    board_pieces : Tuple[float, ...]
        Current pieces on the board (inches).
    new_len : float
        Candidate piece length (inches) to add.
    stock : float
        Stock length (inches).
    kerf : float
        Internal kerf per cut (inches).
    end_trim : float
        End-trim kerf (inches) reserved if non-exact.

    Returns
    -------
    bool
        True if the piece can be added under the rules above.
    """
    base_before = internal_used_no_end(board_pieces, kerf)
    added_internal = kerf if len(board_pieces) >= 1 else 0.0
    base_after = base_before + added_internal + new_len  # still “no end trim” sum

    # Case A: exact (no end-trim needed)
    if abs(stock - base_after) <= 1e-6:
        return True

    # Case B: non-exact; must also fit with one end-trim kerf
    return (base_after + end_trim) <= stock + TOL


def normalize_bins(bins: Tuple[Tuple[float, ...], ...]) -> Tuple[Tuple[float, ...], ...]:
    """
    Canonicalize bin representation to reduce symmetry in the search.

    Sort pieces within each bin in descending order, then sort bins.

    Parameters
    ----------
    bins : Tuple[Tuple[float, ...], ...]
        Current boards with their pieces.

    Returns
    -------
    Tuple[Tuple[float, ...], ...]
        Canonicalized bin tuple for memoization.
    """
    norm = tuple(tuple(sorted(b, reverse=True)) for b in bins)
    return tuple(sorted(norm, reverse=True))


def solve_cutting(
    pieces: List[float],
    stock: float,
    kerf: float,
    end_trim: float,
) -> Tuple[Tuple[Tuple[float, ...], ...], int]:
    """
    Solve the cutting-stock layout with exact branch-and-bound search.

    Parameters
    ----------
    pieces : List[float]
        Piece lengths (inches) to realize.
    stock : float
        Stock length (inches).
    kerf : float
        Internal kerf per cut (inches).
    end_trim : float
        End-trim kerf (inches) to reserve if non-exact.

    Returns
    -------
    (best_bins, explored) : Tuple[Tuple[Tuple[float, ...], ...], int]
        best_bins is a tuple of boards; each board is a tuple of piece lengths.
        explored is a diagnostic count of explored search nodes.
    """
    pieces = tuple(sorted(pieces, reverse=True))  # longest-first for tighter bounds
    best_solution = {"bins": None}
    explored = 0

    total_len = sum(pieces)
    optimistic_lb = int((total_len // stock) + (1 if (total_len % stock) > TOL else 0))

    @lru_cache(maxsize=None)
    def dfs(remaining: Tuple[float, ...], bins: Tuple[Tuple[float, ...], ...]) -> None:
        nonlocal explored, best_solution
        explored += 1

        # Done: no pieces left
        if not remaining:
            if best_solution["bins"] is None or len(bins) < len(best_solution["bins"]):
                best_solution["bins"] = bins
            return

        # Prune when already as bad as best known
        if best_solution["bins"] is not None and len(bins) >= len(best_solution["bins"]):
            return

        # Lower bound on remaining boards ignoring kerf/end-trim fine details
        rem_total = sum(remaining)
        min_extra = int(rem_total // stock) + (1 if (rem_total % stock) > TOL else 0)
        if best_solution["bins"] is not None and (len(bins) + min_extra) >= len(best_solution["bins"]):
            return

        next_len = remaining[0]
        rest = remaining[1:]

        # Try placing into existing boards, dedup by capacity signature
        seen_signatures = set()
        for i, b in enumerate(bins):
            if not can_add_to_board(b, next_len, stock, kerf, end_trim):
                continue

            new_b = tuple(sorted(b + (next_len,), reverse=True))
            used = board_used_length(new_b, stock, kerf, end_trim)
            cap_after = stock - used
            sig = (round(cap_after, 3), len(new_b))
            if sig in seen_signatures:
                continue
            seen_signatures.add(sig)

            new_bins = list(bins)
            new_bins[i] = new_b
            dfs(rest, normalize_bins(tuple(new_bins)))

            # Optional early-exit: if we hit theoretical best for this prefix
            if (best_solution["bins"] is not None
                and len(best_solution["bins"]) == max(optimistic_lb, len(bins))):
                return

        # Or open a new board
        new_bins = normalize_bins(bins + ((next_len,),))
        dfs(rest, new_bins)

    dfs(pieces, tuple())
    assert best_solution["bins"] is not None  # with valid inputs, a solution must exist
    return best_solution["bins"], explored


def compute_mark_positions(board_pieces: Tuple[float, ...], kerf: float) -> List[float]:
    """
    Compute absolute mark positions from the left end for each piece cut.

    Convention: mark to the LEFT of the blade; cut LEFT→RIGHT. The blade removes
    kerf to the RIGHT of the pencil line. The j-th mark is:

        mark_j = sum(first j piece lengths) + (j-1) * kerf

    Parameters
    ----------
    board_pieces : Tuple[float, ...]
        Piece sequence (inches) on the board.
    kerf : float
        Internal kerf per cut (inches).

    Returns
    -------
    List[float]
        Mark positions in inches from the original left end.
    """
    marks: List[float] = []
    acc = 0.0
    for i, L in enumerate(board_pieces, start=1):
        acc += L
        mark = acc + (i - 1) * kerf
        marks.append(mark)
    return marks


def pretty_print_solution(
    bins: Tuple[Tuple[float, ...], ...],
    stock: float,
    kerf: float,
    end_trim: float,
    show_marks: bool = True,
) -> None:
    """
    Render the plan to stdout, including marks, kerfs, used length, and waste.

    Parameters
    ----------
    bins : Tuple[Tuple[float, ...], ...]
        Boards and their assigned pieces.
    stock : float
        Stock length (inches).
    kerf : float
        Internal kerf (inches).
    end_trim : float
        End-trim kerf (inches).
    show_marks : bool, default True
        Whether to print mark positions and the final end-trim mark (if any).
    """
    print(f"\nOptimal boards needed: {len(bins)}")
    print("Assumptions: mark LEFT of blade; cut LEFT→RIGHT; blade removes kerf to the RIGHT of the mark.")
    grand_waste = 0.0

    for idx, b in enumerate(bins, start=1):
        base = internal_used_no_end(b, kerf)
        exact = board_is_exact(b, stock, kerf)
        end_trim_applied = 0.0 if exact else end_trim
        used = base + end_trim_applied
        waste = max(0.0, stock - used)
        grand_waste += waste

        cut_str = " + ".join(f"{x:.3f}\"" for x in b)
        cuts_internal = max(0, len(b) - 1)

        print(f"\nBoard {idx}:")
        print(f"  Pieces: {cut_str}")
        if show_marks:
            marks = compute_mark_positions(b, kerf)
            print(f"  Mark positions (from left): " + ", ".join(f"{m:.3f}\"" for m in marks))
            if not exact:
                end_mark = base  # location of the final end-trim mark (before removing kerf)
                print(f"  Final end-trim mark: {end_mark:.3f}\" (then remove {end_trim:.3f}\" to the right)")
        print(f"  Internal cuts: {cuts_internal} @ {kerf:.3f}\" = {cuts_internal*kerf:.3f}\" kerf")
        print(f"  End trim kerf: {end_trim_applied:.3f}\" ({'none, exact fill' if exact else 'applied'})")
        print(f"  Used: {used:.3f}\" / {stock:.3f}\"")
        print(f"  Waste: {waste:.3f}\"")

    print(f"\nTotal waste: {grand_waste:.3f}\"")


# ---------------------------------- CLI --------------------------------------

def parse_args() -> argparse.Namespace:
    """
    Parse command-line arguments for interactive use.

    Returns
    -------
    argparse.Namespace
        Parsed arguments with attributes:
          - piece: list[[LENGTH, QTY]] or None
          - units: 'inches' or 'feet'
          - stock, stock_ft: optional floats
          - kerf: float
          - end_trim: Optional[float]
          - no_marks: bool
    """
    p = argparse.ArgumentParser(
        description="Optimize 2×4 cut plan with kerf and conditional end trim; print mark positions.",
        formatter_class=argparse.ArgumentDefaultsHelpFormatter,
    )
    p.add_argument(
        "-p", "--piece", nargs=2, action="append", metavar=("LENGTH", "QTY"),
        help="Add a piece requirement (repeatable). LENGTH in --units; QTY integer."
    )
    p.add_argument(
        "--units", choices=("inches", "feet"), default="inches",
        help="Unit for LENGTH inputs (pieces only)."
    )
    p.add_argument(
        "--stock", type=float, default=None,
        help="Stock length in inches. Ignored if --stock-ft is given."
    )
    p.add_argument(
        "--stock-ft", type=float, default=None,
        help="Stock length in feet; overrides --stock if provided."
    )
    p.add_argument(
        "--kerf", type=float, default=DEFAULT_KERF_IN,
        help="Internal kerf per cut (inches)."
    )
    p.add_argument(
        "--end-trim", type=float, default=None,
        help="End-trim kerf (inches). If omitted, equals --kerf."
    )
    p.add_argument(
        "--no-marks", action="store_true",
        help="Do not print mark positions."
    )
    return p.parse_args()


def build_requirements_from_args(args: argparse.Namespace) -> Dict[float, int]:
    """
    Build a {length_in_inches: qty} mapping from CLI args or defaults.

    Parameters
    ----------
    args : argparse.Namespace
        Parsed CLI args.

    Returns
    -------
    Dict[float, int]
        Requirements mapping in inches.
    """
    if not args.piece:
        return dict(requirements)  # use defaults

    factor = 12.0 if args.units == "feet" else 1.0
    req: Dict[float, int] = {}
    for L, Q in args.piece:
        length_in = float(L) * factor
        qty = int(Q)
        req[length_in] = req.get(length_in, 0) + qty
    return req


def main() -> None:
    """
    CLI entry point. Parses args, solves the layout, and prints the cut plan.

    Steps
    -----
    1) Parse CLI args (or fall back to defaults in this file).
    2) Construct the piece multiset.
    3) Run the exact solver with kerf + conditional end-trim.
    4) Pretty-print the plan, including mark positions (unless suppressed).
    """
    args = parse_args()

    # Resolve stock length
    if args.stock_ft is not None:
        stock = float(args.stock_ft) * 12.0
    elif args.stock is not None:
        stock = float(args.stock)
    else:
        stock = DEFAULT_STOCK_LENGTH_IN

    kerf = float(args.kerf)
    end_trim = kerf if args.end_trim is None else float(args.end_trim)

    req_map = build_requirements_from_args(args)
    pieces = multiset_to_list(req_map)

    print("Input pieces (length in inches):")
    ctr = Counter(pieces)
    for L in sorted(ctr.keys(), reverse=True):
        print(f"  {L}\" x {ctr[L]}")

    print(f"\nStock length per board: {stock}\"")
    print(f"Internal kerf per cut: {kerf}\"")
    print(f"End-trim kerf (conditional): {end_trim}\"")

    bins, explored = solve_cutting(pieces, stock, kerf, end_trim)
    pretty_print_solution(bins, stock, kerf, end_trim, show_marks=not args.no_marks)
    print(f"\nSearch nodes explored: {explored}")


if __name__ == "__main__":
    main()