Skip to content

Main content

3D Bin Packing Instance Generator Source Code

Browse the implementation files for 3D Bin Packing Instance Generator.
tool.ts typescript
// Tool: 3D Bin Packing Instance Generator

type GenerationMode = 'guaranteed-feasible' | 'unrestricted';

interface Dimensions {
	depth: number;
	height: number;
	width: number;
}

const MAX_BINS = 100;
const MAX_DIMENSION = 1_000_000;
const MAX_ITEMS = 1_000;
const MODES: GenerationMode[] = [
	'unrestricted',
	'guaranteed-feasible'
];

const parsePositiveInteger = (
	input: unknown,
	maximum: number
): number | null => {
	if (
		(typeof input !== 'string' && typeof input !== 'number') ||
		(typeof input === 'string' && input.trim() === '')
	) {
		return null;
	}

	const value = Number(input);

	return Number.isSafeInteger(value) &&
		value >= 1 &&
		value <= maximum
		? value
		: null;
};

const createRandom = (seed: string): (() => number) => {
	let state = 2166136261;

	for (let index = 0; index < seed.length; index += 1) {
		state ^= seed.charCodeAt(index);
		state = Math.imul(state, 16777619);
	}

	return () => {
		state += 0x6d2b79f5;
		let value = state;
		value = Math.imul(value ^ (value >>> 15), value | 1);
		value ^= value + Math.imul(value ^ (value >>> 7), value | 61);

		return ((value ^ (value >>> 14)) >>> 0) / 4294967296;
	};
};

const randomInteger = (
	minimum: number,
	maximum: number,
	random: () => number
): number =>
	minimum + Math.floor(random() * (maximum - minimum + 1));

const shuffle = <T>(values: T[], random: () => number): T[] => {
	for (let index = values.length - 1; index > 0; index -= 1) {
		const otherIndex = randomInteger(0, index, random);
		[values[index], values[otherIndex]] = [
			values[otherIndex],
			values[index]
		];
	}

	return values;
};

export const generate3dBinPackingInstance = (
	binWidthInput: unknown,
	binHeightInput: unknown,
	binDepthInput: unknown,
	binCountInput: unknown,
	itemCountInput: unknown,
	minimumItemDimensionInput: unknown,
	maximumItemDimensionInput: unknown,
	allowRotationInput: unknown,
	modeInput: unknown,
	seedInput: unknown
): string => {
	const binWidth = parsePositiveInteger(
		binWidthInput,
		MAX_DIMENSION
	);
	const binHeight = parsePositiveInteger(
		binHeightInput,
		MAX_DIMENSION
	);
	const binDepth = parsePositiveInteger(
		binDepthInput,
		MAX_DIMENSION
	);
	const binCount = parsePositiveInteger(binCountInput, MAX_BINS);
	const itemCount = parsePositiveInteger(itemCountInput, MAX_ITEMS);
	const minimumItemDimension = parsePositiveInteger(
		minimumItemDimensionInput,
		MAX_DIMENSION
	);
	const maximumItemDimension = parsePositiveInteger(
		maximumItemDimensionInput,
		MAX_DIMENSION
	);

	if (
		binWidth === null ||
		binHeight === null ||
		binDepth === null ||
		binCount === null ||
		itemCount === null ||
		minimumItemDimension === null ||
		maximumItemDimension === null ||
		minimumItemDimension > maximumItemDimension ||
		maximumItemDimension > Math.min(binWidth, binHeight, binDepth) ||
		(allowRotationInput !== 'yes' && allowRotationInput !== 'no') ||
		!MODES.includes(modeInput as GenerationMode) ||
		typeof seedInput !== 'string' ||
		seedInput.trim() === ''
	) {
		return '';
	}

	const mode = modeInput as GenerationMode;
	const random = createRandom(seedInput);
	const bins = Array.from({ length: binCount }, (_, index) => ({
		id: `bin-${index + 1}`,
		depth: binDepth,
		height: binHeight,
		width: binWidth
	}));
	const items = Array.from({ length: itemCount }, (_, index) => ({
		id: `item-${index + 1}`,
		depth: randomInteger(
			minimumItemDimension,
			maximumItemDimension,
			random
		),
		height: randomInteger(
			minimumItemDimension,
			maximumItemDimension,
			random
		),
		width: randomInteger(
			minimumItemDimension,
			maximumItemDimension,
			random
		)
	}));

	const result: {
		allowRotation: boolean;
		bins: Array<{ id: string } & Dimensions>;
		items: Array<{ id: string } & Dimensions>;
		knownPacking?: Array<{
			binId: string;
			itemId: string;
			x: number;
			y: number;
			z: number;
		}>;
		mode: GenerationMode;
		seed: string;
	} = {
		allowRotation: allowRotationInput === 'yes',
		bins,
		items,
		mode,
		seed: seedInput
	};

	if (mode === 'guaranteed-feasible') {
		const slots: Array<{
			binId: string;
			x: number;
			y: number;
			z: number;
		}> = [];

		for (const bin of bins) {
			for (
				let z = 0;
				z + maximumItemDimension <= bin.depth &&
				slots.length < itemCount;
				z += maximumItemDimension
			) {
				for (
					let y = 0;
					y + maximumItemDimension <= bin.height &&
					slots.length < itemCount;
					y += maximumItemDimension
				) {
					for (
						let x = 0;
						x + maximumItemDimension <= bin.width &&
						slots.length < itemCount;
						x += maximumItemDimension
					) {
						slots.push({ binId: bin.id, x, y, z });
					}
				}
			}
		}

		if (slots.length < itemCount) return '';

		shuffle(slots, random);
		result.knownPacking = items.map((item, index) => ({
			binId: slots[index].binId,
			itemId: item.id,
			x: slots[index].x,
			y: slots[index].y,
			z: slots[index].z
		}));
	}

	return JSON.stringify(result, null, 2);
};

