construction.timber-length

export function timberCuttingList(cuts: readonly number[], stockLength: number, kerf: number): CuttingList

/** One stock length and the pieces cut from it. */
export interface CutBar {
  /** piece lengths in the order they are placed, longest first */
  readonly cuts: readonly number[];
  /** usable length left after the last cut, in millimetres; 0 when less than a kerf remains */
  readonly offcut: number;
}

/** The bars to buy and what to cut from each. */
export interface CuttingList {
  readonly bars: readonly CutBar[];
  /** how many stock lengths to buy */
  readonly barCount: number;
  /** millimetres bought but not in any piece: offcuts plus everything the saw removed */
  readonly waste: number;
}

import { timberCuttingList } from "#fune/construction.timber-length@^1";

import { type CutBar, type CuttingList } from "./construction_timber_length_types.ts";

/**
 * Plan which pieces to cut from which stock length, first-fit decreasing.
 *
 * A bar holds pieces p1..pn when their lengths plus a kerf between each pair
 * fit: sum + kerf * (n - 1) <= stockLength. The last piece may end exactly at
 * the end of the bar, which needs no final cut. Ignoring kerf is the usual
 * mistake: three 1200 mm pieces do not come out of one 3600 mm length.
 */
export function timberCuttingList(cuts: readonly number[], stockLength: number, kerf: number): CuttingList {
  if (!Number.isInteger(stockLength) || stockLength <= 0) {
    throw new RangeError(`stockLength must be a whole number of millimetres greater than 0, received ${stockLength}`);
  }
  if (!Number.isInteger(kerf) || kerf < 0) {
    throw new RangeError(`kerf must be a whole number of millimetres, 0 or more, received ${kerf}`);
  }
  cuts.forEach((cut, i) => {
    if (!Number.isInteger(cut) || cut <= 0) {
      throw new RangeError(`cut ${i + 1} must be a whole number of millimetres greater than 0, received ${cut}`);
    }
    if (cut > stockLength) {
      throw new RangeError(`cut ${i + 1} (${cut} mm) is longer than the stock length (${stockLength} mm)`);
    }
  });

  // Equal lengths are interchangeable, so a plain descending sort is deterministic.
  const sorted = [...cuts].sort((a, b) => b - a);
  const pieces: number[][] = [];
  const used: number[] = [];
  for (const cut of sorted) {
    let placed = false;
    for (let b = 0; b < pieces.length; b++) {
      if (used[b] + kerf + cut <= stockLength) {
        pieces[b].push(cut);
        used[b] += kerf + cut;
        placed = true;
        break;
      }
    }
    if (!placed) {
      pieces.push([cut]);
      used.push(cut);
    }
  }

  let total = 0;
  for (const cut of cuts) total += cut;
  const bars: CutBar[] = pieces.map((p, b) => ({
    cuts: p,
    offcut: Math.max(0, stockLength - used[b] - kerf),
  }));
  return { bars, barCount: bars.length, waste: bars.length * stockLength - total };
}

Install

fune build

With that line in your source, in a TypeScript project (language typescript in fune.project), fune build resolves it and nothing else, pins them in fune.lock, downloads only the TypeScript package of each, and builds the code above into your project’s .fune/build, one readable file per capability with a header linking back here. Or pin a range in fune.project and build in one step:

fune add construction.timber-length

The manifest, vectors and README with only the TypeScript implementation. Install it without the registry with fune add ./construction.timber-length-1.0.0-typescript.fune, or fetch it from a terminal with fune pull construction.timber-length@1.0.0:typescript.

The whole function, every language, is one file too: construction.timber-length-1.0.0.fune, 19,176 bytes, sha256 124e7adbbd6c2a9011a4643743e9dc813bf87e176a788a2da7e1a58768ac3aea. It installs into a project of any language.

// fune: before construction.timber-length

// fune: after construction.timber-length

// fune: step construction.timber-length after <n|label>

More from the author

- **First-fit decreasing.** Pieces are sorted longest first, and each goes on the first bar (in the order bars were opened) that still has room; if none has, a new bar is opened. It is not always the fewest bars possible (that problem is NP-hard), but it is never more than 11/9 of the optimum plus one, it is what most cutting-list tools and carpenters do by hand, and it is deterministic: equal lengths are interchangeable, so the input order does not change the answer. - **Kerf.** Every cut removes `kerf` millimetres. A bar holds pieces p1..pn when `sum + kerf × (n − 1) <= stockLength`: there is a kerf between each pair, and the last piece may run to the very end of the bar with no final cut. So three 1200 mm pieces do not come out of a 3600 mm length with a 3 mm blade; ignoring kerf is the usual mistake. - **Offcut** is what is left after cutting the last piece off: `stockLength − sum − kerf × n`. When that is less than zero (less than a kerf's width remained) it is 0: the saw turned it to dust. - **Waste** is everything bought but not in a piece, `barCount × stockLength − sum of cuts`: offcuts plus all the kerf.

All lengths are whole millimetres. One call is one section size and one stock length; call it once per section (47×100 studs, 47×150 joists). It does not trim a factory end or allow for defects: add that to each piece, or shorten `stockLength`, if your timber needs squaring.

Errors: a piece that is not a positive whole number, a piece longer than the stock, a stock length that is not positive, or a negative kerf. An empty list buys nothing.

Source: D. S. Johnson, "Near-optimal bin packing algorithms" (MIT, 1973), for first-fit decreasing and its 11/9 bound.

Files