test/shared/capacity-fit.test.ts
Rama main · réplica de lectura del repositorio original.
/**
* The exact combined-capacity search: how many whole parent tickets a
* parent's required children can serve together.
*
* Direct unit tests, because the surfaces that exercise the search render
* whole pages, and a bound or a prune that answers one too high oversells a
* group on every page that reads it.
*/
import { expect } from "@std/expect";
import { describe, it as test } from "@std/testing/bdd";
import {
childCapacityPartsFor,
combinedChildCapacityForParent,
} from "#shared/capacity-fit.ts";
import { byGroup } from "#test-utils/by-group-map.ts";
/** One child's part in the brute-force check, mirroring the caller-side part:
* the group ids and the units ceiling. */
type BruteChild = { groupIds: number[]; ownMax: number };
/** Whether placing `units` lines of one child keeps every shared pool within
* its places, with the parent's own `t` places already spent. */
const bruteUnitsFit = (
pools: readonly number[],
spent: ReadonlyMap<number, number>,
remaining: ReadonlyMap<number, number>,
parentGroupIds: readonly number[],
t: number,
units: number,
): boolean =>
pools.every(
(groupId) =>
(spent.get(groupId) ?? 0) + units <=
(remaining.get(groupId) ?? 0) -
(parentGroupIds.includes(groupId) ? t : 0),
);
/** Whether a split of `left` child lines over the children from `index` on
* keeps every shared pool within its places, with the parent's own `t`
* places spent. Zero units always fit: a child can sit a ticket out. */
const bruteSplitWorks = (
children: readonly BruteChild[],
poolsOf: (child: BruteChild) => number[],
remaining: ReadonlyMap<number, number>,
parentGroupIds: readonly number[],
index: number,
left: number,
spent: ReadonlyMap<number, number>,
t: number,
): boolean => {
if (index === children.length) return left === 0;
const child = children[index]!;
const pools = poolsOf(child);
for (let units = 0; units <= Math.min(child.ownMax, left); units++) {
if (
units > 0 &&
!bruteUnitsFit(pools, spent, remaining, parentGroupIds, t, units)
) {
continue;
}
const nextSpent = new Map(spent);
for (const groupId of pools) {
nextSpent.set(groupId, (nextSpent.get(groupId) ?? 0) + units);
}
if (
bruteSplitWorks(
children,
poolsOf,
remaining,
parentGroupIds,
index + 1,
left - units,
nextSpent,
t,
)
) {
return true;
}
}
return false;
};
/** The definition, brute force: the largest quantity whose child lines have a
* split that keeps every pool the children draw from within its places. The
* parent's own spend lands only on the pools it belongs to; pools only the
* parent sits in belong to the caller's parent ceiling. */
const bruteForceCombinedCapacity = (
parentGroupIds: readonly number[],
children: readonly BruteChild[],
remaining: ReadonlyMap<number, number>,
): number => {
const poolsOf = (child: BruteChild): number[] =>
child.groupIds.filter((groupId) => remaining.has(groupId));
const ledgerPools = [
...new Set(
children
.filter((child) => child.ownMax > 0)
.flatMap((child) => poolsOf(child)),
),
];
for (let t = 12; t > 0; t--) {
const parentFits = ledgerPools.every(
(groupId) =>
!parentGroupIds.includes(groupId) || (remaining.get(groupId) ?? 0) >= t,
);
if (
parentFits &&
bruteSplitWorks(
children,
poolsOf,
remaining,
parentGroupIds,
0,
t,
new Map(),
t,
)
) {
return t;
}
}
return 0;
};
describe("childCapacityPartsFor", () => {
test("reads each child's groups from the one lookup and its ceiling from its own source", () => {
const child = { id: 11, places: 4 };
expect(
childCapacityPartsFor(
new Map([[11, [7, 8]]]),
[child],
(c) => c.id,
(c) => c.places,
),
).toEqual([{ groupIds: [7, 8], ownMax: 4 }]);
});
test("gives a child absent from the lookup no pools", () => {
// A listing that belongs to no group cannot draw from any pool, so an
// absent entry reads as an empty set, not as unknown.
const child = { id: 12, places: 2 };
expect(
childCapacityPartsFor(
new Map(),
[child],
(c) => c.id,
(c) => c.places,
),
).toEqual([{ groupIds: [], ownMax: 2 }]);
});
});
describe("combinedChildCapacityForParent", () => {
test("sums the children's own ceilings when they share no capped group", () => {
expect(
combinedChildCapacityForParent(
[7],
[
{ groupIds: [8], ownMax: 2 },
{ groupIds: [], ownMax: 1 },
],
byGroup({ 8: 100 }),
),
).toBe(3);
});
test("bounds children sharing one pool once, not once per child", () => {
// Two children in the same pool of four spots: two whole pairs fit, so
// together they serve two parent tickets, never the sum of their
// ceilings (four).
expect(
combinedChildCapacityForParent(
[7],
[
{ groupIds: [7], ownMax: 2 },
{ groupIds: [7], ownMax: 2 },
],
byGroup({ 7: 4 }),
),
).toBe(2);
});
test("refuses a count the flow bound passes but no split can place", () => {
// Both children draw both pools, and each pool holds five places with
// the parent spending three: the residuals (two each) pass the flow
// bound for three lines, but the largest child's room (two) leaves one
// line the smaller child cannot place in pools it has already emptied.
// The exact search refuses it and answers two.
expect(
combinedChildCapacityForParent(
[7, 8],
[
{ groupIds: [7, 8], ownMax: 4 },
{ groupIds: [7, 8], ownMax: 2 },
],
byGroup({ 7: 5, 8: 5 }),
),
).toBe(2);
});
test("bounds a pool across children whose shared sets merely overlap", () => {
// One child uses pool A alone, the other pools A and B. Both draw pairs
// from A, so A bounds their total even though the children partition
// into different shared sets.
expect(
combinedChildCapacityForParent(
[7, 8],
[
{ groupIds: [7], ownMax: 2 },
{ groupIds: [7, 8], ownMax: 2 },
],
byGroup({ 7: 4, 8: 4 }),
),
).toBe(2);
});
test("ignores a shared pool whose remaining is unknown", () => {
// Only capped groups with a known remaining enter the bound: a daily
// child's pool with no submitted date bounds nothing here, and the
// submit fold decides.
expect(
combinedChildCapacityForParent(
[7],
[
{ groupIds: [7], ownMax: 2 },
{ groupIds: [7], ownMax: 2 },
],
byGroup({}),
),
).toBe(4);
});
test("serves two, not four, when each child draws a different pool", () => {
// The parent takes one place in both pools per ticket: at three tickets
// only one child place is left in each pool, so the three child lines the
// tickets need cannot all be placed. Two tickets fit: two child lines
// through each pool.
expect(
combinedChildCapacityForParent(
[7, 8],
[
{ groupIds: [7], ownMax: 2 },
{ groupIds: [8], ownMax: 2 },
],
byGroup({ 7: 4, 8: 4 }),
),
).toBe(2);
});
test("spares children that do not use a tight pool", () => {
// The parent's two pool places go to two tickets whose child lines both
// ride the child outside the tight pool; that child's ceiling (three)
// covers both lines. The tight pool's own ceiling holds the parent to
// two tickets, and the child inside it can sit them out.
expect(
combinedChildCapacityForParent(
[7],
[
{ groupIds: [7], ownMax: 2 },
{ groupIds: [8], ownMax: 3 },
],
byGroup({ 7: 2, 8: 100 }),
),
).toBe(2);
});
test("answers six hundred sixty six on large pools without walking every count", () => {
// Two pools of a thousand places, the parent in both, two children of
// five hundred each in one pool apiece. At t tickets each pool holds t
// parent places and 1000 - t child places, and the two children can
// place 2 × min(500, 1000 - t) lines, so the last feasible t is 666.
// A walk down from a thousand would retry every failing count from the
// top; the search answers in a handful of checks.
const started = performance.now();
expect(
combinedChildCapacityForParent(
[7, 8],
[
{ groupIds: [7], ownMax: 500 },
{ groupIds: [8], ownMax: 500 },
],
byGroup({ 7: 1000, 8: 1000 }),
),
).toBe(666);
expect(performance.now() - started).toBeLessThan(5000);
});
test("does not let a multi-pool child split one unit across its pools", () => {
// A child's unit takes one place in EVERY pool the child belongs to.
// The child below sits in pools A and B, holds two units of its own,
// and pool B has nothing left: the child can serve nothing, even though
// a flow that lets one unit travel through pool A alone would answer
// two. The flow bound only rejects; the exact split decides.
expect(
combinedChildCapacityForParent(
[7, 8],
[
{ groupIds: [7, 8], ownMax: 2 },
{ groupIds: [7], ownMax: 0 },
],
byGroup({ 7: 4, 8: 0 }),
),
).toBe(0);
});
test("lets a child sit a ticket out so a later child can carry the line", () => {
// Pool A has almost nothing left, so the largest child — the only one
// that draws from it — sits both tickets out, and the second child
// carries both lines through pool B on its own.
expect(
combinedChildCapacityForParent(
[7, 8],
[
{ groupIds: [7], ownMax: 3 },
{ groupIds: [8], ownMax: 2 },
],
byGroup({ 7: 2, 8: 4 }),
),
).toBe(2);
});
test("refuses a quantity no child order can complete", () => {
// Every child draws pool A alone, so t tickets need t lines through a
// pool with room for fewer after the parent's own places. No split can
// finish, and the search must say so rather than answer a partial one.
expect(
combinedChildCapacityForParent(
[7],
[
{ groupIds: [7], ownMax: 2 },
{ groupIds: [7], ownMax: 2 },
],
byGroup({ 7: 5 }),
),
).toBe(2);
});
test("serves two, not four, when only the children share a pool", () => {
// The parent sits outside the capped group, so neither child shares a
// pool with it — but both children draw from the same group with two
// places left. Each child line takes one of them, so the children can
// serve two parent tickets, never the sum of their ceilings (four), and
// a minimum of three must read unservable.
expect(
combinedChildCapacityForParent(
[],
[
{ groupIds: [7], ownMax: 2 },
{ groupIds: [7], ownMax: 2 },
],
byGroup({ 7: 2 }),
),
).toBe(2);
});
test("binds a child-only pool and spares it the parent's spend", () => {
// Child two draws pool A with the parent AND a child-only pool B with
// one place left. B bounds child two to one line, so the children serve
// three tickets, not four. B never holds the parent, so the parent's
// tickets must not subtract from it — charging the parent there would
// answer two.
expect(
combinedChildCapacityForParent(
[7],
[
{ groupIds: [7], ownMax: 2 },
{ groupIds: [7, 8], ownMax: 2 },
],
byGroup({ 7: 10, 8: 1 }),
),
).toBe(3);
});
test("answers eight with thirty children on two tight pools without walking every split", () => {
// Thirty one-unit children all drawing two child-only pools of eight
// places each: the flow bound sums the pools (sixteen) and accepts a
// need of fifteen, while every line takes one place in BOTH pools, so
// eight is the most the children can serve. The include/exclude walk
// retries millions of splits for that midpoint; the memoised walk visits
// each (child, owed, pool levels) state once.
const children = Array.from({ length: 30 }, () => ({
groupIds: [7, 8],
ownMax: 1,
}));
const started = performance.now();
expect(
combinedChildCapacityForParent([], children, byGroup({ 7: 8, 8: 8 })),
).toBe(8);
// The unbounded walk spends seconds on one date-less evaluation; a daily
// parent repeats it per offered date, so the bound has to hold with room
// for a whole request.
expect(performance.now() - started).toBeLessThan(1000);
});
test("matches a brute-force allocator on random small graphs", () => {
// The generator is a fixed-seed LCG so a failure names the same graphs on
// every run.
const seed = 0x2f6e2b1;
let state = seed;
const next = (bound: number): number => {
state = (Math.imul(state, 1_103_515_245) + 12_345) & 0x7fffffff;
return state % bound;
};
for (let round = 0; round < 300; round++) {
const poolCount = 1 + next(3);
const remaining = new Map<number, number>(
Array.from({ length: poolCount }, (_, index) => [index + 1, next(7)]),
);
const parentGroupIds = Array.from({ length: poolCount }, (_, index) =>
next(2) === 0 ? index + 1 : 0,
).filter((groupId) => groupId > 0);
if (parentGroupIds.length === 0) parentGroupIds.push(1);
const childCount = next(4);
const children = Array.from({ length: childCount }, () => {
const groupIds = Array.from({ length: poolCount + 1 }, (_, index) =>
next(2) === 0 ? index + 1 : 0,
).filter((groupId) => groupId > 0);
return { groupIds, ownMax: next(4) };
});
const exact = combinedChildCapacityForParent(
parentGroupIds,
children,
remaining,
);
const brute = bruteForceCombinedCapacity(
parentGroupIds,
children,
remaining,
);
expect(
`round ${round}: pools ${JSON.stringify([...remaining])} parent ${JSON.stringify(parentGroupIds)} children ${JSON.stringify(children)}: exact ${exact} brute ${brute}`,
).toBe(
`round ${round}: pools ${JSON.stringify([...remaining])} parent ${JSON.stringify(parentGroupIds)} children ${JSON.stringify(children)}: exact ${brute} brute ${brute}`,
);
}
});
});