export const Tool: TypeTool = {
	name: '3D Bin Packing Instance Generator',
	slug: 'generate/3d-bin-packing-instance',
	intro:
		'Generate a reproducible 3D bin-packing problem instance as JSON.',
	tool: generate3dBinPackingInstance,
	i: [
		{
			example: '100',
			label: 'Bin Width',
			placeholder: 'Bin width',
			type: 'number',
			value: 100
		},
		{
			example: '100',
			label: 'Bin Height',
			placeholder: 'Bin height',
			type: 'number',
			value: 100
		},
		{
			example: '100',
			label: 'Bin Depth',
			placeholder: 'Bin depth',
			type: 'number',
			value: 100
		},
		{
			example: '1',
			label: 'Bin Count',
			placeholder: 'Number of bins',
			type: 'number',
			value: 1
		},
		{
			example: '10',
			label: 'Item Count',
			placeholder: 'Number of items',
			type: 'number',
			value: 10
		},
		{
			example: '5',
			label: 'Minimum Item Dimension',
			placeholder: 'Minimum width, height, and depth',
			type: 'number',
			value: 5
		},
		{
			example: '20',
			label: 'Maximum Item Dimension',
			placeholder: 'Maximum width, height, and depth',
			type: 'number',
			value: 20
		},
		{
			example: 'yes',
			label: 'Allow Rotation',
			placeholder: 'Allow item rotation',
			type: 'select',
			value: 'yes',
			options: [
				{ value: 'yes', text: 'Yes', selected: true },
				{ value: 'no', text: 'No' }
			]
		},
		{
			example: 'unrestricted',
			label: 'Generation Mode',
			placeholder: 'Select a generation mode',
			type: 'select',
			value: 'unrestricted',
			options: [
				{
					value: 'unrestricted',
					text: 'Unrestricted',
					selected: true
				},
				{
					value: 'guaranteed-feasible',
					text: 'Guaranteed feasible'
				}
			]
		},
		{
			example: 'tool.io',
			label: 'Seed',
			placeholder: 'Random seed',
			type: 'text',
			value: 'tool.io'
		}
	],
	o: [
		{
			example: '{ "bins": [], "items": [] }',
			label: '3D Bin Packing Instance',
			placeholder: 'Generated JSON will appear here...',
			render: 'textarea',
			type: 'text'
		}
	],
	cite: [
		{
			title: 'Bin packing problem - Wikipedia',
			url: 'https://en.wikipedia.org/wiki/Bin_packing_problem'
		}
	]
};

export default Tool;

Description

Browse the implementation files for 3D Bin Packing Instance Generator.

References

  1. Tool.io on GitHub
  2. Tool.io TypeScript tools library

Similar or alternative tools