The Thatcher's Reed Bundles

# The Thatcher's Reed Bundles

The thatcher of bitwick ties the morning's cut reeds into bundles before they go up on the roof. The reeds come off the cart in a fixed order, and the thatcher never reorders them: each bundle is a contiguous run taken from the front of what remains.

You are given three arguments:

• reeds — a list of non-negative integers, the reed lengths in cart order.
• spread — a non-negative integer, the largest allowed difference between the longest and the shortest reed inside one bundle.
• cap — a positive integer, the largest number of reeds one bundle may hold.

The bundling rule, applied to the reeds strictly left to right:

• The first reed starts the first bundle.
• For each later reed, consider adding it to the bundle currently being tied. It may be added only if, after adding it, that bundle holds at most cap reeds and its longest reed minus its shortest reed is at most spread.
• If it may be added, add it. Otherwise the current bundle is tied off as it stands and the reed starts a new bundle.

Write bundleReeds(reeds, spread, cap), which returns a list of bundles. Each bundle is a list of integers — the reed lengths it holds, in cart order. Concatenating the bundles in order must give back reeds exactly. If reeds is empty, return an empty list (never a bundle holding nothing).